0
$\begingroup$

I have been working on a C implementation of padding oracle attack on a block encryption algorithm using CBC mode of operation. I understand the concept fine but I can't seem to find an answer to the following question(despite looking up similar questions on stackoverflow and this site):

When we send a Ciphertext block concatenated at the end of a block we manipulate to the padding oracle, why do we assume that first success means that the XOR operation produced a 1 and not 2,3,4,5,6 or 7 for that matter?

To add more information for those not in the know, PKCS#5 is a padding scheme for plaintexts of blocksize 8 bytes where the last block contains n number of padding bytes each containing the value n. So, lets say we send (C1||C2) where C2 is the original Ciphertext and C1 is a block whose lowest byte we vary from 0 to 255 so as to get a successful validation from the padding oracle. A successful validation, in my opinion, means that the padding is correct, i.e. the resultant plaintext byte is 1 if there were just 1 padding byte and 2 if there were 2 and so on...

Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower? If yes, does that mean there may be instances where this algorithm would fail to decode ciphertext?

Improve this question
$\endgroup$
1
  • $\begingroup$ It's worth watching youtube.com/watch?v=8Tr2aj6JETg, it gives an overview of the attack and CBC encryption. You can see that if you get unlucky with your first attempt, you can modify the second digit and then it'll only be valid if there is a 1 in the last position $\endgroup$
    – Jordan
    Oct 7, 2016 at 9:24

1 Answer 1

Reset to default
0
$\begingroup$

Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower?

Largely, yes. Remember, our general assumption is that an attacker is happy with an attack that only works most of the time. In this case, assuming that the attacker has no initial information about the plaintext block under attack, then a random C1 that causes us to have valid padding would correspond to an 01 padding byte with probability circa $1 - 1/255$ of the time.

In addition, if you find a C1 that might reveal the last byte, and might have a longer padding pattern, there's a very easy test; try C1 with the penultimate byte modified; the resulting decryption will still have valid padding if it had an 01 padding byte, and have invalid padding if it was anything else; hence it would be easy to catch.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Accepting the answer although the probability you've indicated is very close to correct but not entirely so(it does not account for the thin cases 3 3 3, 4 4 4 4 and so on...) $\endgroup$
    – Donbhupi
    Oct 4, 2016 at 17:35
  • $\begingroup$ I did try to account for those patterns, but going through the math in detail, the success probability is a tad higher; there are $2^{120}$ values of C1 that makes the last byte 01, there are $1+2^8+2^{16}+...+2^{112}$ values of C1 that makes it a valid padding pattern other than 01; the probability that a random valid padding will be 01 is, since $1 + 2^8 + ... + 2^{112} + 2^{120} = (2^{128}-1)/(2^8-1)$, we have $2^{120}/(1 + 2^8 + ... + 2^{112} + 2^{120} = 2^{120} / ((2^{128}-1)/(2^8-1)) = (1 - 2^{-8})( 2^{128}/(2^{128}-1))$; effectively $1 - 1/256$ $\endgroup$
    – poncho
    Oct 4, 2016 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.