Cryptography
cbc padding padding-oracle
Updated Fri, 01 Jul 2022 22:03:11 GMT

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


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?

Solution

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.

Comments (5)

  • +0 – In particular, if we cycle through all possibilities for the last byte, we're guaranteed to find exactly one validly padded block of the first kind. We might (with probability about 1/256) also find another valid block of some other type (most likely the second type), if the previous byte(s) just happen to be 02 (or 03 03 or so on). If that happens, we can easily find out which block is which by changing the second-to-last byte and seeing if that makes the padding invalid or not. — Jul 09, 2016 at 18:35  
  • +0 – Are you saying that the "01" may not necessarily be the value of the last byte? So, it has a high probability to be the "01" but its not necessarily "01"? — Jul 09, 2016 at 18:51  
  • +0 – @Minaj: yes, the last two bytes might be 02 02, or the last three bytes might be 03 03 03, etc. However, the last byte 01 will be the most frequent (and it's easy for the attacker to double check with just one addition query) — Jul 09, 2016 at 18:54  
  • +0 – Looking at the link I provided, there is no indication at all that this value needs to be crosschecked using a second query. The author says that the value is "01" and proceeds to do the rest of the computation based on this assumption. So, thanks for pointing that out. Which brings me to my next question. How exactly would one do the next query to confirm if this value is indeed "01". If you can relate your solution to the schema used in the document on the link I provided, it would be so helpful — Jul 09, 2016 at 19:03  
  • +0 – @Minaj: in CBC mode decryption, the decryption of the last block is $C_{n-1} \oplus D_k( C_n )$. If we know that we submitted a message with the the decryption of the last block having a valid padding pattern, we can submit a second query with $C_n$ being the same, and $C_{n-1}$ having its next-to-last byte altered. Then, if the last byte was a 01, the padding will still be valid; if the pattern was anything else, that'd break up the padding pattern. — Jul 09, 2016 at 19:07  

External Links

External links referenced by this document:

References