Last weekend I participated in the
GitS 2013 CTF for team Clevcode.
Here is my writeup for the crypto 250 challenge, called Rabinsbitch.
The challenge consisted of a python script running on a remote server. The goal was to extract the cryptographic keys from the script.
#
#for the answer take the hash of p,q concatenated together as decimal strings
#such as if p=7,q=11 p being by definition smaller you'd hash the string "711"
#please hash with sha512, thank you and g'luck
import math
import operator
import random,struct
import os,SocketServer
import base64 as b64
def encrypt(m,n):
c=pow(m,2,n)
return c
def extended_gcd(a, b):
if b == 0:
return (1, 0)
else:
(q, r) = (a/b, a%b)
(s, t) = extended_gcd(b, r)
return (t, s - q * t)
def invmod(a, p, maxiter=1000000):
if a == 0:
raise ValueError('0 has no inverse mod %d' % p)
r = a
d = 1
for i in xrange(min(p, maxiter)):
d = ((p // r + 1) * d) % p
r = (d * a) % p
if r == 1:
break
else:
raise ValueError('%d has no inverse mod %d' % (a, p))
return d
def reste_chinois(la,lm):
"""
Return the solution of the Chinese theorem.
"""
M = reduce(operator.mul, lm)
lM = [M/mi for mi in lm]
ly = map(invmod, lM, lm)
laMy = map((lambda ai, Mi, yi : ai*Mi*yi), la, lM, ly)
return sum(laMy) % M
def decrypt(c,p,q):
mp=pow(c,(p+1)/4,p)
mq=pow(c,(q+1)/4,q)
r1 = pow(c, (p+1)/4, p)
r2 = pow(c, (q+1)/4, q)
return (reste_chinois([r1, r2], [p, q]), \
reste_chinois([-r1, r2], [p, q]), \
reste_chinois([r1, -r2], [p, q]), \
reste_chinois([-r1, -r2], [p, q]))
p=7
q=11
n=p*q
TEST=True
if TEST:
m=[]
for x in xrange(200):
m.append(random.getrandbits(1200))
print m[0]
print len(set(m))
assert(len(set(m))>2)
i=0
print decrypt(3,p,q)
for x in m:
enc=encrypt(x,n)
if i%20==0:
print "ENCRYPTED IS %r" %enc
i+=1
assert(x in decrypt(enc,p,q) )
class SignHandler(SocketServer.BaseRequestHandler):
def handle(self):
req=self.request
req.sendall("You must first solve a puzzle, a sha1 sum ending in 26 bit's set to 1, it must be of length %s bytes, starting with %s"%(len(proof)+5,proof))
test=req.recv(21)
ha=hashlib.sha1()
ha.update(test)
if (test[0:16]!=proof or ord(ha.digest()[-1])!=0xff or
ord(ha.digest()[-2])!=0xff or
ord(ha.digest()[-3])!=0xff or
ord(ha.digest()[-4])&3!=3
):
req.sendall("NOPE")
req.close()
return
leng=struct.unpack("H",req.recv(2))[0]
s=""
while len(s) leng:
req.sendall("Okaly Doakaly")
req.close()
return
i=0
s=s[::-1]
for el in xrange(len(s)):
i+=(ord(s[el])<<(8*el))
rets=decrypt(i,p,q)
for el in rets[:-1]:
req.sendall(str(el)+",")
req.sendall(str(rets[-1]))
req.close()
class ThreadedServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
pass
if __name__ == "__main__" and not TEST:
HOST, PORT = "", 9955
server = ThreadedServer((HOST, PORT), SignHandler)
server.allow_reuse_address = True
server.serve_forever()
The challenge server first requires the client to compute a proof-of-work
to prevent brute-forcing. The client should find a string so that, when concatenated
to a seed provided by the server, the last 26 bits of its SHA1 hash are ones. This
took approximately one minute with a naive python implementation on the slow machine
I had at hand.
The server then accepted an integer
c encoded as a byte stream,
computed some values using
c and returned them. The computations were:
p,q = secret
r1 = c ** (p+1)/4 (mod p)
r2 = c ** (q+1)/4 (mod q)
a, so that a*r1 = 1 (mod p) and a*r2 = 1 (mod q)
b, so that b*-r1 = 1 (mod p) and b*r2 = 1 (mod q)
c, so that c*r1 = 1 (mod p) and c*-r2 = 1 (mod q)
d, so that d*-r1 = 1 (mod p) and d*-r2 = 1 (mod q)
The hack here is to choose
c = 1, then both
r1 and
r2 becomes 1.
d will be congruent to -1 in both
modulo
p and
q, so
d = p*q - 1 = M - 1 and
M can trivially be computed. We also have that
b = p*k - 1
for some integer
k. We can now compute
p as
GCD(M,b-1) and then
q=M/p.
The flag were to be computed as the SHA256 hash of the concatenated p and q.
This was actually the most problematic part of the problem, due a copy-paste
error from the proof-of-work code that used SHA1. The final solution is listed
below.
import hashlib, struct
import socket
HOST = 'rabinsbitch.2013.ghostintheshellcode.com'
PORT = 9955
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((HOST, PORT))
data = s.recv(132)
proof = data.split()[-1]
print proof
test = ''
x = 0
while True:
ha = hashlib.sha1()
ha.update(proof + struct.pack("I",x))
d = ha.digest()
if d[-3:] == '\xff\xff\xff' and ord(d[-4])&3 == 3:
test = proof + struct.pack("I",x)
break
if d[-2:] == '\xff\xff':
print "Close..."
x += 1
#assert x & (2**32 - 1) != 0, "Could not find matching proof!"
print "Found proof %r" % test
s.send(test)
i = 0x1
toSend =''
while i > 0:
toSend += chr(i%256)
i = int(i/256)
datagram = struct.pack('H', len(toSend)) + toSend
s.send(datagram)
result = ''
tmp = 'asdf'
while tmp != '':
tmp = s.recv(999)
result += tmp
#result = "1,16941066001474695845719308384813140784186795259157054765289986998445863711720505625812362392697741205506049415906549237302653271360565551697039440068630125139408726686167733805604385582596700326652668377493932061724923381450000827786706063473133681438897765791275734911181038668585952430992240545833488889467911361773431544879600184386683684500892680154414816031266754352400273467267938247266548887205133112948093607346676644817468289304022898908247554057630196442472940983356348803549279910983869343866117264685687034360294868608260912165854176452135379353057412438116196758723769316960521491688495464097529269456197,5634409376365928014416246503986138236992108737039947072941477791958438637877531730514281925969449690964163598045979764319142248921381193502060187717633426958368050694066134300481039643146320871981320853532778576589804902495007704046087597562459337727373717481169459494040528451601731742862806515204023196360495905604537025264792329270035269210755345238017503967990869306160108267542185442376337836021860709096121093532913732125456749131910969411738108129561943901454827954858124025207923012141584943546695856004655276250645522524369645338890458467726951800793914414373991692269936254513675131200905511369778088032944,22575475377840623860135554888799279021178903996197001838231464790404302349598037356326644318667190896470213013952529001621795520281946745199099627786263552097776777380233868106085425225743021198633989231026710638314728283945008531832793661035593019166271483272445194405221567120187684173855047061037512085828407267377968570144392513656718953711648025392432319999257623658560381734810123689642886723226993822044214700879590376942925038435933868319985662187192140343927768938214472828757202923125454287412813120690342310610940391132630557504744634919862331153851326852490188450993705571474196622889400975467307357489140"
[a,b,c,d] = map(int, result.split(','))
M = d+1
pk = b+1
from fractions import gcd
p = gcd(M,pk)
q = M/p
toHash = 'p=0x%x,q=0x%x'%(p,q)
print toHash
ha = hashlib.sha256()
ha.update(toHash)
print 'Solution:', ha.digest().encode('hex')
I liked the proof-of-work mechanism, there were no problems with overloaded
servers. See you all at the Codegate quals in early March!
