Is the 'Padding Oracle attack' deterministic?

Question

I'm thinking about the example of Padding Oracle attack in CBC mode with PKCS7 padding given in Wikipedia.

It says about the guess of the last byte in the plain text:

In the worst case, they need to make 255 attempts to find the right value of z_1 (one guess for every possible byte).

But what will happen if the last but one byte of P2 happens to be 0x02. In this case it is obvious that we may have two possible values of z_1 which will result in correct padding: the first one will cause the last byte to be equal to 0x01 (valid padding) and the second one will cause the last byte to be equal to 0x02 (again a valid padding).

So is it guaranteed that the attacker will decrypt the message. Or the attacker may decrypt the message with high probability?

EDIT: How the attacker may distinguish between these sample plain text blocks (PT2) with different length of the padding:

... ... ... 68 02 02
... ... ... 68 02 01

The first plain text is with length 14 and 2 bytes padding. The second plain text is with length 15, last byte but one is 2 and padding 1.

Another edit:

By following the advice in the accepted answer I managed to quickly build an app which demonstrates a successful padding oracle attack. Available here.

Answer 1

These should both be valid paddings:

... ... ... 68 02 02
... ... ... 68 02 01

But if this ambiguity comes up, we can distinguish between the two by modifying the second-to-last byte in some way. After flipping, say, the highest four bits:

... ... ... 68 f2 02
... ... ... 68 f2 01

Only the second one is a valid padding.

Answer 2

I am afraid you didn't understand the algorithm of the padding oracle. I suggest studying the algorithm given at Vaudenay's original article on this. He is very concise in what he writes in the article, but it is there. It is deterministic, doesn't assume anything about plain bytes and works like this:

• The last block of ciphertext always has to contain correct padding bytes. If the plain text was an exact multiple of block size, the last block would be a full padding block

• The last block of ciphertext then must be ending in one of these patterns:

.......1
......22
.....333
....4444
........
n..nnnnn  (n is the block size)

Base on the above, the algorithm takes a cipher block from the cipher text (doesn't matter which one) to decrypt. It first prepends a random block in front of it, which pretends to be the previous cipher block. It then iterates the last byte of this block prepended and sends to Oracle until it receives a valid padding answer. This would take at most 256 tries.

At this point, it is known that the prepended block xored with the decrypted cipher block resulted in a valid padded block, i.e one of those listed above. But we don't know which one. It is most likely a block of 1 padding (......1) but it is possible it could be any of those listed above.

To find which one it really is, the algorithm starts modifying first the initial byte of the prepended block and send it to Oracle again. If it was a full padding block, by modifying the first byte of the prepended block we would have broken the padding. So if Oracle returns false padding, we know we had full padding block. If not algorithm changes the next byte and asks again and so on, until it receives from Oracle not valid padding answer.

This way we know exactly which one of those padding patterns we had, and so we know the last byte's plain value, which would be prepended cipher block's last byte x-ored by the number of padding bytes. Actually if by a good chance we had found a full padding byte, at this point we know all of the bytes of the block. But that is a low probability. The chance that the padding was only 1 byte is the highest.

So the algorithm goes on to decrypting the whole block after decrypting the last byte, again by changing one byte's value at a time on the prepended block that pretends to be previous cipher block. It first tries to find a padding pattern of ....22 which decrypts 2nd byte from the end, then looks for the pattern ...333 which decrypts 3rd byte from the end and so on. Each takes 256 tries max, so maximum it takes 256 * block size Oracle questions to decrypt a block.

Answer 3

Do you mean that there are multiple possible positive answers from the oracle? For example, if P2 is something like

... 0x2 0x1

then you have multiple guesses that will result in a 'correct padding' response. The right answer is given if your guess for the last bit is '0x1':

... |0x2| 0x1         |
XOR
... |0x0| (0x1 ^ 0x1) |

Since 0x1 XOR 0x1 XOR 0x1 yields 0x1, and ... 0x1 is a correct pad, then the answer is 'yes'.

But you can also get 'yes' if you try:

... |0x2| 0x1         |
XOR
... |0x0| (0x1 ^ 0x2) |

since 0x1 XOR 0x1 XOR 0x2 is 0x2, and the last 2 bits of the text are 0x2, 0x2, which is also a correct pad.

I think you can reconcile this by doing the guessing in ascending order -- 0x1 is the correct answer, so if you get 'yes' there first, you shouldn't need to try 0x2. If you guessed 0x2 first and got a yes, you may want to check all lower values down to 0x1 to verify.

The lowest value for which the oracle returns 'yes' is the correct one.

Answer 4

If you're like me, you're probably wondering what to do in this case

... 02 02
... 02 01

and you've probably already heard the solution that tells you to just modify the last two bytes instead of just the last one. You're probably wondering why that actually works (which it does).

You will find two valid paddings when trying all 256 values for the last byte. The one creating the 01 ending is always right whereas the 02 ending is a coincidence of the second-to-last byte being 02. Remember that the second-to-last byte is the actual ciphertext while the last byte is the result of XORing your guess. So you're not trying to find both the 01 solution and the 02, rather than you're trying to make sure the valid padding you have is in fact the 01 solution since the 02 solution is a valid padding by coincidence

The confusion usually stems from seeing this on paper rather than implementing it. When implementing, you'll loop over all 256 values for the last byte, but when you find a valid padding you won't know if it's because you hit the padding ending in ...02 01 or the padding ending in ...02 02. So to be doubly sure you have the right one you'll tweak the second-to-last byte to anything else and only the truly valid guess on the last byte will still return a valid padding.

Answer 5

Assume that your plantext has two block: P1 and P2. The cipher text is C1 and C2. You are worrying when P2 with padding is something like:

.........................0x2 0x2

To crack P2, you need to send a controllable block X and C2 to the Oracle, iterate the last bit of X from 0 to 255, and check the response. And you are concerning that a valid return from Oracle can happen with 0x2 0x2 or 0x1.

However, if you initialise X = C1, without any byte modification, sending X and C2 to the Oracle would return a valid response, which is for 0x2 0x2. This is because there are at most two cases that Oracle return "valid", and block C1 is one of them. Therefore, you just need to vary the last byte of X to other 255 values rather than the original value of C1. Any other byte value that gets a valid response is for 0x1.

Keep in mind that if P2 with padding is something like ............0x1, there will be no other bytes that can get a valid response from the Oracle. In this case, you know the byte of C1 is the valid one.