Choice of padding scheme to prevent CBC padding oracle attacks?

Question

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.

Answer 1

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.

Answer 2

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.