September 8, 2013

Encryption - CBC Mode IV: Secret or Not?

When encrypting with CBC mode, the Initialization Vector (IV) is:

This page explains why. First, get familiar with how CBC mode works:

CBC mode of operation encryption CBC mode of operation decryption
(images taken from Wikipedia)

There are three scenarios where an attacker could possibly abuse the IV:

The next sections will discuss the security implications of an attacker with those capabilities.

Nonrandom and Predictable IVs

Statistical Correlations between IV and Plaintext

The IV must be random. To see why, consider what would happen if a counter, starting from zero, was used as an IV[1]. Suppose the first message sent is 0x0000000000000000. The IV would be 0x0000000000000000, so the input to the block cipher is 0x0000000000000000. Now, suppose a second message 0x0000000000000001 is encrypted. This time, the IV is 0x0000000000000001, causing the input to the block cipher to be the same as before: 0x0000000000000000 (because 1 XOR 1 is 0). So, both messages encrypt to the same ciphertext, which tells the adversary that they were different (since the IV is different, but the ciphertexts are the same). This shows how nonrandom IVs are more likely to correlate with the plaintext and leak information.

In general, whenever the first plaintext block is equal to the IV, the result will always be the encryption of 0x0000000000000000. If the adversary knows this value, they can look at a given (IV, ciphertext) pair and know whether or not the first block is the same as the IV. When the IV is random, it's much less likely for the IV to coincide with the first plaintext block by accident.

Chosen-Plaintext Attacks

Randomness is not enough, though. IVs have to be unpredictable, too[2].

Suppose there is a CBC-mode encryption system that selects a random IV, publishes it, asks the user for a one-block plaintext to encrypt, encrypts it with that IV, then gives the ciphertext to the user. Suppose Alice uses the system to encrypt two distinct messages A, and B, to get ciphertexts C and D. Alice gives Mallory the plaintexts and the ciphertexts and offers Mallory $1000 if he can tell her which of the two ciphertexts is the encryption of plaintext A. If he can't, he has to give Alice $1000.

If Mallory made a random guess, he would be right with 50% probability, because either C corresponds to A, or D corresponds to A. If the system is secure, Mallory shouldn't be able to do any better than this.

Mallory doesn't have to guess, though, because he can use a chosen-plaintext attack on the CBC-mode encryption system to figure out if C corresponds to A, or D corresponds to A. Mallory knows that the IV Alice used to encrypt A was IVA, and he knows that the input to the block cipher was A XOR IVA. Mallory just needs to know whether the block cipher encryption of A XOR IVA is C or D. Mallory asks the encryption system for the next IV, IVN, and sends it the plaintext A XOR IVA XOR IVN to encrypt. The system follows CBC mode, XORing Mallory's plaintext with IVN and passing the result to the block cipher. IVN XOR IVN is 0, so the system passes A XOR IVA to the block cipher, and gives Mallory the ciphertext. What Mallory gets back is either C or D, whichever one corresponds to plaintext A. In this case, Mallory gets back C, tells Alice that C corresponds to A, and wins $1000 with 100% probability.

Mallory would not have been able to do this if he could not predict the IV, since the plaintext he sends to the system depends on the next IV.

Knowledge of IV After Encryption

The IV's purpose is to ensure same plaintexts encrypt to different ciphertexts. When an adversary learns the IV after the plaintext has been encrypted, no harm is done, since it has already served its purpose.

The IV can be made public after encryption, without impacting the security of the system. Usually, it is prefixed to the ciphertext.

Altering the IV Before Decryption

If the adversary can alter the IV, without detection, before the ciphertext is decrypted, then they can corrupt the first block of plaintext. If the adversary knows the first block of plaintext is P and the original IV is OIV, and wants it to decrypt to Z, they can alter the IV to be P XOR Z XOR OIV, which will cause the first block to decrypt to Z (since (P XOR OIV) XOR (P XOR Z XOR OIV) = Z).

Encryption provides secrecy, not authentication or integrety. If encryption is used in a setting where the adversary can modify the IV or ciphertext, it must be authenticated. The right way to do this is to have the sending party apply a keyed Message Authentication Code (MAC), like HMAC, to the IV and ciphertext, and have the receiving party check that the MAC is correct before decrypting.


The above sections explain why, when encrypting with CBC mode: