Matasano Crypto Challenges Set 3

This is a great attack, and it relies on something we setup and tested in set 2, namely that the CBC block we're decrypting has valid padding. This is our first ciphertext only attack, its also our first exposure to a side-channel leak. Its important to realize that a side-channel attack exploits information that depends on the encryption procedure, but it does not attack the encryption procedure directly. Side-channel attacks can be prevented by securing the information leaked, in this case, the fact that the padding is invalid should not be exposed to our adversaries.

The attack procedure itself is outlined very well on the wikipedia page, so I won't go over too much of the specifics (annoying I know, but the article really does cover it at the right level). We've used an oracle before in Challenge 11, but this is the first time its front and center. Oracle's in cryptanalysis are appropriately named because they tell us something about the ciphertext without giving us the plaintext back. In this specific case, the oracle is telling us if the submitted ciphertext has valid padding of the plaintext. Through successive edits to the ciphertext (in order to create valid padding) we are able to extract the plaintext bytes.

In real world applications, the oracle is typically a remote server where we can submit cipher texts and observe the server's response. The server has a vested interest in not exposing the plaintext, but it may leak information about the decryption that we as attackers can exploit.

AES-CTR is our first stream cipher. The idea is to use the output of AES-ECB when encrypting the result of a running counter and a key. This generates a stream of random looking bits that we can use to XOR against an input string. As soon as we see the XOR part of the operation, alarm bells should ring that bit-flipping attacks are available. What we're doing here is using AES-ECB as a CSPRNG.

The next two challenges are related. The first sets up our intuition about guessing the keystream when its re-used, and the second (Challenge 20) is a throwback to the repeating-key XOR from Set 1. (You remember that right?) all the same techniques still apply, so dust of your code from Set 1 and knock these two out quickly.

I became obsessed with Challenge 21-23 for a time. I wrote about it previously, so I won't repeat myself. Challenge 21 is simply implementing the algorithm, it goes pretty quick. You'll want to at least implement it yourself following pseudocode or translating from a different language to get a feel for how its going.

The key idea here is to set the MTRNG up with an unknown timestamp, and then discover it by trying successive seeds in another MTRNG until you get the same output as the MTRNG with the unknown seed. The problem suggests that you wait (as you would have to do if the MTRNG was on a remote server) and then try to clone the output, but I was lazy.

If we do Challenge 24 given the parameters of the challenge, then the MTRNG is easily crackable (the key space (2¹⁶) is really small) and the follow-up exercise (password reset token) is seeded by the current timestamp. This doesn't do justice to the MTRNG as a CSPRNG. Challenges 20-23 systematically broke the MTRNG as a cryptographic construct, but they rely on the attacker recovering the entire 32 bit (or 64 bit) output of the algorithm.

If the attacker only has access to the first 8 bits of the output, it is impossible to recover the internal state. Then the security lies only in the key. In this problem, the keyspace is too small. Even if we expanded our keyspace to be 32 or 64 bit single-integer seeds, then our attack would still take as long as it took our implementation to try each possible integer seed.

Instead, it is possible to seed the MTRNG's internal state with 628 32bit integers with a suitable amount of entropy, and use the resulting output as a secure key-stream. Now the key space has grown considerably (2^(628*32) to be exact), and it is no longer feasible to try to clone the stream even on modern hardware.