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).