Here is a typical cryptographic situation:
A secret key exists that is only known to a sender and a receiver of messages. As it is hard to replace that key, since you either need a secure channel for transmission or a way how the receiver can send something to the sender to perform a key exchange and both may not exist, a lot of different messages will be encrypted all with the same key. Note, however, that the messages exchanged will all be different. It's not impossible that two messages could start with the same couple of bytes or contain the same byte sequences somewhere within the messages but that would be pure coincident and is not generally expected to happen frequently.
Now when using CBC encryption, there is an IV and that IV is randomly chosen for every message exchanged. With a 128 bit block cipher, like AES, the IV has 128 bits as well, so the chances that two messages are encrypted with the same IV is only 1 to 2^128, which is rather tiny. And even if the same IV would have been used for two messages, does it really matter if the messages are entirely different in the beginning? After all the IV is XORed with the first 128 bit of the message first, so even for the same IV that operation has a different result if the first 16 byte of the message are different than the last message that had the same IV.
However, CBC is considered outdated by most people today, pretty much every paper about block cipher chaining recommends to only use CTR for new development, praising all it's advantages. Sure, CTR has a couple of nice features but is it really equally secure to CBC in a situation initially described?
CTR also uses an IV, yet that IV is split into two parts: A nonce and a counter. As the counter values are for sure repeating for different messages, since all counters start at zero for the first block of every new message, the only randomness comes from the nonce. Yet the nonce will be less than 128 bit because there must be room for the counter. All papers say, you must never use the same IV with the same key to encrypt two different data blocks but the nonce space of CTR is always for sure smaller than the IV space of CBC, so the chances for a collision are much higher, aren't they?
I've seen CTR implementation that split the IV in half, so there are 64 bit nonce and 64 bit counter. In that case the chances for a nonce collision are just 1 to 2^64 compared to 1 to 2^128 for the CBC case. While 2^64 is still a big number, it's a whole lot smaller than 2^128.
Thus won't using CTR force you to replace the key much more frequently, unless you want to risk the security of your encrypted data exchange? Is CTR really a suitable replacement for CBC in a situation as described above?
Aside from that, CTR doesn't seem compatible to itself. Every CBC implementation can decrypt data correctly that any CBC implementation has encrypted. That's because there are no open question on how CBC works, everything is standardized. The same cannot be said for CTR as different CTR implementation can use different ways to split the IV into nonce and counter. When I know that my messages will never have more than 2^20 blocks, I could use only a 20 bit counter and thus get a 108 bit nonce, yet this won't work if the other side expects a nonce to be exactly 64 bit long.
To make things even more complicated, instead of splitting the IV into two parts, one can also create the IV by adding nonce and counter together or XORing nonce and counter together, which avoids the issue with the IV space reduction, yet I have no idea what such a behavior means in regards to security of CTR. Also it will make the implementation incompatible to most existing CTR implementations.
