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.