Cryptography
Updated Sat, 04 Jun 2022 21:22:18 GMT

I just finished reading about padding oracle attacks at https://blog.skullsecurity.org/2013/a-padding-oracle-example, and it blew my mind. I think I understand almost all of it, but I do not understand one critical thing:

When looking for good padding, why should the first one (last byte of the message) be `0x01` when you've found the right symbol? Additionally, why should the pattern for the next to last byte be `0x02 0x02` and the next `0x03 0x03 0x03`, etc.

I understand the padding scheme requires that if you have 4 bytes of padding, the bytes should be `0x04`, `0x04`, `0x04`, `0x04`. And if you have 2 bytes of padding, it should be `0x02`, `0x02`, etc. That's not the problem. The problem I do not understand is: Why should you get padding when you decrypt your now-modified sequence of bytes?

In other words, pretend I had the string "Hello!" and a block size of 8 bytes. I would expect there to be two bytes of `0x02` padding after whatever the encrypted "Hello!" string turns out to be. Now, in the attack, I add 8 bytes of zeros before it, run it through decryption, incrementing the last byte until I get valid padding. I do not understand why the padding should be 0x01 at this point, not 0x02, as was in the original. Similarly, when it moves on to the next byte to figure out, they are looking for 0x02, and 0x03 for the next, etc. Why is this?

## Solution

I do not understand why the padding should be 0x01 at this point, not 0x02. Similarly, when it moves on to the next byte to figure out, they are looking for 0x02, and 0x03 for the next, etc. Why is this?

Have a look at the CBC block cipher mode.

The basic of the padding oracle attack is that \$ P_i=D_k(C_i) {\oplus} C_{i-1} \$.

Going through the paddings you are effectively looking up the value of \$D_k(C_i)\$. Increasing the padding is not applies to the plaintext, it just helps to reveal the decrypted ciphertext byte by byte (not yet plaintext).

Example - you choose to encrypt string "Hello!" and add padding 0x02 0x02 before encryption. But the attacker doesn't know this. After encryption the output looks completely random (no padding).

The attacker tries to change the last byte of the previous block (or IV) array (for clarity we used zeros) until the oracle says the padding is good. Now the attacker knows, that \$D_k(C_i)[8] {\oplus} test[8] = 0x01 \$ (assuming 8 byte = 64 bit block).

Continuing this way the attacker completely reveals \$D_k(C_i)\$ (looking at image it's the output of the "block cipher decryption" box)

Now appying original previous ciphertext block (or IV) \$C_{i-1}\$ the attacker reveals your Hello!0202

(ok, as a shortcut, the padding could be revealed the discarted in the first step, but that's not important in this example).