1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you don't reuse the key with multiple IVs then with CTR you just start at 0 and go. No need to worry about nonce reuse and you can encrypt as much data as you want. You don't get that with CBC. And I don't see people recommending CTR as much as GCM (authenticated). While not talked about as much, I see CCM used in many situations, probably most notably by Microsoft in SMB encryption. $\endgroup$ – Swashbuckler Jan 31 at 22:29
  • $\begingroup$ GCM, CCM (and, for completenesss, EAX) all use CTR internally, although they do make sure that the nonce/counter creation is specified explicitly. $\endgroup$ – Maarten Bodewes Feb 1 at 9:54
  • $\begingroup$ @Swashbuckler GCM is not really an own mode of operation, it's just CTR with a downstream message authentication. I know that as I've already implemented GCM on top of an existing CTR implementation. If you ignore authentication for a moment, its only advantages is that it exactly defines how the IVs for CTR are generated; thus it won't suffer by the incompatibility problem of CTR. $\endgroup$ – Mecki Feb 3 at 9:56
  • 1
    $\begingroup$ @fgrieu What do you mean by broken? If you have two encrypted messages, encrypted with the same key but with a different IV and both encrypted messages share one equal ciphertext block, does that make it possible to recover the encryption key? As there is XOR prior to encryption, two equal ciphertext blocks won't mean two equal plaintext blocks; exactly this ECB problem is what CBC avoids, isn't it? $\endgroup$ – Mecki Feb 3 at 10:06
  • $\begingroup$ @Mecki: I was partially in error. Should have said that while CBC and CTR both are not CPA-secure after about $2^{64}$ blocks due to ciphertext block collision, in CBC (not CTR) a collision allows partial decryption (if one of the corresponding plaintext block is known). Fun fact: for both CBC and AES, it is possible to recognize if AES-encrypted file(s) totaling 500 Exabyte have plaintext consisting of a true payload (video..) or zero: a duplicate block is likely for the first kind only. This is mostly theoretical for AES, but problems (some more serious) start at a mere 50 Gigabyte for TDES. $\endgroup$ – fgrieu Feb 3 at 10:36
4
$\begingroup$

Your analysis is mostly correct, yet it ignores the reasons CBC has lost favour. CBC requires padding. And we have seen multiple practical attacks on the padding.

Nounce reuse in CTR is indeed much worse than IV reuse in CBC (which is bad enough).

I've seen implementation where the sender sends a full block length nonce(e.g 128 bit) and how he split it up is up to sender. receiver need not verify the bottom part starts with an appropriate number of trailing zeros. In fact the protocol could work even if we start each message with a fully random nonce with no trailing zeros and increment it.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, just performing $\pmod {2^{128}}$ increments is usual for the counter. The onus of making sure that the counter is not reused is then on the sender - but I guess that's the case anyway. The latter scheme of using the whole IV as random nonce is not a good idea, because it becomes more likely that an overflow occurs and thus that duplicate counters are encountered. Generally how CTR mode is used should be clearly specified in a protocol, and not rely on one party (you don't want to find out that long messages get broken if the counter at the receiver is too small). $\endgroup$ – Maarten Bodewes Feb 1 at 9:50
  • 1
    $\begingroup$ @MaartenBodewes I don't think that's true. I feel like I read that picking fully random starting points for intervals of length n has roughly the same chance of producing overlapping intervals as you'd expect from choosing a random multiple of n as the starting point. (Make n a power of two, then you have the equivalent randomizing high order (nonce) bits and setting low order (counter) bits to zero.) That method gets you more distance between intervals, so you'd think it would help avoid duplicate blocks. You pay for it then, though, because collisions in the random part are more likely. $\endgroup$ – Future Security Feb 3 at 6:04
  • $\begingroup$ @MaartenBodewes I'm not sure if that's what you meant. I wondered if you were suggesting someone mistakenly doing increments mod, say, 2^64. (Not carrying the overflow from the low 64-bit word to the high 64-bit word.) But that doesn't matter either. It would just have the effect of just permuting the order of keystream blocks, those blocks still would be unique if you used no more than 2^64 of them. (As long as overflow on increment just means the register value goes back to zero. That's only a programming problem though.) $\endgroup$ – Future Security Feb 3 at 6:15
  • $\begingroup$ @MaartenBodewes I might be wrong on the claim in my first comment. I don't have a citation and never tried working out the math on my own to prove it to myself. But it's worth pointing out that if interval lengths are much smaller than n then choosing a random multiple of n as a starting point would be worse for avoiding duplicates. So wouldn't a completely random starting point be safer if you don't know all your messages are n blocks long? $\endgroup$ – Future Security Feb 3 at 6:22
  • $\begingroup$ Isn't padding is only an issue if it is predictable? Well, this can easily be avoided if the size of the message is known in advance. Just write the length of the unencrypted message to front before encryption and at the end pad with completely random bytes. That way you can even randomize the padding length to hide the real size of the message. Also if padding was the only disadvantage of CBC, then why not using CFB instead? $\endgroup$ – Mecki Feb 3 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.