Set 3: block and stream crypto
More block cryptography!
Challenge 17: the CBC padding oracle
The setup:
- a function that pads and encrypts one text chosen at random from a list, with CBC, using one unknown key generated at the beginning. PKCS#7 padding is used.
- a second function, the oracle, decrypts a ciphertext and returns whether the padding is valid or not.
Turns out that we can exploit the oracle to uncover the plaintext.
Let's describe a bit how CBC decryption works: a ciphertext block, let's say C2, is passed through AES with the secret key, producing the _intermediate state _I2; this is then XOR'ed with C1, the previous ciphertext block (with C0 = IV), to get the final plaintext P2. Therefore:
P2 = I2 XOR C1
We can manipulate C1 at will. Let's start by leaving C1[0...15] as they are, and setting C1[16] (the last byte of the block; let's assume the block size is 16 bytes as with standard implementations) to '\x00'. We pass the modified C1 + unchanged C2 to the oracle. If the oracle returns true, this decrypted to something with valid padding. If the oracle return false, we try again by setting C1[16] to \x01, then to \x02, etc... until the oracle returns true (essentially we try all possible bytes).
As the challenge suggests, if the oracle returns true it is very likely that the valid padding is \x01; \x02 is also possible, if the previous byte was \x02 too, but much less likely. So let's assume the last byte of P2, P2[16], is \x01. We can recover the last byte of I2:
I2[16] = P2[16] XOR C1[16]
Since we did not touch C2, I2 is the same as for the real untampered ciphertext. We can therefore find the real plaintext:
P2[16] = I2[16] XOR C1[16]
At this stage this will just be padding. Let's move on. This time we deal with second-to-last bytes: we control C1[15] such that P1[15] is valid padding. The most likely possibility is for P1[15] and P1[16] to be \x02. So we leave C1[1...14] unchanged, we set C1[16] so that P1[16] is \x02:
C1[16] = \x02 XOR I2[16]
and we try all possibilities for C1[15] until the oracle returns true. When that happens, we know P2[15] was \x02. From that we find I2[15], and then we repeat as above. We work backwards until we have uncovered the whole block.
For the first block, we need to know the IV: note that we do already because it is returned as part of the encryption procedure.
Challenge 18: implement CTR
Implement the CTR mode of AES. In CTR, you use AES to encrypt a block formed by a fixed nonce and the value of a counter, which is usually incremental from 0. The resulting block, called the keystream, is XOR'ed with the plaintext to produce the ciphertext.
In the decryption, AES encryption is used on the nonce plus counter, and then the ciphertext is XOR'ed with the result.
Challenge 19: break fixed-nonce CTR using substitutions
In this challenge, we exploit the fact that using the same nonce for multiple CTR encryptions is not a great idea. We encrypt 40 ciphertexts using the same nonce (and counter, since it is reset at every encryption).
Now due to how CTR work, we have that
plaintext XOR ciphertext = keystream
and the keystream is always the same, because the input and the key never changes.
Initially I thought of uncovering the keystream byte-by-byte. I tried all possible options for the first keystream byte (there are not many) until I found that keystream XOR ciphertext gives a readable plaintext byte for all the ciphertexts. To simplify things, I added the assumption that all plaintexts start with a capital letter, which proved correct. I then repeated this for subsequent bytes.
However for every byte there were too many possibilities that gave readable characters for all plaintexts. The challenge suggests to use heuristics for English, but I did not know many that could work on few characters and could be implemented easily.
I worked on the reverse. I found the first keystream byte by assuming the plaintexts should start with a capital letter. Then I would look for one plaintext for which guessing the next character was easy, assumed I was right, and compute the keystream byte as
keystream = ciphertext XOR plaintext
For instance, one plaintext started with 'W' so I assumed the next character was 'h' and computed the keystream byte from that. Then I used the keystream byte to compute all the other plaintext bytes and see if they made sense next to the first bytes. If it did, I would move to the next byte, otherwise I knew my assumption was wrong and I looked for a different one. It was especially easy to find which text had just "completed" a word so I could guess a whitespace next. After I recovered enough characters I googled the first words and found the complete poem.
My code contains all the guessed next characters in order: https://github.com/shainer/matasano/blob/master/set3/break_fixed_nonce.py#L111. You can see many of them are indeed whitespaces.
Challenge 20: break fixed-nonce CTR statistically
TODO
Challenge 21: MT19937 Mersenne Twister RNG
Implement a Mersenne Twister random number generator. We actually need our own implementation for the next challenges.
Challenge 22: crack the seed
The generator is initialized like this:
- Wait a random number of seconds.
- Seed the generator with the current Unix timestamp.
- Wait another random number of seconds.
- Get a 32-bit integer from the generator.
From the integer, we want to recover the seed. This has a simple and pretty hackish solution: just try many seeds starting from the current timestamp backward, until the generator produces the same integer you got. Generators seeded with the same number will always produce the same sequence by definition.
I looked around to see if other people had found a solution not relying on brute force, but all of them came up with this. Let me know if you did it differently.
Challenge 23: Clone a generator from its output
Given enough outputs of a generator, you are able to recover the internal state. The internal state is used to clone the generator: such clone can reproduce all past outputs of the generator and predict the next one.
Since I found this especially interesting for its mathematical computation, I already explained how to do it on an article on my website.
Challenge 24: MT stream cipher
TODO.