Choice of padding scheme to prevent CBC padding oracle attacks? 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.
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.