Is it safe to use a randomized IV for CTR mode?

Question

I'm currently reading the chapter of Cryptographic Engineering (Ferguson, Schneier, Kohno 2010) about block cipher modes of operation. They have recommended CBC with random IV instead of CTR due to the difficulty of generating nonces for CTR:

In the first edition of this book, we recommended CTR. However, we are always learning more, and we now recommend CBC with random IV. [...] CTR is a very good mode, but only if the application can guarantee that the nonce is unique, even when the system is under attack. That turns out to be a major source of problems and security weaknesses. CBC with random IV has some disadvantages [...], but it is robust and stands up well to abuse. Nonce generation turns out to be a really hard problem in many systems, so we do not recommend exposing to application developers any mode that uses nonces.

To me this seems to be ignoring an obvious solution: use CTR with a random IV instead of a generated nonce. This would let us avoid these problems and keep the random-access fun of CTR. This possibility being ignored implies there's some issue with it, but nothing I've read suggests one to me.

I know that the value is used differently in the different modes...

• CBC: the IV or previous output block are XORed with input block, then ciphered
• CTR: the nonce is combined/XORed with the counter, then ciphered, then XORed with the input block

...but I don't see how this would prevent a random IV from being as secure as a properly-chosen nonce. It would also be unique, and would provide more bits of randomness than a nonce system (though I think this shouldn't be significant unless the cipher were weak).

Can I safely use a randomized IV for CTR mode?

Answer 1

You say that a random IV "would also be unique", but really that is the crux of the problem. The problem with counter mode is that it is secure unless the same counter is used twice; if it is, it is likely that an attacker will be able to recover both plaintext messages. This contrasts with CBC mode, which if you repeat an IV, it has the relatively benign failure mode of allowing an attacker to detect whether or not the initial blocks of the messages are the same.

So, with random IVs, is the probability of a repeat sufficiently negligible that we can live with the possibility? Well, that depends on the size of the IV, the total number of messages we're talking about (and our tolerance to risk; how small is negligible). With 8 byte IVs, well, we're likely to see repeats (because of the Birthday Paradox) after a few billion messages (and have nontrivial probability of repeats before then); I would consider that too high of a risk to live with. With 12 byte IVs, it's unlikely we'll see a repeat before a few trillion messages, but for very long-lived keys, perhaps this is unacceptable. With 16 byte IVs, it is unlikely to ever see a true repeat, however now we'll need to worry about partial overlaps (where two different IVs generate the same block cipher input after combining with the counter for different parts of the messages).

In contrast, with CBC mode, we don't have to worry about any of this. Once we make sure that the IVs are generated unpredictably (and we check the integrity of the encrypted text, a requirement of CTR mode as well), we're golden. I believe Ferguson et al recommend CBC mode specifically because it is more foolproof and less fragile.