Cryptography
block-cipher padding-oracle
Updated Sat, 04 Jun 2022 21:22:18 GMT

Padding Oracle: Why should padding be 0x01?


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).

Comments (2)

  • +0 – Oh. So in other words, we're looking at each byte (starting with the last), and monkeying with our extra input until the decrypted result LOOKS LIKE a valid padding byte. Then we use our extra input against the encrypted portion to reveal what it actually is. Is this correct? If so, I think I've got it now. — Aug 29, 2018 at 15:47  
  • +0 – @kmort yes, that's the idea.. that's why it is important that the server doesn't reveal if the padding is wrong (today if the padding is wrong, random padding is implemented and the response fails later) — Aug 29, 2018 at 18:14  

External Links

External links referenced by this document:

References