Clarification on the origin of `01` in this oracle padding attack?

Question

I have found what I believe to be a straightforward explanation of the oracle padding attack here: http://robertheaton.com/2013/07/29/padding-oracle-attack/

I am however getting confused by something which experts here should I believe find so easy.

When you open the link and browse to the subsection titled "Manipulating the Cipher text", there is a statement which says ...

If the server says that we have produced a plaintext with valid padding, then we can be pretty sure that P2'[16] must be 01.

I am unable to understand why a value of 01 will imply that the padding is OK. I know that as per PKCS#5, the only way we can get 01 as the last byte is when there was only 1 byte of padding. But according to the example on this page, I don't see anything that suggests that the data had 1 byte of padding. So, I fail to understand why a result of 01 is considered successful.

Is anyone able to look at the document and advise where the 01 comes from?

Answer 1

Actually, we don't care about the amount of padding the original message had; we care whether the modified plaintext (that is, the result of the decryption of the modified ciphertext) has good padding or not.

The padding will be valid if the last block had one of these patterns:

XX XX XX XX XX XX XX 01

XX XX XX XX XX XX 02 02

XX XX XX XX XX 03 03 03

XX XX XX XX 04 04 04 04

XX XX XX 05 05 05 05 05

etc

(where XX is any byte value). If we modify the ciphertext, and then the decryptor decrypts and packet and finds a valid padding, then we know that the value in that last block is one of those patterns.

Now, why do we initially consider one the first one, and essentially ignores the others? Well, for a random change (that is, if the attacker is in the initial stages of that attack, and may have no information about the decryption), then the last block will have the last byte 01 with probability 1/256; the rest of the alternatives will, in aggregate, happen with probability less than 1/65280, hence with quite high probability, the ciphertext being accepted with indicate that the last byte of the plaintext was 01.

Answer 2

This article is quite sloppily written... We suppose that the padding is valid, this means that upon decryption of $C_1' + C_2$, the resulting plaintext will be correctly padded. And we want to show that then $P2'[16] = \mathtt{01}$. We can show this by contraposition: with our construction of $C_1'$ as 15 random bytes followed by $\mathtt{00}$, if $P_2'[16] \ne \mathtt{01}$, then it is overwhelmingly likely that the padding will be rejected.

Suppose then that $P_2'[16] \ne \mathtt{01}$, we want to show that $P_2'[15] \ne P_2'[16]$, since this would make the padding invalid. Recall that $P_2'[n] = C_1'[n] \oplus I_2[n]$. On the one hand, we set $C_1'[16] = \mathtt{00}$, so $P_2'[16] = I_2[16]$. On the other hand, $C_1'[15]$ is random and independent of $I_2[15]$, so $P_2'[15]$ is random and so it equals $P_2'[16]$ with probability $1/256$, and the padding will be incorrect with probability at least $255/256$.