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.

migrated from security.stackexchange.com Oct 19 '16 at 6:40

This question came from our site for information security professionals.

up vote 3 down vote accepted

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 study 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 cipher text always has to contain correct padding bytes. If plain text was exact multiple of block size, last block would be a full padding block

  • Last block of cipher text then must be ending in one of these patterns: .......1 ......22 .....333 ....4444 .... n..nnnnn (n being 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, 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 number of padding bytes. Actually if by good chance we had found a full padding byte, at this point we know all of the bytes of the block. But that is 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 end, then looks for pattern ...333 which decrypts 3rd byte from 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
  • 1
    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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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