Nuit du hack 2011 CTF Crypto 300

Crypto300 (150 pts.) source

Python source code is very clear and concise, and could sometimes bring out lots of clues. This is particularly true for this challenge.

Summary: key exchange algorithm based on permutations (braid based cryptography), has some vulnerabilities

Intro

This challenge is based on an interesting cryptosystem. It operates on permutations of the set {1..22}, which are called braids (more strictly braids are defined here).

Both sides – client and server – have a public known braid (it’s 0D121404010... here). Then they generate there private keys by shuffling halves of the braid 0001010203040506...1415: server shuffles the left part, client shuffles the right part [braid.py:102]. Also a reversed private key is calculated – it contains indexes of corresponding values in braid (for example [4,3,1,2] is reverse of [3,4,2,1]). Then this code is executed:

self.pubkey = self.privkey.combine(self.K.combine(self.privrkey))

Where K is that common known braid. combine uses it’s caller’s braid as permutation vector for the argument, e.g. [4,3,2,1].combine([3,2,4,1]) = [1,4,2,3]. So, this pubkey is sent to the other side and the analogical operation is done there [braid.py:140]:

self.secret = self.Pk.privkey.combine(pubkey.combine(self.Pk.privrkey))

So, the server has:
secret = ServerPriv(ClientPriv(K(ClientPrivRev(ServerPrivRev))))
and the client has:
secret = ClientPriv(ServerPriv(K(ServerPrivRev(ClientPrivRev))))
Due to the nature of this algorithms and the fact, that both sides have shuffled different halves, this secrets are equal. So, this is the final shared key the both sides have and use to make a key for the Blowfish encryption.

Challenge

Now, back to the challenge. Let’s run client.py:

crypto300 $ py client.py 
[Crypto300 sample client]
[i] Welcome on Goofyleaks. Can I haz ur public kay ?
[+] Your leaked flag: ##NOT ALLOWED##

We don’t receive a flag, because the server sends flag only when our pub key is what defined in allowed_pubkeys=['0F0C110...'] on the server side [network.py:112]. But if we just send that pubkey to the server, we won’t have the corresponding private keys and won’t be able to decode the message.

So, the most straightforward solution is to bruteforce all permutations of the right half, to find an appropriate privkey. The half is 11 bytes, so number of permutations is 11! ~ 39kk. Here is a script for that:

crypto300 $ time py bruteforce.py 
0/40 000102030405060708090A0B0C0D0E0F101112131415
1/40 000102030405060708090A0B0E13140F150D11120C10
2/40 000102030405060708090A0B11101214130F0D0E0C15
3/40 000102030405060708090A0B140E100D130C0F111215
4/40 000102030405060708090A0C0D0B0F13121014150E11
5/40 000102030405060708090A0C0F140B0D111310120E15
6/40 000102030405060708090A0C1210140F0E0B0D111315
7/40 000102030405060708090A0C150E11140D0F12130B10
8/40 000102030405060708090A0D0E0B11100C1412130F15
9/40 000102030405060708090A0D10140C130B0E0F111215
10/40 000102030405060708090A0D13110B0C150F12140E10
11/40 000102030405060708090A0E0B0F141113120D100C15
12/40 000102030405060708090A0E0F0B1215130C0D101114
13/40 000102030405060708090A0E11140F0D120C13150B10
14/40 000102030405060708090A0E14110C130F120D100B15
15/40 000102030405060708090A0F0C100B0E120D11131415
16/40 000102030405060708090A0F100B14120D0E13150C11
GOT IT: 000102030405060708090A0F12110E0D151410130B0C
[i] Welcome on Goofyleaks. Can I haz ur public kay ?
0d0f0c06041412030a0e0805010709151002000b1311
[+] Your leaked flag: Br4iDCrypto_i5_b3au7ifu11

real    23m13.224s
user    23m2.086s
sys    0m1.436s

Note: this method was offered by kyprizel from Smoked Chicken. I solved the task with the following one:

Another way

Another way has a life because of the two mistakes:

  • The server’s private key is generated only once – at startup
  • Received public key isn’t checked for validness

When generating shared secret, The server is creating it’s secret key in such way [braid.py:140]:
secret = ServerPriv.combine(ReceivedPubkey.combine(ServerPrivr))

So, if we pass, for example, a braid 000000000..00 or "00"*22, then

  • ReceivedPubkey.combine(ServerPrivr) = ServerPrivr[0]*22
  • secret = ServerPrivr[0]*22 (because bytes at any index are equal)

Nice, don’t? But the server uses this secret as a key to blowfish, so how can we get it? The answer is obvious – there are only 22 possible keys, so we can easily check each one.

So, the idea is to send fake 22 public keys for each one byte of the server’s privr key. Then we just rebuild the server’s priv key and then, combining it with the only accepted pub key (0F0C11...) we get the secret, which is used by server to encrypt the message!

A script for that:

crypto300 $ time py fast_solve.py 
[0]
[0, 6]
[0, 6, 5]
[0, 6, 5, 7]
[0, 6, 5, 7, 3]
[0, 6, 5, 7, 3, 10]
[0, 6, 5, 7, 3, 10, 4]
[0, 6, 5, 7, 3, 10, 4, 1]
[0, 6, 5, 7, 3, 10, 4, 1, 8]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16, 17]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[0, 6, 5, 7, 3, 10, 4, 1, 8, 2, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
Br4iDCrypto_i5_b3au7ifu11

real    0m13.953s
user    0m0.284s
sys    0m0.024s

14 seconds vs 24 minutes!

Outro

Bruteforce solution
Fast solution

Some info about braid crypto

Cool solution by Sleepya (reversing combine function)

Leave a Reply

Your email address will not be published.