With AES-CTR does the block input need to be implemented as nonce || counter?

Question

I am looking at an AES-CTR implementation (WebCrypto) and it takes an initialization parameter count which is an array of 16 bytes. It then asks you to specify length, or how many bits are dedicated to the counter (the rest will act as a nonce.) So if you specify e.g. length = 32 the block input will be nonce (96-bit) || counter (32-bit). It then says that the counter should be large enough that it does NOT wrap.

My question is why not just use the full 128-bits as a nonce AND counter. Initialize it with a random 128-bit value and increment the whole thing and as long as you don't wrap all the way to where you began then everything is fine.

https://developer.mozilla.org/en-US/docs/Web/API/AesCtrParams#Properties

Answer 1

CTR mode turns a Pseudo-Random Function (PRF) ( and Pseudo-Random permutation (PRP)) into a stream cipher. Like any stream cipher, this mode is vulnerable to (key, nonce) pair reuse problem that can break the confidentiality. This doesn't mean that the uses key is revealed, CTR mode is CPA secure.

My question is why not just use the full 128-bits as a nonce AND counter. Initialize it with a random 128-bit value and increment the whole thing and as long as you don't wrap all the way to where you began then everything is fine.

This is a little more problematic then nonce||counter since

1. Current state of the counter must be saved and you may end up sending messages to each other using the same counter, failure!.

2. During system failures, you may end up using an old value, failure, too. In this case, exchange a new key.

   The system failure will also affect if the 96-bit nonces when generated sequentially. In such cases, exchanging a new key is a MUST.

3. The second problem is that when the nonce is generated randomly for future usage under the same key, the nonce incrementation of the different nonce may overlap. This is the direct consequence of the incrementation on random values instead of using separated counter section starts from 0.

   For short messages, this is a very low probability and this happens in the AES-GCM if a nonce is provided not equal to have a size of 96 bits. Note that the GCM limits the size up to $2^{32}$ blocks.

   In (96||32) only birthday calculation is for the collision of the nonce when generated randomly. The security bound of nonce+counter is hard to derive.

4. Also, the nonce value may end up near $2^{128}$ which means that the number will round up. This also has a low probability, especially for shorter messages. For message sized up to $2^{32}$ block, it has $1/2^{96}$ probability that the round-up occurs.

5. The long message distinguisher; If CTR mode is initialized with a PRP like the AES, then with the birthday paradox(attack) there will be at least two same message block after $2^{n/2}$ message block with 50% probability. This may be one of the reasons that GCM keep it way below $2^{32}$ blocks per (key,IV) pair. That will make

   $$(2^{k})^2/2^{n}/2=2^{2k-n-1}$$
   with $k=32$ and $n=128$ that aproxiamate $2^{-65}$ collision probability.

The conclusion:

1. The proposed 128-bit nonce has some little more considerations that make the use of the CTR mode is harder.
2. For short messages like the GCM's size, this scheme AES(nonce+counter) is fine.

---

Some notes:

• The 64-bit counter should be enough for all for one encryption that makes 147.573953 exabytes.

• Using a key for a long time is not a good usage, and the correct way to use a key more than once is the proper generation of the nonce.

• The use of nonce enables us to use one key more than once and provides CPA security with probabilistic encryption notion, introduced by Shafi Goldwasser and Silvio Micali in 1984. If you don't use there will be no CPA security at all, too.

• If you want the learn the pros and cons of the CTR mode see this question.

• In modern cryptography, we prefer the authenticated encryption like AES-GCM and its nonce misuse resistant version AES-GCM-SIV and ChaCha20-Poly1305. AES-GCM internally uses CTR mode inside to turn the AES into a stream cipher, similarly the ChaCha. too.

• The GCM has many pitfalls to use. If you are not obligated to use the AES, you may go for ChaCha20-Poly1305 or better xChaCha20-Poly1305 that extends the nonce of ChaCha20 to 192 bits to safely generate the random nonces.

Answer 2

Usually a 128 bit counter is implemented, and the 16 byte IV is really just the initial counter value, consisting of the nonce and a counter. The counter is generally an unsigned value. So your scheme is very possible, but other implementations may make other choices (and if you look at NIST SP 38A, Appendix B, about any scheme suffices).

The fully random IV scheme however has a problem. You never know how close the initial random value is to another initial random value. The chance of two counters out of $N$ counters being close to each other quickly increases with the number of IV's generated.

If you have a incrementing part consisting of $l$ bits then you can have $2^l$ separate counter values before you may run into a collision. There is still a birthday problem, but it is now at least quantifiable, and it's only an issue for the nonce, not for the entire counter. Furthermore, you know exactly how large your message may be.

Let's create an example, which one would you rather have of these initial IV's?

Fully randomized:

27df9ad9921861c7 b53ab03a aad9bf3f
27df9ad9921861c8 dca9d07a 2f50dc18

or nonce || iteration counter:

27df9ad9921861c7 b53ab03a 00000000
27df9ad9921861c8 dca9d07a 00000000

On the first you've got a random amount of counters for each message (in this case 0x84771CD9 or 2,222,398,681), for the second you've got exactly $2^{32}$ counters. Worse, in the first case you don't exactly know how much space you have, because you're not going to store the random values.

The fully random scheme is also somewhat slower as it requires more random bytes. It also requires careful handling of overflows, as you don't want to have an issue after you hit FFFFFFFF.

In short, if the random scheme has any advantage then I'm missing it; I would strongly recommend keeping to a concatenated nonce and counter as input block.