Challenge : http://repo.shell-storm.org/CTF/NDH2K11-prequals/CRYPTO/CRYPTO300/crypto300.zip
The challenge gives me the python code. The code is some kind of key exchange algorithm (I do not know). There are 3 important methods in Braid class.
class Braid: # ... def reverse(self): rev = [self.items.index(i) for i in range(self.size)] return Braid(rev) def combine(self, _braid): if len(_braid) != self.size: raise "Invalid size" return Braid([_braid[self.items[i]] for i in range(self.size)]) def shuffle(self,offset=0,size=0): for j in range(randint(1024,4096)): if size==0: # client for i in range(offset,self.size): # range(11, 22) idx1 = randint(offset,self.size-1) # randint(11, 21) self.swap(i,idx1) else: # server for i in range(offset,size): # range(0, 11) idx1 = randint(0,size-1) # randint(0, 10) self.swap(i,idx1)
The public key and private key are generated from BraidKey class
class BraidKey: def __init__(self, K, client): self.K = K N = len(K) self.privkey = Braid(N) if client: self.privkey.shuffle(offset=N/2) else: self.privkey.shuffle(size=N/2) self.privrkey = self.privkey.reverse() self.pubkey = self.privkey.combine(self.K.combine(self.privrkey))
From code, the client privkey is initialized with [0..21], then shuffled only last 11 elements and first 11 elements are fixed. So the client privkey always be [0..10, random shuffled]. The client privrkey is derived from privkey with so strange reverse function. With the client privkey generation, the client privkey always be [0..10, derived from privkey].
When looking in "server.py", I found
raw_K = '0D1214040108060F050C0E0207030A151009000B1311' self.s = ServerSocket(peer,allowed_pubkeys=['0F0C11040108060B05150E1000090A030D1312140207'])
So the server accepts only public key '0F0C11040108060B05150E1000090A030D1312140207'. From pubkey generation algorithm (the last line in BraidKey::__init__), We know pubkey, half of privkey, K, and half of privrkey. Also the combine() function is reversible. So I think it's possible to find the privkey from pubkey.
It's difficult to explain. Just see the code findpriv.py (I know you guys will understand :P).
K = str2ary(hex2str("0D1214040108060F050C0E0207030A151009000B1311")) pubkey = str2ary(hex2str("0F0C11040108060B05150E1000090A030D1312140207")) priv = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 ] privr = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 ] inter = [ -1 ]*22 # inter is self.K.combine(self.privrkey) for i in range(11): inter[i] = pubkey[i] # pubkey = priv.combine(K.combine(privr)) # for i in [0,11) => priv[i] = i; pubkey[i] = inter[priv[i]] = inter[i] = privr[K[i]] for i in range(11): privr[K[i]] = pubkey[i] # inter = K.combine(privr); inter[i] = privr[K[i]] for i in range(11, 22): inter[i] = privr[K[i]] # pubkey = priv.combine(K); pubkey[i] = K[priv[i]] for i in range(11, 22): if pubkey[i] in inter: priv[i] = inter.index(pubkey[i]) # privr = priv.reverse() for i in range(11, 22): if i in priv: privr[i] = priv.index(i) for i in range(11, 22): if privr[1] != -1: priv[privr[i]] = i # inter = K.combine(privr); inter[i] = privr[K[i]] for i in range(11, 22): inter[i] = privr[K[i]] # pubkey = priv.combine(K); pubkey[i] = K[priv[i]] for i in range(11, 22): if pubkey[i] in inter: priv[i] = inter.index(pubkey[i]) if priv.count(-1) == 1: pos = priv.index(-1) for i in range(22): if i not in priv: priv[pos] = i break print priv
$ python findpriv.py [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 18, 17, 14, 13, 21, 20, 16, 19, 11, 12]
Then I changed the self.privkey.shuffle(offset=N/2) line in BraidKey class to self.privkey = [above privkey].
$ python client.py [Crypto300 sample client] [i] Welcome on Goofyleaks. Can I haz ur public kay ? [+] Your leaked flag: Br4iDCrypto_i5_b3au7ifu11
Answer: Br4iDCrypto_i5_b3au7ifu11
awesome :)
ReplyDeleteare you by any chance looking for a job in .au?
ReplyDelete