18 Feb 2019

The Padding Oracle Attack

If I took anything away from reading the Return Of Bleichenbacher’s Oracle Threat and The 9 Lives of Bleichenbacher’s CAT papers, it was that padding oracle attacks have been relevant for the past 21 years and will very likely continue to be relevant for the foreseeable future. Therefore, I think it is worth taking the time to understand how this attack works.

A good example is the classic padding oracle attack on CBC mode encryption. In an exploitable scenario, an attacker who hopes to obtain the plaintext of a given ciphertext is free to make modifications to the ciphertext before it is secretly decrypted by the server. This scenario is commonly referred to as an adaptive chosen-ciphertext attack (CCA2 for short). The decryption routine does not directly reveal the plaintext to the attacker, but it does reveal whether an error took place during the validation of the resulting plaintext’s padding. It turns out that this single bit of information (literally 1 bit, as in true or false) is enough for an attacker to completely decrypt a given ciphertext.

The diagram below illustrates the theory behind the attack.

The intuition here is that when an error isn’t raised regarding invalid PKCS#7 padding, the attacker knows \(P_2^\prime[8] = 1\) since this is valid padding. The value of \(C_1\) is also considered public knowledge. That means that if an attacker can guess what value of \(C_1^\prime[8]\) results in valid padding (of which there are only 256 possibilities), it is trivial to recover the result of \(P_2[8] = 1 \oplus C_1[8] \oplus C_1^\prime[8]\).

To decrypt an entire block, this process is repeated for each remaining byte by incrementing the PKCS#7 padding (e.g. the next is \x02\x02) and applying the same concept. Since \(A \oplus A = 0\) and \(A \oplus 0 = A\), it is trivial to increase the padding for all previous bytes in the block. This means that at most, the number of guesses for each block is \(256 \times block\ length\).