Padding Oracle: Why should padding be 0x01?

Question

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?

Answer 1

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

Answer 2

That is the way the PKCS#7 standard works. This standard is the "most used padding method in symmetric ciphers". Which is why most descriptions of the padding oracle attack simply assume that padding scheme. Other padding schemes are likely also vulnerable.

Answer 3

Yeah, the article is not being very clear about that detail.

They are attacking DES in CBC mode:

c = OpenSSL::Cipher::Cipher.new('des-cbc')

So let's look up the padding scheme for CBC. RFC 5652 Cryptographic Message Syntax (CMS) Section 6.3 gives this:

6.3. Content-encryption Process

Some content-encryption algorithms assume the input length is a multiple of k octets, where k is greater than one. For such algorithms, the input shall be padded at the trailing end with k-(lth mod k) octets all having value k-(lth mod k), where lth is the length of the input. In other words, the input is padded at the trailing end with one of the following strings:

01 -- if lth mod k = k-1

02 02 -- if lth mod k = k-2
          .
          .
          .
k k ... k k -- if lth mod k = 0

The padding can be removed unambiguously since all input is padded, including input values that are already a multiple of the block size, and no padding string is a suffix of another. This padding method is well defined if and only if k is less than 256.

Wikipedia gives a less terse version of the explanation:

The padding will be one of:

01

02 02
03 03 03
04 04 04 04
05 05 05 05 05
06 06 06 06 06 06
etc.

This padding method (as well as the previous two) is well-defined if and only if N is less than 256.

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes

... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |

---

Basically, the padding scheme is:

1. You are required to add at least one byte of padding; if the message is an even number of blocks, then you add an entire block of padding.
2. The last byte of the padding indicates how many bytes of padding were added (ie how many bytes you need to truncate off when decrypting)
3. It doesn't matter what you put in the padding bytes, but by convention it's the same as the last byte, which is the number of bytes of padding to remove.

(If there is a good reason why padding bytes aren't 0x00, I would love to know in comments)

---

So to pull off the padding oracle attack, you need to construct a known value for the last byte of the padded plaintext, which will be 01 when you fool the oracle into thinking that there's one byte of padding. Now that you have cracked the last byte, you can move on to constructing a known value for the second-last byte of the padded plaintext, which will be 02 when you fool the oracle into thinking that there's two bytes of padding, and so forth.