Cryptography
Updated Mon, 06 Jun 2022 13:52:21 GMT

# Modes of operation that allow padding oracle attacks

It seems to me that padding oracle attacks are mainly a concern for users of CBC mode encryption. Question: are any other modes of operation vulnerable to padding oracle attacks? And if so, why?

There was some discussion in the comments section of this answer with regards to ECB, but it didn't reach a conclusion. It would be a surprise to me if ECB would allow padding oracle attacks that give more information than the length of the plaintext, but I'd rather be sure.

## Solution

In the padding oracle attack you have an oracle that only tells you whether a particular chosen ciphertext decrypts to a correctly padded plaintext. That oracle is used to build a last word oracle, which used iteratively can reveal a whole message.

The reason it works in CBC mode is that we can make predictable, arbitrary changes to the plaintext of the last block by modifying the ciphertext (of the second to last block, or the IV):

\$\$P_i = E(C_{i}) \oplus C_{i-1}\$\$

For another mode to be vulnerable, the same kind of control would be needed.

It would be a surprise to me if ECB would allow padding oracle attacks that give more information than the length of the plaintext, but I'd rather be sure.

In ECB, the ciphertext only passes through the decryption function, so any change to it makes an unpredictable change to the only block of plaintext it affects.

Except, there is one predictable change we can make: we can substitute any other ciphertext block of a valid message for the last. If it passes the padding oracle, we know it ends with one of `1`, `2|2`, ... `16|...|16` (assuming that's the padding mode used), but we can make no other checks.

This is unlikely to help because a textual (ASCII or UTF-8) message will never include most of those `9|...|9` (tabs) and `10|...|10` (newlines) being the only ones I could imagine seeing. In a "random" binary plaintext, it would be likely you'd see some `1`s at least, but that would probably not be helpful.

Still, I guess this leaks information, so it should count as an attack.

Question: are any other modes of operation vulnerable to padding oracle attacks?

As above, ECB is only partially vulnerable, but how about other modes?

CFB, OFB and CTR all allow predictable changes to the last plaintext block. However, they are essentially stream ciphers that don't require padding. If an implementation does use padding, it could be vulnerable. GCM is authenticated, so it doesn't leave room for the attack, and anyway also doesn't require padding.

For example, here's a padding oracle attack on \$b\$-byte blocksize CTR padded with \$p = 1\$ to \$b\$ bytes each equal to \$p\$, up to a multiple of the blocksize:

1. The ciphertext is simply the xor of a message and an IV-derived keystream: \$C = M \oplus K\$. You know the final 1-\$b\$ bytes of \$M\$ will be padding, so you can flip a single bit in the last byte, test it; the second last, test; etc. as long as the oracle returns 0. You will find the padding length, and thus know the last \$p\$ bytes of both \$M\$ (\$M_i=p\$) and \$K\$ (\$K_i=C_i \oplus p\$).
2. Set the last \$p\$ bytes so that they are correct for a \$p+1\$ byte padding (or if \$p = b\$, remove the last block of ciphertext). Now you can try every possible ciphertext byte in the next position (\$p+1\$ counting from the right). One of them will pass the oracle, returning 1. Now you know the last \$p+1\$ bytes of both \$M\$ and \$K\$.
3. You can repeat step 2. any number of times, to find the whole keystream and message.