**Cryptanalysis of AES-CBC (Part-1)**

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**=**ciphertex**t[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.

**NOTE:To understand the code more easily just give the blocknumbers 1 and 2 separately instead of the loop iterator k.**

If any doubt persists please feel free to contact me at:

**sarangdileep2771@gmail.com**

Thank you for reading this far.Stay tuned for the next blog post !!