CBC Padding Oracle

July 25, 2021

In this post we will investigate the byte-at-a-time ECB decryption exercise from Cryptopals. It’s helpful to read the problem statement before reading this blog post and I highly recommend attempting the previous exercises yourself as they do a great job ramping up your knowledge on the subject.We also have a previous post explaining how CBC works.

This attack relies on a padding oracle, which is something that is able to tell us whether the ciphertext we provide for decryption has a valid padding or not after decryption. In our exercise this will be in the form of a method that returns true or false based on a valid padding or not. Let’s see this in Ruby:

def padding_oracle(ciphertext, key, iv)
  plaintext = aes_cbc_decrypt(ciphertext, key, iv)
  valid_padding?(plaintext)
end

# Based on https://en.wikipedia.org/wiki/Padding_(cryptography)#PKCS#5_and_PKCS#7
def valid_padding?(plaintext)
  padding_size = plaintext.last
  return false unless padding_size > 0 && padding_size < 256

  padding = plaintext.slice(
    -padding_size,
    padding_size
  )

  padding.all? { |b| b == padding_size }
end

To make things more relatable we can think of this padding_oracle as our server validating whether a cookie passed to it is valid or not.

Recap on CBC decryption

CBC Decryption by WhiteTimberwolf

In order to obtain the plaintext block from a ciphertext block the algorithm first decrypts the ciphertext block using ECB with the encryption key (labeled “block cipher decryption” in our image), followed by a XOR with the previous ciphertext block. For the first block we use the inialization vector since we don’t have a previous ciphertext block.

See our previous post for a more in-depth explanation of how CBC works.

We have access to the previous ciphertext block or the initialization vector, but we do not have access to the ECB decryption. Luckily for us this attack allows us to derive the value of the AES decryption (labeled “block cipher decryption” in our image), which makes us able to compute the plaintext out of an encrypted block.

It’s worth reiterating, what this attack allows us to do is:

Derive the value of the AES decryption (labeled “block cipher decryption” in our image).

Exploitation

Even though we don’t control the AES decryption value, we control the value that will be XORed against it. Let’s define this operation:

AES_DEC(ciphertext_block) XOR user_controlled_value

Normally this “user controlled value” would be the previous ciphertext block or the initialization vector (IV), but nothing prevents us from sending whatever we want, right? :) The insight is that:

By making modifications to the previous ciphertext block (or IV for the first block), we can predictably modify the plaintext block.

What we want to achieve with this “user controlled value” is to generate on every iteration a plaintext that has a valid padding. Recall that we are using PKCS7 for this exercise, so a valid padding consists of the last n bytes of our plaintext all having the same value n. So the following endings for our plaintext are all considered valid:

01
02 02
03 03 03
...
16 16 16 .. 16 16

What we need to do is:

Create what we will call a Zeroing IV, which for now is an array containing zeros with the size of a block
- By the end of the algorithm the Zeroing IV will be an array that once XORed with AES_DEC(ciphertext_block) returns zero
Compute an IV that once XORed provides us with a plaintext that has a valid padding of 1
Get the last byte from that IV and XOR it with 1, storing the result in the last byte of our Zeroing IV

Once this is done we will:

Derive a new IV that sets thet final byte to 2 and try to compute the penultimate byte to 2 as well.
Get the penultimate byte from that IV and XOR it with 2 to generate the penultimate byte of the Zeroing IV

Keep doing this until we can find all 16 bytes of a block.

If you are used to the XOR operation you will realize right away that the only way for AES_DEC(ciphertext_block) XOR Zeroing IV to output zero is if they are equal! This means that we have just computed the value of AES_DEC(ciphertext_block), which was the only thing we didn’t know.

To output our plaintext message all we need to do now is perform the operation: Zeroing IV XOR Our original IV.

Visual example

Let’s see an example with the first two iterations of our attack to make things a bit more concrete.

Assume AES_DEC(ciphertext_block) has a value of:
[99, 111, 110, 103, 114, 97, 116, 117, 108, 97, 116, 105, 111, 110, 115, 33]

Our initial Zeroing IV is of course composed of all zeros:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Iteration 1

We want to make the operation AES_DEC(ciphertext_block) XOR Zeroing IV return an array with the final byte set to 1 in order for our padding_oracle method to return true. To achieve that we first need to find a value that makes 33 XOR <something> = 1:

33 XOR 0 = 33 is a valid padding? NO
33 XOR 1 = 32 is a valid padding? NO
33 XOR 2 = 35 is a valid padding? NO
..
33 XOR 32 = 1 is a valid padding? YES

So right now our Zeroing IV is:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32]

This means that AES_DEC(ciphertext_block) XOR Zeroing IV will output something like:
[99, 111, 110, 103, 114, 97, 116, 117, 108, 97, 116, 105, 111, 110, 115, 1]

This is indeed a block with a valid padding!

Time to XOR this last value with 1 so we can get our true zero value.
32 XOR 1 = 33

So right now our Zeroing IV is:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33]

Notice how 33 is the same value of our imaginary AES_DEC(ciphertext_block) last byte!

Iteration 2

Now we need to make the operation AES_DEC(ciphertext_block) XOR Zeroing IV return an array with the final and penultimate bytes set to 2 in order for our padding_oracle method to return true. In order to do that we need to:

Make 33 XOR <something> = 2
Make 115 XOR <something> = 2

Since we already know due to our first iteration that AES_DEC(ciphertext_block) last byte is 33 we can just compute 33 ^ 2 which is equal 35

