Today, we will learn about the CBC block cipher mode, how it works, and the bitflipping attack. This post is related to https://cryptopals.com/sets/2/challenges/16.

CBC block cipher mode

Cipher Block Chaining (CBC) is a block cipher mode of operation. Data is encrypted in blocks of fixed size and with the same key. Also, some bytes are added when the plaintext doesn’t have a length that is a multiple of the block size, known as padding.

Let p be the plaintext, c the ciphertext, k the key, IV the initialization vector (later explained), ^ the XOR operation, E any encryption algorithm and D its decryption counterpart. Assume that the ciphertext can be divided into blocks of length equal to l, without any leftover bytes. For the first block, the encrypted version is computed as c[0] = E(IV ^ p[0], k). For all the other blocks, we have that c[i] = E(p[i] ^ c[i - 1], k). From these equations, we can derive the decryption. We have that p[i] = D(c[i], k) ^ c[i - 1] and p[0] = D(c[0], k) ^ IV.

The IV is a unique, non-repeating, random binary sequence that we use to randomize the encryption. As opposed to ECB, identical plain blocks won’t result in identical encrypted blocks. Furthermore, the same message will return different encrypted messages.

It still has some issues. Encryption can’t be parallelized, even though decryption can be, and it’s vulnerable to attacks.

CBC bitflipping attack

Setup

For this exercise, we assume that we have access to two functions.

The first function takes some userdata as input and builds the following string comment1=cooking%20MCs;userdata={};comment2=%20like%20a%20pound%20of%20bacon. It then encodes and encrypts the data.

pub fn encrypt_user_data(data: &str) -> Vec<u8> {
    let data = format!(
        "comment1=cooking%20MCs;userdata={};comment2=%20like%20a%20pound%20of%20bacon",
        data
    );
    let url_encoded_data = data
        .replace('=', "%3D")
        .replace(';', "%3B")
        .replace(' ', "%20");

    encrypt_aes_128_cbc(url_encoded_data.as_bytes(), &KEY, Some(IV.to_vec()))
}

The second function decrypts the data and checks if the user is admin. However, the data is not decoded. That means that = won’t appear. Therefore, it’s impossible to get admin=true by inputting the data into the first function. We need to break the cryptography.

pub fn is_admin(data: &[u8]) -> bool {
    let plain = decrypt_aes_128_cbc(data, &KEY, Some(IV.to_vec()));
    plain.contains(";admin=true;")
}

Attack

The goal of the exercise is to get the is_admin function to return true.

Get block size

As in a previous ECB blog, we need to detect the block size.

let encrypt_fn = |data: &[u8]| encrypt_user_data(&String::from_utf8_lossy(data));
let (block_size, _) = compute_block_size_and_padding_length(encrypt_fn);

Craft the input to the oracle

We need to compute the prefix length, including the blocks it takes, and how many bytes of the last prefix block are dedicated to the prefix.

let full_prefix_length = prefix_length(encrypt_fn, block_size);
let block_prefix_length = block_size - (full_prefix_length % block_size);

Now, we can craft the input. The trick here is to make sure that our ;admin=true; string ends up all together on one block. Not spilled over two different blocks. With the prefix length, we can make sure that happens. One last detail, ; and = are encoded. On decryption, they won’t be decoded. We are going to use some placeholder characters instead. In this case, X for ; and Y for =. We will see why in the next section.

let mut crafted_input = vec!["a"; block_prefix_length].join("");
crafted_input.push_str("XadminYtrueX");

Flip ciphertext bits

We send the crafted input to the oracle, we get the ciphertext, and it’s time to get into the offense!

In CBC, encrypting a block requires doing XOR between the previous encrypted block and the current plaintext block. Any bit we modify in the ciphertext will modify the final value that gets decrypted because of the XOR operation. We can take advantage of that.

Imagine we have the two following plaintext blocks (I’m using shorter block size to simplify things):

|            p1           |            p2           |
| 00 01 02 03 04 05 06 07 | 08 09 10 11 12 13 14 15 |
| a  a  a  a  a  a  a  a  | a  a  a  a  a  a  a  X  |

Where X is the value we want to modify. We want to get ;. And the final encrypted form is:

|            c1           |            c2           |
| 00 01 02 03 04 05 06 07 | 08 09 10 11 12 13 14 15 |
| b  b  b  b  b  b  b  b  | b  b  b  b  b  b  b  Z  |

Assume the decrypted value of Z is Y. Thus, Y is the result of X ^ b.

We know that on decryption, c2 will be decrypted then XORed with c1. The idea then, is to modify the last byte of c1 in such a way that when XORing, X will turn into ;. In that case, we can do c1[7] = b ^ X ^ ;. That way, during decryption, when it XORs D(c2) with c1, the following operation is performed
Y ^ c1[7] = Y ^ (b ^ X ^ ;) = (X ^ b) ^ (b ^ X ^ ;) = ;.

That’s the attack. That’s all we are doing. We take the byte from the previous block at the same position as the byte that we want to attack, and XOR it with both the plaintext character and the character we want to obtain.

In this case, we applied that theory to the three characters we wanted to modify.

let ciphertext = encrypt_user_data(&crafted_input);

let mut crafted_ciphertext = ciphertext;
crafted_ciphertext[2 * block_size] ^= b';' ^ b'X';
crafted_ciphertext[2 * block_size + 6] ^= b'=' ^ b'Y';
crafted_ciphertext[2 * block_size + 11] ^= b';' ^ b'X';

With that, we accomplished the task.

Code

You can check the whole implementation https://github.com/danielorihuela/cryptopals/blob/main/src/set2/challenge16.rs.

Conclusion

The CBC cipher is simple but insecure. It’s an improvement over ECB. It doesn’t leak patterns. However, it’s still vulnerable to attacks.

Cryptopals: CBC bitflipping attack