Plaid CTF - giga (Crypto 250)

Problem statement:

We found a wonderful new service you can use to secure all of your files with, though it is still in beta.
The source is available at giga.py. And the service can be found at [IP] on port 4321

Service code:

#!/usr/bin/env python
import os
from Crypto.PublicKey import RSA
from Crypto.Hash import MD5
import SocketServer
import threading
import time

rbuf = os.urandom(4096)
hr = MD5.new()

flag = open("secret").read()

def rng(n):
  global rbuf
  rand = rbuf[:n]
  rbuf = rbuf[n:]
  while (len(rbuf) < 4096):
    hr.update(os.urandom(4096))
    rbuf += rbuf + hr.hexdigest()
  return rand


class threadedserver(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass

class incoming(SocketServer.BaseRequestHandler):
  def handle(self):
    cur_thread = threading.current_thread()
    welcome = """
*******************************************
*** Welcome to GIGA! ***
**the super secure key management service**
*******************************************

We are generating an RSA keypair for you now.
(Please be sure to move your mouse to populate the entropy stream)
"""
    self.request.send(welcome)
    rsa = RSA.generate(1024,rng)
    print getattr(rsa,'n')
    #make it look like we're doing hardcore crypto
    for i in xrange(20):
      time.sleep(0.2)
      self.request.send(".")
    self.request.send("\nCongratulations! Key created!\n")

    #no one will ever be able to solve our super challenge!
    self.request.send("To prove how secure our service is ")
    self.request.send("here is an encrypted flag:\n")
    self.request.send("==================================\n")
    self.request.send(rsa.encrypt(flag,"")[0].encode("hex"))
    self.request.send("\n==================================\n")
    self.request.send("Find the plaintext and we'll give you points\n\n")

    #now they can be safe from the FBI too!
    while True:
      self.request.send("\nNow enter a message you wish to encrypt: ")
      m = self.request.recv(1024)
      self.request.send("Your super unreadable ciphertext is:\n")
      self.request.send("==================================\n")
      self.request.send(rsa.encrypt(m,"")[0].encode("hex"))
      self.request.send("\n==================================\n")

server = threadedserver(("0.0.0.0", 4321), incoming)
server.timeout = 4
server_thread = threading.Thread(target=server.serve_forever)
server_thread.daemon = True
server_thread.start()

server_thread.join()

At first glance the code looks pretty good. One thing odd though is the custom random number generator used. Turns out the code to make sure the buffer is full of random data is broken. Not only does it limit data to hex characters (after the first 4096 bytes are used), but it duplicates the data.. (line 20)
Because the random data is used multiple times, and this is a multithreaded server, it’s likely that 2 N’s may share a common factor. Remember RSA; N = p*q; where p and q are large primes (512 bits for 1024 bit RSA).

But we don’t have any way to get N… and this is where more knowledge of RSA comes into play. c = m^e mod N; since we can choose m; and e is 65537 by default in pycrypto (based on quick testing), we are able to figure out N. Since modulus math gives us the remainder, we know that m^e – c = N*k for some k. So if we encrypt 2 things, say the numbers 2 and 4 (since RSA is all number based) and let the cypthertext be c2 for 2 and c4 for 4; we get 2^65537 – c2 = N*k2; and 4^65537 – c4 = N*k4. Taking the GCD of both N*k2 and N*k4 will leave us N*k; where k is an even power of 2. Dividing by 2 until the result is odd leaves us with N.

Code to get secret (named key) and N:

#!/usr/bin/env ruby
#
require './ruby/socket_extras.rb' #implements recv_until - left as an exercise for the reader... 
require 'gmp'
def GetSet()
	server = '184.73.59.25'
	#server = 'localhost'
	port = 4321
	s = TCPSocket.new server, port
	key = s.recv_until("encrypt: ");
	key =~ /==================================\n([0-9a-f]+)\n==================================/
		#key = $1.to_i(16)
		key = GMP::Z($1.to_i(16))
	#puts "k='#{$1}'"
	s.print "\x02"
	c=[]
	c_prime=[]
	c[2] = s.recv_until("encrypt: ");
	c[2] =~ /==================================\n([0-9a-f]+)\n==================================/
		c[2] = GMP::Z(2**65537 - $1.to_i(16))

	s.print "\x04"
	c[4] = s.recv_until("encrypt: ");
	c[4] =~ /==================================\n([0-9a-f]+)\n==================================/
		c[4] = GMP::Z(4**65537 - $1.to_i(16))

	n = c[2].gcd(c[4])

	while n&1 == 0 
		n = n >> 1
	end
	s.close()
	return [n, key]
end

So now we can get at least 1 N.. we need a bunch to try and find ones that have a factor; but the service implements a delay, so threading to the rescue:

#!/usr/bin/env ruby
#
require './ruby/socket_extras.rb'
require 'gmp'

$gList = []

def ThreadMain
	(0..128).each do 
		c = GetSet()
		$gList << c
	end
end

t = []

(0..20).each do
	t << Thread.new { ThreadMain() }
end
found = false
while !found
	puts $gList.size
	$gList.each do |c|
		$gList.each do |i|
			next if i[0] == c[0]
			gc = i[0].gcd(c[0])
			if gc != 1 && gc > 10 then
				puts "FOUND" 
				puts "K = #{c[1].to_s(16)}"
				puts "p = #{(c[0]/gc).to_s}"
				puts "q = #{(gc).to_s}"
				puts "n = #{c[0].to_s}"
				found = true
				break
			end
		end
	end
	sleep 1
end
t.each { |thr| thr.kill }

Once we have K, p, q, and n; we simply need to compute d, and the answer:

#!/usr/bin/env ruby
#
require './ruby/socket_extras.rb'
require 'gmp'

p = GMP::Z(11805116728444088970465485513183327080306344474018225507623675488544127906399172904443763836268125145240727938057195022235109786819172947228222170205336353)
q = GMP::Z(11909456840798246427199708106914367593157640702188915528046958587297551991489948263663943989493907737582570344394542312316615465509039682386736645479545303)
n = GMP::Z(140592528177990270198034735232586968713350050937024133371964431236018188536993314833270805611373402110483523290892272093179281345140375475777410288779880419989198839039896711403989656923965291980676662420979066639625739790746182154681089476563655715027114211099541982136473077443825441951299018191278616299959)
key = GMP::Z(0x22551ac83e34a1958bc6b912d50867df85618ef9fa51b98a4d2b8bed5ef41b10037be3bbba0addca1c0c0030afe8f5bc2c5197376da40a8176211bdb0cb73c98c253c54689eb1824aef9ccd439ee186ef8ff488dae6768f99fb53a39bb2e9ee83caa42a9dbf730fe4ea44e03b1281b2cba5149d9f4140f8a4e370c48e9035aac)


e = GMP::Z(65537)
phi = (p-1)*(q-1)
d = GMP::Z(0)

nm = GMP::Z(0)
begin
	if (GMP::Z(1) + nm) % e == 0 then
		d = (GMP::Z(1) + nm)/e
		d = d.floor()
		break
	end
	nm += phi
end while true

m = key.powmod(d,n)
puts [m.to_s(16)].pack("H*")

And we get: "Im_sure_mega_is_much_better_though";