CBC bitflip
2021-12-30


Advanced Encryption Standard (AES) is a well-known encryption standard and a common name for the symmetric block cipher called Rijndael - originally named after the surnames of researchers who proposed it: Joan Daemen and Vincent Rijmen.

The core encryption algorithm can be applied to blocks of 128 bits with a key of 128, 192, 256 bits. Besides the core encryption algorithm there are multiple modes of operation, which define how to apply the algorithm to multiple blocks. Let's have a quick look at two very basic ones.

Electronic Code Book (ECB) mode is the simplest. Plaintext is split into blocks and each one of them is encrypted in the same way. "ECB Penguin" image shows very well why this is not ideal. Two blocks of plaintext that are the same will give the same output. If we can control some part of the input and we can see the encryption output, we can recover parts of the plaintext without knowing the key. By carefully aligning blocks we can guess and match the encrypted part character by character.

Cipher Block Chaining (CBC) mode is only slightly more complicated. In this mode each block of plaintext is XOR-ed with previous ciphertext before encryption. IV is the initialization vector. The scheme looks something like this:
<pre>
(P_1 ^ IV)  ---[block encryption]---> C_1
(P_2 ^ C_1) ---[block encryption]---> C_2
(P_3 ^ C_2) ---[block encryption]---> C_3
...
(P_n ^ C_(n-1)) ---[block encryption]---> C_n
</pre>

This has an interesting property. Again, if we control some part of the input and we can see the encryption output, we can manipulate the decryption output by modifying the ciphertext without knowing the key.

Let M be the malicious input.
<pre>
encryption:
(P_1 ^ IV)  ---[block encryption]---> C_1
(P_2 ^ C_1) ---[block encryption]---> C_2
(P_3 ^ C_2) ---[block encryption]---> C_3
(P_4 ^ C_3) ---[block encryption]---> C_4

modification:
C_2 ^ M = C_M

ciphertext:
[C_1, C_M, C_3, C_4]

decryption:
C_1 ---[block decryption]---> (P_1 ^ IV) ---[^ IV]---> P_1
C_M ---[block decryption]---> (block of random bullshit)
C_3 ---[block decryption]---> (P_3 ^ C_2) ---[^ C_M]--->
 (P_3 ^ C_2 ^ C_M) = (P_3 ^ C_2 ^ (C_2 ^ M)) = P_3 ^ M = P_M
C_4 ---[block decryption]---> (P_4 ^ C_3) ---[^ C_3]---> P_4
</pre>

We have modified some block of plaintext.
If we can also control the IV we can fix up the blocks we've broken on the way. Oftentimes we don't care though. You may hit some unfortunate bytes once the block of garbage decrypts, but sometimes it's enough to resolve it by messing with the block some more instead of fixing up the decryption output all the way.
This attack is pretty simple in principle, the harder part is to find where exactly to apply it.

I'll just hint that there are more attacks on this mode of operation.
An interesting example is a padding oracle attack, but that's a topic for another post.