# Is the 'Padding Oracle attack' deterministic?

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.

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.

• Yess... it seems to me that you are absolutely right!!! 10x! – Lachezar Balev Oct 20 '16 at 10:38
• It works, I've managed to build and app by following your advice. 10x again. Answer is updated with an example. – Lachezar Balev Oct 22 '16 at 13:10

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.

• I left out the IV discussion from the edit. IVs are not secret so you can assume the attacker already knows it. – otus Mar 14 '17 at 6:24
• I understood it at least partially because I managed to decrypt a text somehow :-) Your algorithm seems much more intelligent. But please explain. You wrote: "This would take at most 256 tries.". Ok, 256. Then: "To find which one it really is, algorithm starts modifying first..." But this means that additional questions should be sent to the oracle to determine the right pattern. Doesn't this mean that the MAX questions per decrypted byte are more than 256? – Lachezar Balev Mar 14 '17 at 13:00
• I am new to the stackexchange thing so I have an account mess, Phazer and PhazorP are both me. Anyways.. the algorithm is not mine, it is Vaudenay's who is the original person who came up with the Oracle Padding attack against CBC. You can find his article on it online, algorithm is there. He is very concise in explanation though. – phazer Mar 15 '17 at 14:11
• About the maximum number of tries, yes for the last byte it needs at maximum 256 plus block size number of tries. For the rest it needs 256 max for each byte, because after the last byte decrypted we are trying specific padding, ...22 for 2nd byte, ...333 for 3rd byte and etc. So for n block size maximum it will need 256 * n+n Oracle questions to decrypt a block. On average it will need 128 * n+n Oracle questions. Very efficient. And if you know the Oracle never lies, you can do 255 tries instead of 256 , if not found after 255 questions it must be 256th. – phazer Mar 15 '17 at 14:30

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.

• I'll think over your explanation later today, thanks. I'm still not completely sure how the sorting may resolve this... I've edited my question because it is really a bit sloppy and it is not easy to understand. – Lachezar Balev Oct 19 '16 at 6:32
• Damn :-) I still do not get it. Both .. 68 02 02 and ... 68 02 01 are validly padded, equally possible and are plain text messages with different length. How the sorting should tell me which is the right one? – Lachezar Balev Oct 19 '16 at 19:33

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.