Why should I use an Initialization Vector (IV) when I have unique keys?

Question

I took a look at “Why, or when, to use an Initialization Vector?” but my question is not the same.

I have unique keys encrypting each plaintext (in CBC mode, AES-256) and I do not use a key to encrypt more than one plaintext. Is it insecure to use null IVs in this case? If it is insecure, why?

Answer 1

Caveat: as very rightly pointed in that other answer, using a fixed/no IV does make some attacks less difficult. I wish the following answer would have been less affirmative. I have accordingly made adjustments in italic.

There's no imperious need for an IV when unique keys are used. Given that a 256-bit key cipher is used, what's proposed is safe.

When each key is used only to encipher a single message, it is reasonably safe (from a confidentiality standpoint) to use null IV for all messages. That's customary, for all common modes requiring an IV. It avoids the need to generate an IV, and transmit it, and (in the case of CBC) perform a XOR of the first block with it.

Why? Intuitively: random (or otherwise appropriate) IVs are primarily here to make it unlikely that the same input/output pairs (at the block cipher level, and using the same key) ever occurs during the encryption of two distinct messages, even when one bears some relation to the other (including but far from limited to: starting with the same first block). When there is a single message, that need disappears. More formally, the basic (non-quantitative) proof of security of CBC (and other secure modes) holds without IV when there is a single message per key.

On the other hand, by not using a random IV, in some setups, one gives the adversary the same known plaintext block enciphered with different keys (in CBC, that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number $n$ of keys. This is bad, but there are mitigating factors:

• The attack only find one of the $n$ keys, and the corresponding plaintext; when theses are independent (e.g. different photos stored enciphered under different keys), the expected number of trial encryptions to revover a certain plaintext is the same as for random IV.
• The attack requires searching the result of each trial encryption of the known plaintext among $n$ values. The investment and operating cost for the non-trivial devices that store the ciphertexts blocks and search among them at high rate grows with $n$ (at least the memory capacity is proportional to $n$).

_{Note: The single message per key setup leaves the total message length per key limit unchanged for CBC, PCBC, CFB: that's $2^{(b+1-k)/2}$ blocks for less than $2^{-k}$ odds of collision (implying some level of insecurity) using a $b$-bit block cipher. That limit is dramatically raised for OFB and CTR in the single message per key setup.}

Answer 2

You should use random IV even when unique keys are used.

This prevents key-collision attack where the attacker collects number of cryptograms that have been encrypted with unique keys and brute-forces for key.

Using predictable IV will reduce security of your cryptosystem by a factor of N (where N is the number of ciphertexts created). The attack recovers one of the ciphertext (but the attacker cannot control which one).

https://eprint.iacr.org/2012/159.pdf