Padding oracle

Padding Oracle Attack is a type of side-channel attack where an attacker can exploit the error messages generated by a system that has padding validation to recover the plaintext of an encrypted message.

How Padding Oracle Attack works in AES CBC mode?

In AES CBC mode, the plaintext is divided into blocks and XORed with the previous ciphertext block before encryption. Padding is added to the last block to make it the same size as the block size.

To recover the plaintext of the block n the following operation is done :

plaintext_n = uncrypt(ciphertext_n) ⊕ ciphertext_n-1

From cipher to xor

Taking an example with a ciphertext composed by 2 blocks, the 2 plaintext blocks are noted P1 and P2 and the ciphertext are C1 and C2. Then we have :

+----+----+                +----+----+
| P1 | P2 | -- encrypt --> | C1 | C2 | 
+----+----+                +----+----+

What happens if the user replace the block C1 by an arbitrary one noted X ?

+---+----+                +-----+-----+
| X | C2 | -- encrypt --> | P'1 | P'2 | 
+---+----+                +-----+-----+

We can write the plaintext as the following equation :

P'2 = uncrypt(C2) ⊕ X

C2 = encrypt(P2 ⊕ C1)

P'2 = uncrypt(encrypt(P2 ⊕ C4)) ⊕ X
# As encrypt is the inverse of uncrypt, uncrypt(encrypt(1)) = 1
P'2 = P2 ⊕ C1 ⊕ X
P2 = P'2 ⊕ C1 ⊕ X

And here we have an equation with two known elements and two unknown :

Known :

• X : The arbitrary "cipher" block

• C1 : The first cipher block

Unknown

• P2 : The last plaintext block, the target

• P'2 : The new plaintext block formed by the equation noted before.

Here the equation do not contains cryptographic elements anymore, just xoring operation remains.

Oracle

The padding is validated by the system after decryption. If the padding is incorrect, the system generates an error message indicating that the padding is invalid. This error message can then be used by an attacker to recover the plaintext of the encrypted message.

The attacker sends a modified ciphertext to the system and observes the error message generated by the system.

The attacker can then use this error message to determine the padding of the ciphertext and then modify the ciphertext accordingly. This process is repeated until the entire plaintext is recovered.

Remember that XOR operation is done byte by byte. It means that an attacker can control exactly which bit is modified within the plaintext.

P2[0] = P'2[0] ⊕ C1[0] ⊕ X[0]
P2[1] = P'2[1] ⊕ C1[1] ⊕ X[1]
...
P2[14] = P'2[14] ⊕ C1[14] ⊕ X[14]
P2[15] = P'2[15] ⊕ C1[15] ⊕ X[15]

As padding would be valid, it's mean that the plaintext ending by 0x01 or 0x02 0x02 etc. As X is controled we can bruteforce the last byte untill the decryption operation return a valid plaintext instead of a padding error message.

At this moment its mean that P'2 end by a valid padding ( 0x01 ) so for the equation ...

P2[15] = P'2[15] ⊕ C1[15] ⊕ X[15]

... only P2[15] remain unknown, so it can be calculated using the 3 others elements.

This page don't take care about false positive. Indeed, there is a (low) chance that the plaintext ends with padding, but these cases are rare.

To retrieve the previous byte ( P2[14]) there is just need to choose X[15] in order to have P'2[15] = 0x2 and bruteforce the X[14] value untill the padding is valid. When there is no padding error message, then X[14] provide a valid padding, that mean P'2[14] = 0x2 et so the equality can be solve

P2[14] = P'2[14] ⊕ C1[14] ⊕ X[14]

This reasoning is to be done in a loop until all the values ​​of the plaintext of the block are found.

However, a problem arises when trying to find block P1.

Indeed, we relied on the knowledge of the encrypted block that preceded the block being decrypted. However, for the first block, the IV used must be known. In this case, there are no miracles:

• Either you know the IV, in which case the same reasoning applies,

• Or you try to guess it using common combinations, such as a null IV or a sequence of consecutive bytes.

If you cannot find it, then you will have to settle for decrypting blocks 2 to N.

Mitigating Padding Oracle Attacks

Padding Oracle Attacks can be mitigated by implementing proper error handling in the system. The system should not generate error messages that reveal information about the padding. Additionally, using authenticated encryption modes like AES-GCM (Galois/Counter Mode) can provide better security than CBC mode.

Resources

Padding OracleHackTricks

Padding oraclehackndo