This is the short, technical version of a technique that I'll be writing more about in a few days. This blog post is geared towards readers already familiar with current topics in cryptanalysis.
In Rizzo and Duong's paper on practical padding oracle attacks, the section on CBC-R states "CBC-R turns decryption oracles into encryption oracles." They describe their technique as an extension of what Vaudenay wrote in his 2002 Eurocrypt paper on security flaws induced by CBC padding. However, as I describe below, Rizzo and Duong's technique is also applicable to decryption oracles operating in CBC mode. This application was not described in their paper and I'm not sure if Rizzo and Duong realized its potential for decryption oracles, but so far I have not been able to find any public documentation on the use of CBC-R apart from discussion on padding oracle attacks.
CBC-R applied to decryption oracles
When performing CBC-R attacks using padding oracles as described by Rizzo and Duong, the first step is to discover the plaintext using Vaudenay's attack. Since we already have a mechanism for obtaining the plaintext of the entire message, we can construct our own message.
From here on, blocks will be referred to using C or P to indicate ciphertext or plaintext, a number to indicate the position of the block, ^ as an XOR operation, and ' to indicate that the block is the version of the block as it exists in the final message we are constructing.
If we have a message with two blocks and the IV included, we start by running the message through our decryption oracle. We now have the plaintext and ciphertext for each block. C2 remains the same, thus C2 = C2'. We calculate C1' as (C1 ^ P2 ^ P2').
We now submit the following, concatenated, to the decryption oracle: IV, C1', C2. This provides us with the new P1, which is garbled because we tampered with C1. We now calculate IV' as (IV ^ P1 ^ P1').
We now have the ciphertext for our newly constructed message: IV', C1', C2.
This technique, when applied to a decryption oracle, allows for encryption with far fewer requests to the oracle: only one per block!
Implications
This makes the discovery of a decryption oracle potentially far more dangerous. Being able to decrypt the contents of any message using the same key and cipher is bad enough, but when you can use the same oracle as an encryption oracle, the layer of encryption may as well not exist. In addition, this technique requires no requests to the oracle that result in decryption-related errors. By contrast, CBC-R as an extension to Vaudenay's attack 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, this technique does not require the use of any specific block cipher. Unlike the original description of CBC-R, this technique does not require a specific type of padding. This attack requires only a decryption oracle operating in CBC mode.
