Matasano Crypto Challenges Set 2

Challenge 10 asks us to implement AES-CBC, or the Cipher-Block-Chaining mode of AES. It works by XORing the previous ciphertext block with the current plaintext block. This is to improve the "confusion and diffusion" properties of the AES cipher. In ECB mode, we know that the same plaintext encrypts to the same cipher text (ie if P[32:64]==P[80:96], then C[32:64]==C[80:96]). In CBC this is not true because the plaintext is XORed with the previous block before encrypting. The wikipedia article describes the technical details of the implementing it. For reference the operation for encrypting and decrypting is:

\begin{equation} C_i = E_{K}(P_i \oplus C_{i-1}, C_0 = IV) \\ P_i = D_{K}(C_i)\oplus C_{i-1} , C_0 = IV) \end{equation}

The fact that the decryption procedure relies on XORing the ciphertext (that an attacker can control) is very important! It will come up soon.

This is the first of many chosen plaintext attacks. In fact, I think it is an "adaptive chosen plaintext attack." This is also the first time in the challenges where we need to think about how this would come up in real applications in order to understand why its relevant. Typically servers issue cookies/session tokens that are encrypted strings that define the user's role and access level. If the server uses AES in ECB mode, it may be possible for a malicious attacker to extract the format of the encrypted session token using this attack.

The attack assumes that we have an oracle (the server) that will give us back cipher texts given a plaintext that we choose. The oracle (aka server) appends an unknown string to the attackers chosen text and returns the cipher text of the concatenated plaintext. Our goal is to read the unknown string.

Why does the challenge ask us to discover the block size and mode? If we were really attacking a server we wouldn't know either of them. Knowing how to determine those two facts enable us to test for this attack against servers that we may audit in real situations.

I got stuck on this for a while because I was restricting myself to a chosen plaintext that was 16 bytes long. This is not necessary in order to complete the attack as written, though servers deployed in the real world may have length requirements on the strings that they allow to be processed.

This is a known plaintext attack. In some sense, Challenge 13 is the natural follow up to Challenge 12. If we successfully attacked a server in Challenge 12, we would now know how the encrypted session cookie is formatted. Knowing the fact that in ECB mode, the same ciphertext block decrypts to the same plaintext block can allow us to give ourselves admin access using a carefully crafted session cookie derived from the server. If our plaintext is:

0123456789ABCDEF
----------------
email=fooAA@bar.
com&uid=10&role=
user

If we took the second block, it would decrypt to a block of text with the string "role=" at the end. Now if we could get the server to issue us with a string that decrypted to "admin", then we could concatenate the two cipher texts and have a string that when decrypted gave the "role=admin" pair. This would give us a session token (albeit mangled) which would give us the admin role.

As alluded to earlier, this is the famous CBC bit-flipping attack. It exploits the fact that when we decrypt in CBC, we XOR the preceding cipher text with the plaintext. Bit-flipping attacks are viable whenever we XOR the plaintext with anything in the encryption/decryption process. If we flip a bit in the cipher text block that is being XORed (C[i-1] for P[i]), then we make a one bit edit in P[i] (and ruin C[i-1]). We'll see more bit-flipping attacks soon. The only challenging thing here is figuring out how to get the bit flips to line up and make the edits you want. There's a nice formula for editing bytes which comes up in the CBC padding oracle attack in Set 3:

\begin{equation} b_i = b_i \oplus p_i \oplus p_i' \end{equation}

In this case, we know \(p_i\) (we control that part of the plaintext), \(p_i'\) is the byte that we want to change it to (a disallowed character say) and \(b_i\) is the cipher text byte in the block previous to the plaintext byte we're editing.