Padding oracle attacks are a huge nuisance when using CBC mode encryption without authentication. Wouldn't all those padding oracle attacks be avoided if we'd just use bit padding instead? Or is does bit padding also leak information during decryption?

With byte aligned data, bit padding allows the padding oracle attack. Every message has to end in a 0x80 byte followed by any number of zero bytes. You can iterate one byte at a time just like with many other byte paddings.

If you allowed plaintexts that are not a full number of bytes long, the attack wouldn't be possible. (Every plaintext that didn't end in a full block of zeros would decode, so no attack.) However, most real world encryption uses byte aligned data.

• Yeah, that idea came to me too. I guess that makes the rest moot. I don't see any implementation switching to partial byte encryption soon. – Maarten Bodewes Sep 6 '14 at 21:44
• Wouldn't the attack work just the same with partial bytes? If I understand right, this attack works by manipulating the previous ciphertext block which is XORed after decrypting, and you can manipulate it by individual bits just the same as by full bytes. – Paŭlo Ebermann Sep 6 '14 at 22:16
• @PaŭloEbermann, you can, but you won't get the feedback from whether the padding is correct, since every bitstring with at least a single 1 in the last block has valid bit padding. – otus Sep 7 '14 at 5:55
• @PaŭloEbermann Other Oracle attacks may be feasible of course, you may be able to use the errors generated by the application receiving the garbled plaintext to extract information about the plaintext. One of such attacks (on encrypted XML) is described here – Maarten Bodewes Sep 8 '14 at 8:39
• @PaŭloEbermann I guess in principle you could extract timing information, but finding timing information about unpadding a bit string may be tricky (as it will take almost no time at all). That said, it can be done, e.g. by carefully putting the plaintext + padding on a page boundary of a modern CPU. Paging can be used to extract timing information. – Maarten Bodewes Sep 8 '14 at 8:44