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]*22secret= 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
Cool solution by Sleepya (reversing combine function)