Now we need to make 115 XOR something = 2, so let’s find the appropriate byte:

115 XOR 0 = 115 is a valid padding? NO
115 XOR 1 = 114 is a valid padding? NO
115 XOR 2 = 113 is a valid padding? NO
..
115 XOR 113 = 2 is a valid padding? YES

So right now our NEW Zeroing IV is:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 113, 35]

This means that AES_DEC(ciphertext_block) XOR NEW Zeroing IV will output something like:
[99, 111, 110, 103, 114, 97, 116, 117, 108, 97, 116, 105, 111, 110, 2, 2]

Which is again a block with a valid padding!

Time to XOR this penultimate value with 2 so we can get our true zero value.
113 XOR 2 = 115

So right now our “final” Zeroing IV is:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 33]

Notice how 115 is the same value of our imaginary AES_DEC(ciphertext_block) penultimate byte!

The next iteration will make the last three bytes equal to 3 and we are going to find yet another byte, and so on and so forth until we decrypt an entire block, so eventually our Zeroing IV will become the same as our AES_DEC(ciphertext_block):

[99, 111, 110, 103, 114, 97, 116, 117, 108, 97, 116, 105, 111, 110, 115, 33]

Implementation

This is one of those algorithms that are harder to explain than to implement, so let’s attempt to do it.

require 'openssl'

KEY = 16.times.map { rand(0..255) }
IV = 16.times.map { rand(0..255) }
BLOCK_SIZE = 16
BYTE_RANGE =0..256

# Don't look! ;)
PLAINTEXT = [99, 111, 110, 103, 114, 97, 116, 117, 108, 97, 116, 105, 111, 110, 115, 33, 32, 119, 101, 32, 100, 105, 100, 32, 105, 116, 33]

# See our previous post on CBC Bitflipping Attacks to understand CBC better
def aes_cbc_encrypt(plaintext)
  cipher = OpenSSL::Cipher::AES.new(128, :CBC)
  cipher.encrypt
  cipher.key = KEY.pack('C*')
  cipher.iv = IV.pack('C*')
  cipher.padding = 0
  cipher.update(plaintext.pack('C*')) + cipher.final
end

def aes_cbc_decrypt(ciphertext, iv)
  cipher = OpenSSL::Cipher::AES.new(128, :CBC)
  cipher.decrypt
  cipher.key = KEY.pack('C*')
  cipher.iv = iv.pack('C*')
  cipher.padding = 0
  cipher.update(ciphertext.pack('C*')) + cipher.final
end

# See https://tools.ietf.org/html/rfc2315#section-10.3
def pkcs7_pad(bytes, block_size)
  raise 'Invalid block size' if block_size >= 256
  padding_len = block_size - (bytes.size % block_size)
  padding = Array.new(padding_len, padding_len)
  bytes + padding
end

#############################################################
# Our boilerplate is done, time to implement our algorithm! #
#############################################################

def encrypt_credentials
  padded_buffer = pkcs7_pad(PLAINTEXT, BLOCK_SIZE)
  ciphertext = aes_cbc_encrypt(padded_buffer).unpack('C*')

  [IV, ciphertext]
end

def padding_oracle(ciphertext, iv)
  plaintext = aes_cbc_decrypt(ciphertext, iv).unpack('C*')
  valid_padding?(plaintext)
end

# Based on https://en.wikipedia.org/wiki/Padding_(cryptography)#PKCS#5_and_PKCS#7
def valid_padding?(plaintext)
  padding_size = plaintext.last
  return false unless padding_size > 0 && padding_size <= BLOCK_SIZE

  padding = plaintext.slice(
    -padding_size,
    padding_size
  )

  padding.all? { |b| b == padding_size }
end

def decrypt_byte(block, zero_iv, known)
  iv = Array.new(BLOCK_SIZE, 0)
  padding_size = known + 1
  next_byte_pos = BLOCK_SIZE - known - 1

  (1..known).each do |index|
    iv[-index] = zero_iv[-index] ^ padding_size
  end

  BYTE_RANGE.each do |candidate|
    iv[next_byte_pos] = candidate
    return candidate if padding_oracle(block, iv)
  end

  raise 'Candidate not found'
end

def decrypt_block(block, previous_block)
  zero_iv = Array.new(BLOCK_SIZE, 0)

  BLOCK_SIZE.times.each do |known|
    byte = decrypt_byte(block, zero_iv, known)
    zero_iv[BLOCK_SIZE - known - 1] = byte ^ (known + 1)
  end

  zero_iv.zip(previous_block).map { |a, b| a ^ b }
end

def decrypt(ciphertext, iv)
  blocks_amount = ciphertext.size / BLOCK_SIZE
  previous_block = iv

  (0...blocks_amount).flat_map do |block_index|
    block = ciphertext.slice(
      block_index * BLOCK_SIZE,
      BLOCK_SIZE
    )

    decrypted_block = decrypt_block(block, previous_block)
    previous_block = block

    decrypted_block
  end
end

iv, ciphertext = encrypt_credentials
puts decrypt(ciphertext, iv).pack('C*')

If we run the program above we will receive our plaintext as the output, how cool is that?! This is probably one of the problems that I have the most fun with since it uses most of the knowledge we have built upon previous exercises.

If you made it this far, congratulations! We are almost done with CBC attacks (I promise!), and we will start investigating CTR mode. As always, if anything is confusing or could be improved please reach out to me on Twitter or by email and I will be happy to chat about it!