Cryptanalysis of AES-CBC (Part-1)

7 min readDec 2, 2020

This is the continuation of my cryptanalysis series.In this post we are going to look into one of the most elegant attacks on AES-CBC mode.The attack is called ”Padding oracle attack” and as the name suggests it involves the manipulation of the padding oracle to retrieve the plaintext.Now, atleast a few of you would be wondering what a padding oracle is so let us first have a look at what it is.

Padding Oracle:

Most of you would have heard about the “oracle of Delphi”(I am a huge fan of Percy Jackson). So here,our padding oracle is somewhat similar to the oracle of Delphi but instead of giving out prophecies it checks whether the plaintext corresponding to a given ciphertext is properly padded.For those who have no clear idea about padding please take a look at my earlier blog post Cryptanalysis of AES-ECB (Part-1) where I have given sufficient explanation on the same.

Now on a closer look, what the oracle does is it first decrypts the ciphertext(which of course we have no access to) and then validates the padding .i.e, it checks the final character of the plaintext and makes sure the last n characters are same as the final character(here n is the numeric equivalent of the last character also denoted by ord(last character)). And if the padding is valid it returns True else False.Below I have given an implementation of the same.

Setup:

For the ease of explanation I have made a setup similar to a CTF challenge.Which is as follows:

Here we have defined various functions for padding, unpadding, encrypting, decrypting, padding validation etc.Note that in line number 29, we have encrypted our flag and written the ciphertext in ciphertext.txt .Check the content of ciphertext.txt below:

Now it must be clear to you that our aim is to decrypt this gibberish text to retrieve our flag.

On taking a closer look at the encrypt function,we can see that it returns the ciphertext after appending it to the IV which explains the initial “YELLOW SUBMARINE” part in the ciphertext.

Now moving on to line number 33, we see that the program is taking a ciphertext from us and validating the padding of its corresponding plaintext.This little part turns out to be the Achilles’ heal in this otherwise secure oracle as you will see later.

Suppose we send in the ciphertext at hand, it will return true since the oracle has taken care of the padding before encrypting.

NOTE: Here we have excluded the trailing newline character.

Now take a look on what happens if we change the last byte to something else

Hope you have picked up everything till now if not take a few more minutes to read through the above content again(It is perfectly fine if you don’t catch it in the first try!!).Now let us move on and see how we can exploit this one bit of information(True is 1 and False is 0 thus what we get is a one bit info) to decrypt the entire ciphertext.

Exploiting

(WARNING:Writing down and keeping track of the variables is highly recommended we have plenty of them)

Here we have 2 blocks of ciphertext(excluding the IV) thus 2 blocks of plaintext.First we will look into decrypting the second block and after that decrypting the first block will be a cake walk.

Note that our ciphertext= IV(length 16) +encrypted text(2 blocks of length 16 each)

let C1=ciphertext[16:32] and C2=ciphertext[32:48]

We also take a string of null bytes whose length is equal to 16,

C_prime=(“\x00”*16).encode()

Now we concat the two strings C_prime and C2 , thus we get a resultant string with initial 16 bytes null and the next 16 bytes corresponding to C2 let us term it as C_prime_C2 .

Next, let us take a look on how AES-CBC decryption works,

In our scenario, if we try to decrypt C_prime_C2 , the first block of ciphertext will be C_prime and the second block will be C2. Let p_prime be the resulting plaintext.Here,we can form a relation between the first block of ciphertext, second block of ciphertext and the second block of plaintext. Examining the above image will make it evident,

ciphertext[1] xor decryption(ciphertext[2])=plaintext[2]

On replacing ciphertext[1] with C_prime ,ciphertext[2] with C2 and plaintext[2] with p_prime2, we get:

C_prime xor D(C2)=p_prime2 — — — — — — ->eqn 1

Now if we look at how C2 is formed, we see:

C2=E(p2 xor C1) — — — — — — — — — — ->eqn 2

NOTE: p2 is the second block of the original plaintext.

Refer the following diagram to get clarity on that matter.

Combining both eqn 1 and eqn 2 we get,

C_prime xor D(E(p2 xor C1))=p_prime2

Since decryption and encryption are opposite operations, they cancel out leaving behind,

C_prime xor p2 xor C1=p_prime2

Or,

p2 =p_prime2 xor C_prime xor C1

Let us now concentrate on our eqn 1,

C_prime xor D(C2)=p_prime2

Suppose, we change the last byte of C_prime , this will effect the last byte of p_prime2.Now keep changing this last byte until we get a True value when C_prime_C2 is passed to the oracle.

Now the question arises when does the oracle return True ? The answer is simple when the last byte becomes “\x01” which implies the padding is just 1 byte.

So when we get a True value, we can confirm the last byte of p_prime2 is “\x01”

Thus in the equation p2 =p_prime2 xor C_prime xor C1,we posses values of the last byte of three variables p_prime2 ,C_prime ,C1. (C1 is already known from the ciphertext, C_prime is controlled by us and p_prime we now know is “\x01”)

Thus we can calculate,

p2[-1] =p_prime2[-1] xor C_prime[-1] xor C1[-1]

In our example it will be ‘\x0c’

Note: -1 is used to indicate the last byte.

Awesome we’ve now figured out the last byte of the second block of plaintext not a bad start but we’ve got no time to rest the remaining bytes are waiting for us!

To find the second last character, we brute force the second last byte of C_prime so that on decryption we get the padding as ”\x02\x02". After that we can just use the formula used above to find the second last character.

p2[-2] =p_prime2[-2] xor C_prime[-2] xor C1[-2]

But you might have noticed ,to get a padding of ”\x02\x02" it is not enough to change the second last character,we must also change last character so that the decryption yields “\x02” in the last position.This is quite easy since we already know that the last byte of the original plaintext is “\x0c”.

We have,

p2[-1] =p_prime2[-1] xor C_prime[-1] xor C1[-1]

thus,

C_prime[-1]=p2[-1] xor p_prime2[-1] xor C1[-1]

This process is repeated until we recover the entire second block of plaintext.Just change the corresponding byte of C_prime to get a valid padding and then substitute in the above formula.

We have the first block of plaintext yet to be found but don’t worry it is just the repetition of the same process with the changes listed below:

C1=ciphertext[:16]
C2=ciphertext[16:32]

Try decrypting the entire plaintext on your own.Good luck :)

I am posting a picture of my entire exploit in case you have any doubts.Hope it comes to your aid.Here N is the number of blocks in ciphertext.