Nuit du Hack CTF 2011 Crypto 300 Writeup

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