/ GENERAL , CS4236 , CRYPTOGRAPHY

The Padding Oracle Attack

Implementing the padding oracle attack was one of the assignments I got for the module CS4236: Cryptography Theory and Practice. Needless to say, it took me quite a while to get the idea and to implement it. I am writing this blog post for anyone who needs and prefers an easier explanation (and also for myself, in case I forget how this attack works).

The padding oracle attack is performed by manipulating the padding (see below) of a message. It is mostly associated with CBC mode of decryption which is used for block ciphers.

Encryption

CBC Encryption

Image Credits: Wikipedia - CBC

In CBC, every current block of plaintext is firstly XORed with the previous block of ciphertext (or in the case of the first plaintext block, it will be the Initialisation Vector (IV)). Every ciphertext block is therefore in a way, an IV to the next encryption round.

Following the XOR, we obtain an intermediate product. This product is now encrypted with the use of a secret key to obtain the first block of the cipher text. We then repeat this for every plaintext block we have. The key used to encrypt each block remains the same.

Since each cipher text is dependent on the previous cipher text block for encryption for the IV, we have do this process in a sequential manner (i.e.: we cannot parallelise this process).

Padding

The plaintext is broken up into blocks of a predefined size, more commonly 8 bytes or 16 bytes, before we encrypt them (remember that CBC mode is for block ciphers - we encrypt the message in terms of blocks).

Plaintext blocks will not always take up the entire space of the last block. One of the common methods for padding is PKCS#7 which is explained here.

Let’s assume the block size is 8. Hence, each plaintext block has to be of 8 bytes. In the event that the block only has 5 bytes, we simply append 0x030303. 0x is used to indicate that it is a hexadecimal representation. This tells us that there are 3 bytes of 03 when we try to decrypt later.

If a block is full, we still need to add another block full of 0x0808080808080808 to show that that block is complete. This is necessary so the decryption algorithm can determine with certainty whether the last byte of the last block is a pad byte indicating the number of padding bytes added or part of the plaintext message.

Hence, if L = length of the block, then the number of bytes we need to append to the message (b) has to be 1 <= b <= L. Note that b cannot be 0. The receiver should not have any ambiguity on the original message. Hence, if the message’s length is multiple of L, we add one more block of L bytes.

To fill a block with b “spaces” left, we append b (1 byte), b times.

Reference: Wikipedia - PKCS7

Decryption

CBC - Decryption

Image Credits: Wikipedia

Decryption is the inverse of the encryption process. For each cipher text, we first decrypt it with the secret key followed by XORing it with the previous block of cipher text.

Since we already have all the cipher text blocks and the decryption of the current cipher text only requires the involvement of the previous cipher text block, we can parallelise the entire decryption process.

Decryption Process

We can gather information about the encoded data (plaintext) with the use of the final byte. If the final byte of the encoded data has value b,

  • if b=0 or b>L, return error
  • if final b bytes of encoded data are not all equal to b, return error
  • else, we remove the final b bytes and just output the remaining portion as the message

The Attack

Manipulating the bytes

Assume that that the attacker has hold of c[0], c[1] and c[2] which are all the blocks making up the cipher text and that we want to find m[1], which is the 2nd block in the plaintext.

We now have a general case (i.e. this attack is going to work for any 2 cipher text blocks we have - or the first ciphertext block and the IV) where we have 2 cipher text blocks. We can think of c[0] as the IV for the decryption of c[1]. Let’s say I have a guess for the last byte of m[1], denoted by g. I already have c[0]. Now, instead of sending in the actual c[0], I am going to send in a modified c[0], which we denote as c’[0].

In c’[0], we modify the last byte to be as such:

last_byte_of_c’[0] = current_last_byte_of_c[0] ^ g ^ 0x01 where ^ represents XOR. We send in c’[0] as the IV and c[1] and the cipher text block to the padding oracle. 0x01 is the hexadecimal representation of 1, which is the padding we want to “introduce” into the plaintext block.

Realise that now, because of the modification, the last byte of the plaintext in m[1] will also be XORed with g and 0x01.

new_last_byte_of_m[1] = actual_last_byte_of_m[1] ^ g ^ 0x01. Now, we have the attack working. Realise that if g == actual last byte of m[1], they both cancel each other out and leave 0x01 to be the last byte of m[1]. Note that our manipulation is solely on the block which we are using as the IV, which in this case is c[0].

This is a valid padding because we have forcefully created an “empty” space in the block and manipulated the last byte to be 0x01 to reflect that gap. In the process, our guess reveals the actual plaintext byte since the guess and the actual plaintext byte are XORed and cancelled out only when they are equal.

We can similarly repeat the same for the 2nd last byte to create a modified IV, c’[0]. So the next padding we are going to manipulate and create in the block is 0x02. Since we already know the last byte of m[1], we will manipulate such that we pass in the last byte as:

new_last_byte_of_c’[0] = previously_found_last_byte_of_the_plaintext ^ 0x02

Since the last byte of the plaintext is present here, it cancels off with the plaintext byte during the XOR process and leaves 0x02 in the last byte of the plaintext.

The 2nd-last byte of the IV will be sent as follows:

modified_2nd_last_byte_of_c’[0] = 2nd_last_byte_of_c[0] ^ g ^ 0x02. We manipulate the guess, g, till the padding oracle returns with a success message.

Repeating the same for every other byte will soon yield all the plaintext bytes in m[1] and we will have successfully recovered that specific block.

To decode the entire plaintext, we simply repeat the process for every block, taking it as the cipher text and taking the previous cipher text block as the IV to be passed into the padding oracle.

Corner Case

There is one small corner case which might need to take into account. What happens if the current guess (g) is equivalent to the pad byte we are trying to induce? If both of them are equal (assume both are 0x01), then when we attempt to do this:

last_byte_of_c’[0] = current_last_byte_of_c[0] ^ g ^ 0x01,

it fails because g and 0x01 will be cancelled out leaving c[0] intact. This will lead to the correct last byte in the plaintext block and the oracle returns us a “Success” status for the padding. Our attempt to create the pad in the plaintext block has thus failed.

Hence, only for the case of the last byte, we keep searching for another byte which yields a success scenario. If we are able to find another byte, we take that as the correct byte for the plaintext. Else, if no other byte was found, it could have been the case where all the 3: the message byte, the guess and the pad were all 0x01 and the XOR operation would still have given us 0x01 in the plaintext which is a valid padding. Hence, we take 0x01 to be valid byte if no other byte was found.

This only occurs for the last byte. If it was any other byte, the byte next to it would have a padding (e.g.: 0x02) and if the current byte does not hold 0x02 as well, the padding check will fail.