## Monday, April 4, 2011

### Nuit du Hack CTF 2011 Crypto 300 Writeup

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:
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 ?
```

1. 2. are you by any chance looking for a job in .au?

3. Bonjour, à tous j'offre et partage des codes Free Wifi Code Orange et SFR chaque semaine pour vous connecté a internet dans toutes la france

Mon site de partage ▄︻̷̿┻̿═━一 http://caribbeansunshine.co/

wifi gratuit en france