CBC-R: It's not just for padding oracles!

This is the short, technical version of a technique thatI'll be writing more about in a few days. This blog post is geared towardsreaders already familiar with current topics in cryptanalysis.

In Rizzo and Duong's paper on practical padding oracleattacks, the section on CBC-R states "CBC-R turns decryption oracles intoencryption oracles." They describe their technique as an extension of whatVaudenay wrote in his 2002 Eurocrypt paper on security flaws induced by CBCpadding. However, as I describe below, Rizzo and Duong's technique is alsoapplicable to decryption oracles operating in CBC mode. This application wasnot described in their paper and I'm not sure if Rizzo and Duong realized itspotential for decryption oracles, but so far I have not been able to find anypublic documentation on the use of CBC-R apart from discussion on paddingoracle attacks.

CBC-R applied to decryptionoracles

When performing CBC-R attacks using padding oracles asdescribed by Rizzo and Duong, the first step is to discover the plaintext usingVaudenay's attack. Since we already have a mechanism for obtaining theplaintext of the entire message, we can construct our own message.

From here on, blocks will be referred to using C or P toindicate ciphertext or plaintext, a number to indicate the position of theblock, ^ as an XOR operation, and ' to indicate that the block is the versionof the block as it exists in the final message we are constructing.

If we have a message with two blocks and the IV included, westart by running the message through our decryption oracle. We now have theplaintext and ciphertext for each block. C2 remains the same, thus C2 = C2'. Wecalculate C1' as (C1 ^ P2 ^ P2').

We now submit the following, concatenated, to the decryptionoracle: IV, C1', C2. This provides us with the new P1, which is garbled becausewe tampered with C1. We now calculate IV' as (IV ^ P1 ^ P1').

We now have the ciphertext for our newly constructedmessage: IV', C1', C2.

This technique, when applied to a decryption oracle, allowsfor encryption with far fewer requests to the oracle: only one per block!

Implications

This makes the discovery of a decryption oracle potentiallyfar more dangerous. Being able to decrypt the contents of any message using thesame key and cipher is bad enough, but when you can use the same oracle as anencryption oracle, the layer of encryption may as well not exist. In addition,this technique requires no requests to the oracle that result indecryption-related errors. By contrast, CBC-R as an extension to Vaudenay'sattack requires up to 255 errors per decrypted byte and 256 requests per byte,making it relatively easy to spot in server logs since the traffic is so unusual.

As in the case of the original description of CBC-R, thistechnique does not require the use of any specific block cipher. Unlike theoriginal description of CBC-R, this technique does not require a specific typeof padding. This attack requires only a decryption oracle operating in CBCmode.

Trustwave reserves the right to review all comments in the discussion below. Please note that for security and other reasons, we may not approve comments containing links.