Some AES CBC Encryption Myth-busting

Myth-busting us. /ˈmɪθˌbʌs.tɪŋ/ : the act of saying or showing that something generally thought to be true is not, in fact, true, or is different from how it is usually described.

Cambridge Dictionary

Symmetric block ciphers such as the Advanced Encryption Standard or AES (FIPS 197) are a widespread cryptographic primitive extensively used to provide data confidentiality and authentication in countless platforms and systems.

However, a block cipher cannot be used “as is” to protect data, it must be run in a so-called mode of operation to be able to securely process messages of arbitrary length. There exist many proposed and standardized modes of operation, for instance NIST currently approves several confidentiality, authentication, and authenticated encryption modes in the SP 800-38 document suite.

SP 800-38A (currently under revision) discusses five confidentiality modes: ECB, CBC, CFB, OFB, and CTR. ECB is particularly bad, not being randomized; its use is generally discouraged. CBC, CFB, OFB, and CTR are all malleable.

The best practice to avoid malleability is, of course, to add an authentication layer to the message, for instance, with a Message Authentication Code (MAC); the choice is either to go for an authenticated encryption mode (such as GCM or CCM) or to combine a confidentiality mode with a hash-based MAC (AES-CBC with HMAC-SHA-256 is a common choice).

We can say that CBC and CTR are probably the most ubiquitous modes of operation for confidentiality; they lie as well at the core of authenticated encryption modes such as GCM and CCM.

The general preference is probably for CTR, as CBC has no real advantage over it. However, IV reuse has much more catastrophic results for CTR than for CBC. A security proof for the CBC mode of operation can be found here. Note that for CBC, the IV must be chosen randomly for each encryption (beware, a counter is not a safe choice).

So, what can we say about CBC mode of operation? What are its properties? Check out this Wikipedia page for the (in)famous penguin image. Indeed, cryptographic wisdom (or folklore?) and Wikipedia tell us two things about CBC versus other modes of operation:

1. CBC (like ECB) requires the underlying block cipher (e.g., AES) to be implemented in both encrypt (for CBC encryption) and decrypt (for CBC decryption) directions. CTR has no such demand because encryption and decryption are basically the same function, where the underlying block cipher is used in the encrypt direction.
2. CBC encryption is inherently serial and not parallelizable, while CBC decryption is. CTR does not present this issue as encryption and decryption can be fully parallelized at block level.

There are no proofs of the above statements. In fact, both are (at least partially) wrong.

Why? For our discussion here, let us stick to the case where the message to encrypt is fully known in advance (no online encryption).

In CBC encryption, the user is supposed to choose a random IV and then run the process shown in the following picture (4 full blocks of a message):

The randomness of the IV affects all ciphertext blocks via the XOR feedback, and the process looks inherently serial. The corresponding decryption operation is as follows:

One can see that the IV is useful only to recover the first plaintext correctly. Even with a wrong IV, the decryption works “almost” fine. Each plaintext block depends on only two ciphertext blocks, so the decryption process can be parallelized.

Now, so far so good, but… let’s try to “reverse” the direction of CBC encryption. What if the user randomly chooses the last ciphertext block instead of the IV? The process would then be run backward as follows:

In the end, the user will come up with a legitimate CBC encryption, and CBC decryption will work fine and give the correct plaintext. Only the process of generating the ciphertext and IV is different. Note that the IV is still “randomly chosen” in the sense that it depends on the last ciphertext block, which has been chosen randomly.

But wait! The underlying block cipher is now used in the decrypt direction for CBC encryption. Therefore, one can use the underlying block cipher (e.g. AES) in the decrypt direction to perform both CBC encryption and decryption. First myth is busted!

Small digression: In fact, since AES in either encryption or decryption is a good pseudo random permutation (PRP), one could use encryption for both and save cycles and code size (which is good for constrained devices, although this can be no more considered “standard”):

Regarding the second common belief, note that one could run encryption in the following way: instead of generating the last ciphertext block randomly, one can split the message in two and generate the middle ciphertext block randomly (C2 in the picture below). Then, he can proceed both backward as explained above for the first message section and forward as classic CBC encryption for the second message section:

This has the disadvantage of requiring both encrypt and decrypt directions for the underlying block cipher for CBC encryption, but the two processes can clearly be run in parallel. As a result, if we have two AES instances, we can have a parallelization factor of 2 for the CBC encryption. Second myth is also busted!

This modified flow for CBC encryption is secure. In fact, what is lying at the core of the security proof for the CBC mode is the bound on the attacker advantage to distinguish a CBC encryption from a garbage emitter, i.e., an oracle that spits out random data instead of the real result of encryption.

The existing proof for CBC relates this advantage to the probability of causing a collision on an input of the underlying block cipher, considered as a PRP. If the attacker succeeds in producing a collision, he wins and can distinguish the CBC encryption oracle from the garbage oracle.

The paper bounds this probability by making the key observation that the values that are XORed with the plaintext blocks to form the inputs of the PRP are always independent of them and chosen uniformly at random because they are either the IV or the result of applying the PRP on a new input. But this is also the case for the modified flow, where the last ciphertext block is chosen randomly. Therefore, we can have the exact same proof of security for the CBC encryption with the modified flow (choice of random, last ciphertext block instead of random IV).

Note that for a given message and a given block cipher key, and considering straightforward CBC encryption, each ciphertext block is fully determined by choice of the IV, and it is obvious that the relation is a bijection. In fact, one could consider the IV as the “zero” ciphertext coming from a previous (non-existing) iteration, and the consideration remains valid if one “shifts” along the chain and chooses an intermediate cipher text block: all following ciphertext blocks are fully determined, and their values are bijections of the chosen value over the block space.

This is also true considering the modified-flow CBC encryption running in the backward direction switching the direction of the block cipher. It also remains true for all ciphertext blocks whenever an intermediate ciphertext block is chosen, and the others are generated proceeding in both directions.

Therefore, in our modified flows, if one chooses one ciphertext block uniformly at random, all others, including the IV are also distributed uniformly at random (although obviously not independent); but an IV chosen uniformly at random is precisely the starting point of straightforward CBC encryption.

Conclusion

We thus conclude that the advantage of an adversary to distinguish between the original or the modified-flow CBC encryption processes should be negligible. So, don’t bother too much about crypto folklore, and enjoy parallel CBC encryption!