CBC bit-flipping attack

July 18, 2021

This post is based on the CBC bit-flipping attack exercise from Cryptopals. I highly recommend attempting the previous exercises yourself as they do a great job ramping up your knowledge on the subject.

Before we can start tackling this problem it’s worth revisiting how cipher block chaining (CBC) works as we will need to know the algorithm in order to perform the bit-flipping attack.

CBC Encryption

In a nutshell CBC encryption works in the following order:

Split the plaintext into blocks of 16 bytes (this number can change, but the next steps are the same)
For each plaintext block:
- XOR the block with its previous ciphertext block
- Encrypt the result with AES to produce the ciphertext. This ciphertext will be XORed with the next plaintext block.

Since we always use the previous ciphertext to generate a block, how do we generate the first block?

For the first block we use something called an Initialization Vector (IV), which is nothing more than a random array of bytes that has the same length as our block.

Details

For CBC to work the plaintext must be a multiple of the block size, so we usually use a padding algorithm like PKCS7 to pad our plaintext.

Let’s see the visual representation of the algorithm:

CBC Encryption by WhiteTimberwolf

CBC Decryption

The decryption process consists of us doing the inverse of what we did for the encryption process, so:

Split the full ciphertext into blocks of 16 bytes
For each ciphertext block:
- Decrypt the block with AES
- XOR the decrypted block with the previous ciphertext block.

In order to decrypt our first block we need to rely yet again on our initialization vector (IV).

Let’s see the visual representation of the algorithm:

CBC Decryption by WhiteTimberwolf

CBC Ruby Implementation

def xor_bytes(bytes1, bytes2)
  if bytes1.size != bytes2.size
    raise 'Array of bytes should have same length'
  end

  bytes1.zip(bytes2).map { |a, b| a ^ b }
end

def aes_cbc_encrypt(plaintext, key, iv)
  blocks = plaintext.each_slice(key.size)
  previous_ciphertext_block = iv

  blocks.flat_map do |block|
    previous_ciphertext_block = aes_ecb_encrypt(
      xor_bytes(previous_ciphertext_block, block),
      key
    )

    previous_ciphertext_block
  end
end

  def aes_cbc_decrypt(ciphertext, key, iv)
  blocks = ciphertext.each_slice(key.size)
  previous_ciphertext = iv

  blocks.flat_map do |block|
    decrypted = xor_bytes(
      aes_ecb_decrypt(block, key),
      previous_ciphertext
    )

    previous_ciphertext = block
    decrypted
  end
end

See ECB decryption post for the implementation of the aes_ecb_encrypt and aes_ecb_decrypt_methods methods.

Bitflipping Attack

Now that we understand how CBC works we can talk about this particular attack which relies on the fact that in CBC mode, a 1-bit error in a ciphertext block:

Completely scrambles the block the error occurs in
Produces the identical 1-bit error in the next ciphertext block.

The first point is the easier one to reason about. Since we have encrypted our block with ECB, messing up with the ciphertext bits will in fact change the contents of our plaintext once it is decrypted by ECB in a random manner.

The second point requires more attention though and for it to make sense I feel it is helpful to reach out for an example.

Our goal with the following exercise is to transform our input

From: name=cbc attack;admin<true:id=11
To: name=cbc attack;admin=true;id=11

A few important things to note:

Our plaintext is already block aligned since the block size for this exercise is 16 bytes and our plaintext has 32 bytes.

First block: name=cbc attack;
Second block: admin<true:id=11

Transforming admin<true:id=11 into admin=true;id=11 will require us to transform:

< (ASCII 60) into = (ASCII 61)
: (ASCII 58) into ; (ASCII 59)

Let’s lay the ground for our problem in Ruby:

BLOCK_SIZE = 16
KEY = BLOCK_SIZE.times.map { rand(0..255) }
IV = BLOCK_SIZE.times.map { rand(0..255) }
PLAINTEXT = 'name=cbc attack;admin<true:id=11'.bytes

# Our encryption method defined earlier in this post
ciphertext = aes_cbc_encrypt(PLAINTEXT, KEY, IV)

ciphertext.each_slice(BLOCK_SIZE) do |block|
  puts block.inspect
end

This program outputs the following:

First block:
[135, 247, 220, 139, 108, 224, 161, 24, 21, 43, 213, 93, 49, 101, 91, 55]

Second block:
[161, 167, 98, 71, 30, 176, 244, 73, 72, 228, 148, 176, 198, 21, 39, 68]

Here’s what we want to prove again:

A 1-bit error in a ciphertext block:

Completely scrambles the block the error occurs in

Produces the identical 1-bit error in the next ciphertext block.

Let’s recap what we need to do in order to decrypt blocks using CBC:

Decrypt the current ciphertext block with AES-ECB

XOR that decrypted_value with the previous ciphertext block

With that in mind let’s reverse engineer what we need to do to achieve our goal:

First we have to figure out the value of the ECB decryption for the bytes we are interested in:

ecb_decryption(176) XOR 224 = 60
ecb_decryption(148) XOR 213 = 58

Let’s dive into what these numbers represent.

What are these numbers?

176 is the value of the 6th byte (<) in our second block and 224 is the 6th byte of our first block, while 60 represents the < character in ASCII.
148 is the value of the 11th byte (:) in our second block and 213 is the 11th byte of our first block, while 58 represents the : character in ASCII.

Let’s compute our XOR equation for our first point:

=> ecb_decryption(176) XOR 224 = 60
=> ecb_decryption(176) = 60 XOR 224
=> ecb_decryption(176) = 220

Now we need to convert our < into an =, which is represented as 61 in ASCII:
220 XOR 61 = ?
225

Going to our second point:

=> ecb_decryption(148) XOR 213 = 58
=> ecb_decryption(148) = 58 XOR 213
=> ecb_decryption(148) = 239

Now we need to convert our : into an ;, which is represented as 59 in ASCII:
239 XOR 59 = ?
212

So the changes in our first block needs to be:

6th byte goes from 224 to 225
11th byte goes from 213 to 212

And if we look closely that’s exactly a 1-bit XOR!

=> 224 XOR 1 = 225
=> 213 XOR 1 = 212

We are ready for our full code:

BLOCK_SIZE = 16
KEY = BLOCK_SIZE.times.map { rand(0..255) }
IV = BLOCK_SIZE.times.map { rand(0..255) }
PLAINTEXT = 'name=cbc attack;admin<true:id=11'.bytes

ciphertext = aes_cbc_encrypt(PLAINTEXT, KEY, IV)
ciphertext[5] ^= 1  # 6th byte of our first block
ciphertext[10] ^= 1 # 11th byte of our first block

puts aes_cbc_decrypt(ciphertext, KEY, IV).pack('C*')

And the output of this is: �;5��H��G�\Ladmin=true;id=11

Which is exactly what we expected. The first block became scrambled while the second one carried the changes we were looking for!

And we have reached the end of our exercise! Congratulations, take a moment to be proud of what you have achieved and I hope you are looking forward to the next posts as much as I am. :)