The last PlaidCTF was full of very interesting challenges. Giga was one of them in the crypto thread. The source code of the application was provided and it reveal an RSA cryptosystem. Each time you connect the server, it generate a new key and encrypt the flag with it, after you can send any strings and get the encrypted result.
A quick look into the code shows extra effort on the random function, to insert a vulnerability. The quality of the generated random is degraded and partially reused beetween sessions. So, we can guess a faulty key generation, and a possible attack is about common factor. A good reading is available here.
The source code provided is self-contained and I started to debug my attack locally, simulating the same conditions :
#!/usr/bin/env python
# PlaidCTF [FFF] Crypto challenge : giga 250pts
# Writeup : Guenael
#
# Vulnerability : Random fault RSA key generation
# Attack : RSA common factor attack
# References : http://www.loyalty.org/~schoen/rsa/
import os
import sys
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from Crypto.Hash import MD5
DEBUG = 1
# Code from Rosettacode : http://rosettacode.org/wiki/Greatest_common_divisor#Python
def gcd(u, v):
return gcd(v, u % v) if v else abs(u)
# Code from Rosettacode : http://rosettacode.org/wiki/Modular_inverse#Python
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
# Code from Rosettacode : http://rosettacode.org/wiki/Modular_inverse#Python
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m
# Random fault vulnerability
def rng(n):
if DEBUG>1: print 'arg. n= ' + str(n)
global rbuf
rand = rbuf[:n]
rbuf = rbuf[n:]
while (len(rbuf) < 4096):
hr.update(os.urandom(4096))
rbuf += rbuf + hr.hexdigest()
if DEBUG>1: print 'ret. rand= ' + str(bytes_to_long(rand))
return rand
rbuf = os.urandom(4096)
hr = MD5.new()
clearText = 'theSecretLocalFlag'
nArray = []
while True:
rsa = RSA.generate(1024,rng)
e=65537 #e = getattr(rsa,'e') #65537 by default
ciphertext = bytes_to_long(rsa.encrypt(clearText,"")[0])
a = 2**e - bytes_to_long(rsa.encrypt("\x02","")[0])
b = 3**e - bytes_to_long(rsa.encrypt("\x03","")[0])
n = long(extended_gcd(a,b)[0])
for nc in nArray:
p = extended_gcd(nc,n)[0]
if (p > 2**510): # Possible cadidate close to 1024/2 bits ?
q = n / p # Deduct q
d = modinv(e, (p-1)*(q-1)) # Calculate the private key
if DEBUG:
print "n= " + str(n) + "\n"
print "p= " + str(p) + "\n"
print "q= " + str(q) + "\n"
print "d= " + str(d) + "\n"
print("Decrpyted ciphertext: ")
print long_to_bytes(pow(ciphertext, d, n))
quit()
nArray.append(n)
if DEBUG: print "Trying another candidate..."In a second time, the code was adapted to connect the real server :
#!/usr/bin/env python
# PlaidCTF [FFF] Crypto challenge : giga 250pts
# Writeup : Guenael
#
# Vulnerability : Random fault RSA key generation
# Attack : RSA common factor attack
# References : http://www.loyalty.org/~schoen/rsa/
import re
import telnetlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from Crypto.Hash import MD5
DEBUG = True
# Code snip from Rosettacode : http://rosettacode.org/wiki/Modular_inverse#Python
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
# Code snip from Rosettacode : http://rosettacode.org/wiki/Modular_inverse#Python
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m
e=65537 #65537 used by default on Crypto.PublicKey API
HOST = '184.73.59.25'
PORT = 4321
MSG = "Now enter a message you wish to encrypt: "
nArray = []
while True:
tn = telnetlib.Telnet(HOST,PORT)
ciphertext = long(re.search('={34}\W(\w+?)\W={34}', tn.read_until(MSG), re.MULTILINE).groups()[0],16)
tn.write("\x02") # Short values are faster for next gcd
a = 2**e - long(re.search('={34}\W(\w+?)\W={34}', tn.read_until(MSG), re.MULTILINE).groups()[0],16)
tn.write("\x03")
b = 3**e - long(re.search('={34}\W(\w+?)\W={34}', tn.read_until(MSG), re.MULTILINE).groups()[0],16)
tn.close()
n = long(extended_gcd(a,b)[0]) # Extract the public key
for nc in nArray:
# Looking for a common factor with the previous keys
p = extended_gcd(nc,n)[0]
# Remove false positives. Prime close to 1024/2 bits ?
if (p > 2**510):
q = n / p
d = modinv(e, (p-1)*(q-1)) # Calculate the private key
if DEBUG:
print "n= " + str(n) + "\n"
print "p= " + str(p) + "\n"
print "q= " + str(q) + "\n"
print "d= " + str(d) + "\n"
print("Decrpyted ciphertext: ")
print long_to_bytes(pow(ciphertext, d, n)) # Decode ciphertext with the private key
quit()
nArray.append(n)
if DEBUG: print "Trying another candidate..."And finally, the original source code of the challenge (available on other place, but given here to be self-contained)
Thanks FFF!
#!/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()