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.

-
Can you define what you mean by padding oracle attacks? If you count switching the order of the blocks around in ECB mode to be a padding oracle attack, then you're using a non-standard meaning of the phrase (since in that case you're not even attacking the padding function nor using it as an oracle). Do you maybe simply mean chosen-ciphertext attacks on confidentiality? – D.W. Jul 18 '14 at 23:08
@D.W. The best definition I can come up with is "any attack that relies on the unpadding of the decrypted plaintext message to retrieve information on the plaintext". If an attacker only has access to the ciphertext - and this presumption may be made - then it would be a subset of chosen ciphertext attacks. BTW I was expecting that this was more or less implied by the question. Obviously the CBC specific attack would not work for any other mode than CBC without some alteration. – Maarten Bodewes Jul 19 '14 at 12:04

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 1s 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.
-
I would count switching the blocks around in ECB a kind of padding oracle attack. An attack does not have to provide full plaintext to be considered successful - it does give information about the plaintext and more than just the length. It depends on the use case if the vulnerability has any significance. Thanks! – Maarten Bodewes Jul 18 '14 at 12:07
@MaartenBodewes, no, even if the plaintext was all zeros, you couldn't get the full padding oracle attack to work on PCBC because any ciphertext change affects the decrypted plaintext that gets XORed into the next block. It is vulnerable to an ECB-like attack by truncation (revealing which blocks end in some correct padding). – otus May 24 at 4:18

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

Nope, it’s purely restricted to CBC.

A padding oracle attack, also known as “Vaudenay attack” because it was originally published by Serge Vaudenay in 2002 and introduced at EUROCRYPT 2002, is an attack against cipher-block chaining.

The attack works against any block cipher in CBC mode, but other block cipher modes of operation are not affected by it… which – among other things – means that the discussion about padding oracle attacks against ECB didn’t make much sense in the first place. ECB isn’t affected by the attack… at all.

For details, check Vaudenay’s paper (PDF) which is available via the related Springer page. Related to your question, section “6. Fixes Which Do Not Work” (starting at page 541) is worth a read; including “6.4 Other Modes Of Operation” (on page 542) and “7. A Fix Which May Work” (on page 543).

A note aside:

Since most of your links point to Wikipedia (which does not provide a really good insight in the attack), something tells me you might want to take a look at SkullSecurity's “padding-oracle-attacks-in-depth” article, which explains padding oracle attacks a bit better than Wikipedia (that is, from my point of view).

Since it goes hand-in-hand with what I wrote above, I’ll just quote (emphasis mine) the last part of it:

…I've tested this successfully against the following ciphers:

• CAST-cbc
• aes-128-cbc
• aes-192-cbc
• aes-256-cbc
• bf-cbc
• camellia-128-cbc
• camellia-192-cbc
• camellia-256-cbc
• cast-cbc
• cast5-cbc
• des-cbc
• des-ede-cbc
• des-ede3-cbc
• desx-cbc
• rc2-40-cbc
• rc2-64-cbc
• rc2-cbc
• seed-cbc

But that's not interesting, because this isn't an attack against ciphers. It's an attack against cipher-block chaining — CBC — that can occur against any block cipher.

-
I know most of this, and I know about Vaudenays paper. I've actually used it to show padding Oracles on XML encrypt for a specific product. But I don't see anything in it about explicit tests on other modes of operation - except authenticated encryption of course. ECB is in there, but only to explain that CBC is as efficient (same number of block encrypts) as ECB. – Maarten Bodewes Jul 18 '14 at 0:08
@owlstead Trying to wrap it up in short: the attack exploits the information leakage that’s merely “protected“ by the XOR phase… that leakage lives within CBC’s required message padding. Now, since your biggest thing seems to be ECB… ECB doesn’t use a XOR operation to exploit etc. which hinders applying the padding oracle attack as we know it. Also, ECB has greater weaknesses in itself (which gives reason to use other modes in the first place) so there is not much logic in trying to use a padding oracle attack. (That’s like trying a padding oracle attack on CTR which doesn’t use padding…) – e-sushi Jul 18 '14 at 0:44
@owlstead Maybe it helps if you look at the different block cipher modes of operation again and ask yourself which modes offer alike leakage of information due to padding in a way that CBC does. If you look at the modes close enough, you’ll notice that it’s only CBC that introduces the exploitable issue… which is why no paper ever talks about successfully applying a padding oracle attack to any other mode (and why I said it’s purely restricted to CBC). – e-sushi Jul 18 '14 at 0:49
I'll have a look of course. I just thought that maybe somebody had taken a look before me. Otherwise I'll try and answer myself. Besides, it is a while back that I programmed the padding oracle attack (I used my old implementation for Crypto I at coursera and it worked the first time, so I did not take too good a look). – Maarten Bodewes Jul 18 '14 at 0:51
@ownstead Sure! To be honest, I’m not sure how I could make it clear why it won’t work with other modes without going through every single mode and practically show how an application of the attack fails on that specific mode and why. An alternative would’ve been to point at some kind of non-proof that states something like “…in this paper we prove that a padding oracle attack fails when trying to apply it on ECB/OFB/WHATEVER because…”, but I’m not aware of any alike paper or proof. Anyway, I’ll surely keep an eye open for your answer… which might pin it down much better than I ever could. – e-sushi Jul 18 '14 at 1:02

Padding Oracle attacks are mainly a problem in cases, where e.g. an encrypted message is modified and send to a target. These attacks try to measure the difference when decrypting and validating the message.

The steps are:

1. decrypting the message
2. checking the padding > error if wrong
3. checking or processing the data > error if wrong or format corruption detected

The padding oracle attacks try to measure timing differences between step (2) and (3) or utilizes different error messages.

Therefore if you do not have some kind of MAC applied on the encrypted data, these attacks might be applicable to your solution.

Padding is required on CBC, as it operates on full blocks. If you use other modes like CTR or GCM etc, which depend on CTR mode, this specific problem does not exist.

Always try to use either an AEAD scheme or at least apply a MAC (HMAC or CMAC) to your encrypted data. But take care and use Encrypt-then-MAC !

-
Thank you, but that's not what I was asking. – Maarten Bodewes Jul 17 '14 at 22:12
Sorry that I did not answer your question. At the end it depends heavily on the implementation. All modes which work only on full blocks might be affected. I am not aware of any other modes besides CBC and ECB and their derivations. – Thor Jul 17 '14 at 22:21
Hm, yes, ECB is wrong here. My mistake. – Thor Jul 18 '14 at 11:34