I was watching a lecture about the padding oracle attack on CBC mode block ciphers, where the padding scheme used was PKCS#7.

My question is can padding oracle attacks be prevented (without any use of a MAC) solely by choosing a suitable padding scheme?

In the lecture, the attack first finds what the actual padding of the plaintext will be. I assumed that the rest of the attack outlined in the lecture worked only because PKCS#7 is a predictable padding scheme. Which means that once the adversary gets a BAD_PAD error, he will know that there is only one possible pad that will be the correct pad.

If the padding scheme used is unpredictable, would the CBC mode be secure against padding oracle attacks?

I was thinking of the following padding scheme:

Choose distinct and random bytes X and Y, which will be different every time you encrypt a message. Pad with X and at least one copy of Y. So if the block length is 8 bytes and your message is ABCD, you can pad the block to be ABCDXYYY, ABCDXXYY, or ABCDXXXY.

Would this padding scheme prevent padding oracle attacks? Because now when the attacker gets a BAD_PAD error, he will not know for sure what the correct pad should be.

• Have a look at the POODLE attack. – SEJPM Sep 15 '18 at 10:54
• If you don't return padding errors to the attacker there is no padding oracle and no padding attack. – zaph Oct 15 '18 at 16:37
• @zaph You should send some info, at least say generic error. The attacker can still use this information. If you don't send any error and accept it is, how will you know that which part belongs the message. – kelalaka Oct 16 '18 at 9:29
• @kelalaka Padding errors should not be used for anything related to authentication including errors. If error detection is needed add it or authentication. If there is a padding error generally the decryption failed so there is no useful message. – zaph Oct 16 '18 at 12:40

Padding oracle attacks are not the padding scheme's fault! They are not fixed by changing the padding! They are fixed by not leaking partial information about the result of decryption, or (preferably) by just using CCA encryption.

Any time you provide this to an adversary:

* Accept arbitrary c
* Decrypt m = Dec(c)
* Reveal formatcheck(m)


... if it's only a CPA-secure encryption scheme, you undermine all security of encryption. The specifics of the format check don't much matter. Some padding schemes (more generally, "format checks") can make a plaintext recovery attack more or less direct, but all will undermine overall security to some extent.

• Thanks! Although I found out about a scheme called Abit-PAD. In this scheme, there are no invalid padded messages. So will I be correct to say that CBC with the Abit padding scheme will be secure against padding oracle attacks, as the oracle will never return BAD_PAD? I am not considering other attacks, just padding oracle attacks. – amad-person Sep 16 '18 at 8:59
• According to usenix.org/event/sec02/full_papers/black/black.pdf semantic security is maintained in the presence of a valid-padding oracle for this ABIT-pad (since every string is a valid encoding of something, the oracle always responds the same way). – Mikero Sep 16 '18 at 14:48

Yes, you can create a padding scheme (for block cipher modes of operation) that cannot be attacked by padding oracles. Construction of such a scheme would be relatively easy. For instance, you could have a function where the padding is always correct. For instance, for AES you could say that the padding is the value of the last byte modulus 16 + 1. If there are no padding errors then padding oracles are not possible by definition.

The problem is that it is still possible for an attacker to change the plaintext. The padding is not used to authenticate the correctness of the ciphertext. That however also means that any error during further processing of the altered plaintext can cause an error. And guess what: this can also leak information to the attacker.

This shows that padding oracle attacks are part of attacks on the processing of plaintext. In other words: padding oracle attacks are a specific kind of plaintext oracle attack. Plaintext oracles on the original message can be as bad as padding oracle attacks.

It can be easily proven that different plaintext oracles can be as bad as padding oracle attacks by simply embedding padding in the plaintext itself. Any detection of the unpadding within the message can then be used in exactly the same way as a normal padding oracle.

For a real life plaintext Oracle that does not depend on padding you can have a look at the paper "How to break XML encryption" by Jager & Somorovsky, chapter 4.5 "An Axis based Oracle".

In the end you don't want to be processing unauthenticated ciphertext at all, especially not in an online session where plaintext oracles may apply. The generic solution to this is to use authenticated ciphertext, preferably using an authenticated / AEAD cipher.

• sorry. if we use 128-bit character encoding than padding will not be necessary. Not a serious one. – kelalaka Oct 16 '18 at 10:01