# Blobfish - Cryptography - 300 points
> We designed our own proprietary cipher, called Blobfish. We were very proud of it, until someone mounted a chosen-plaintext attack on the cipher, and sent the master key to us. He requested a large amount of money to show us the weakness in Blobfish. Fortunately, we have the queries (plaintexts) he made to our system, as well as the responses (ciphertexts). >> Our CEO decided to hire someone less greedy to help us redesign Blobfish. But he must first prove he is worthy. Look at the log, and the cipher design. If you can find the master key, use the function `make_flag()` on it to generate the flag. Send us the flag, and we'll get back to you for further negotiations. >> PS: `make_flag()` is defined at the end of Blobfish.py.
We are given a list of 200 plaintext -> ciphertext pairs done with an unknown encryption key, and our job is to find the key.
The Blobfish cipher is a simple[Substitution-permutation network](https://en.wikipedia.org/wiki/Substitution-permutation_network). It has a block size of36 bits, and the substitution step uses a 6-to-6 bit S-box. It has 3 rounds, with each round using a separate 36-bit key.(As an aside, this is a totally different structure than the Blo**w**fish cipher, which uses a Feistel network, so not surewhy they picked that name)
The overall structure of the encryption of a block is:
    sbox0    perm0    xor_key0    sbox1    perm1    xor_key1    sbox2    perm2    xor_key2 It is clear from the data in `log.txt` that the cipher is weak - encrypting `0x02CC0F857` gives `0xE9BFB5DFD` as a resultand encrypting the same plaintext with a few bits flipped, `0x02CC0F859` results in `0xE2BFF5DFD` which is the sameciphertext with some bits flipped.
The first idea was to check the S-box function for obvious weaknesses like linearity, where one or more of the output bitsare only affected by a subset of the input bits. Sadly, a quick analysis via the provided `test_sbox.py` script showed itwas nonlinear.
After that, we tried to find some pattern in weak plaintext and ciphertext pairs like the ones above, using our own keys,but even though there were tons of them, no clear relation emerged.
We then considered just directly brute forcing the keys, but even with a meet-in-the-middle attack, one of the sides wouldhave a keyspace of 2*36 bits, which is too large for a head-on attack.
But then we realized that a full brute force wasn't needed - consider the ciphertext after the `sbox2` step - we have sixdistinct 6-bit segments. Going forward, we can see the bits being spread out in `perm2` and xor-ed with six bits of keymaterial, which then results in six bits of ciphertext. If we pick one of the ciphertexts in the log and pick an arbitrary6-bit key `key2a`, we are able to partially decrypt those bits, even back through `perm2` and `sbox2`:
             abcdef    sbox2   |______| |______| |______| |______| |______| |______|             ghijkl   ......   ......   ......   ......   ......    perm2   |___________________________________________________|             .h....   ......   ....l.   .j..i.   .k....   ..g...    xor2    |.v....___......___....z.___.y..w.___.x....___..u...|         key2a = uvwxyz    ct       011001   110100   111100   100010   100111   110111
`abcdef = inv_sbox(ghijkl) = inv_sbox(0^u, 1^v, 1^w, 0^x, 0^y, 0^z)`
We can then pick an arbitrary key `key1a` and that lets us decrypt back through `perm1`:
    sbox1   |______| |______| |______| |______| |______| |______|             .h....   ...l..   ..g...   ...i..   ..k...   j.....    perm1   |___________________________________________________|             ghijkl    xor1    |mnopqr_____________________________________________|         key1a = mnopqr             abcdef
Given a ciphertext and two 6-bit keys `key1a` and `key2a`, we can now deduce six bits of the result after the `sbox1`substitution. While it might not seem like much, this means that for each of the sboxes, we can eliminate half theinputs, leaving 32 out of 64 possible inputs for each box.
We then look at the plaintext corresponding to that ciphertext. We see that `sbox0` and `perm0` can easily be calculatedwithout knowing any key material. Focusing a single sbox in `sbox1` - we now know the six bits of plaintext before the xorwith a six-bit `key0a`, and also 32 possible inputs for that box. Xor-ing each of those 32 inputs with the plaintext bitsresult in 32 possible candidate keys for `key0a`. Then the trick - **when the keys are the same, but the plaintext andciphertext differ, the same `key0a` must be present in all candidate keys for that sbox**. Basically, given `key1a` and`key2a`, the intersection of all possible inputs for a specific sbox in `sbox1` must be nonzero, and if the intersection hasexactly one element, that is a strong candidate for `key0a`.
So, the final algorithm for finding the key is - Iterate over all `key1a` and `key2a`, using the 200 plaintext-ciphertextpairs to narrow down the possible `key0a` candidates. This is a 12-bit brute force, which is easily done. We then repeat thesame process six times, each time focusing on different sboxes, which eventually gives us all bits of the keys.
The final key was [83193ca54 d90e5e945 b29645f8b] and the flag we got from that key was**SharifCTF{8aae67ec50080a359fc92beca22c52e3}**