What is the maximum number of messages that can be encrypted using the same key for CTR mode?

Question

In the counter mode of encryption, the nonce cannot be used again unless a new block cipher key is chosen. What is the maximum number of messages that can be encrypted using the same key?

The maximum length of messages that can be encrypted using the same key under the counter mode is $2^{39} - 256$ bits. I want to make sure am I correct?

Answer 1

You should generally keep the total volume of data encrypted well below $2^{64}$ blocks per key with AES-CTR (or any use of AES)—for example, a petabyte ($2^{50}$) per key is a reasonable limit. This is because AES is slightly defective as a pseudorandom function, which is what ‘CTR mode’ is designed for—it is really a pseudorandom permutation masquerading as a pseudorandom function, with a corresponding minor loss in security proportional to $q^2\!/2^{128}$ after $q$ messages.

AES-CTR specifically entails using $\operatorname{AES}_k(n \mathbin\| c)$ as a block of a one-time pad, where $n$ is a per-message nonce and $c$ is a block counter within the message, so that the concatenation $n \mathbin\| c$ is 128 bits long. Just like the security of a one-time pad goes up in smoke if it's a two-time pad, the security of AES-CTR goes up in smoke if you repeat $n \mathbin\| c$. The size of the nonce $n$ determines a hard limit on the number of messages, and the size of the counter $c$ determines a hard limit on the length of any individual messages.

Different systems use different sizes for $n$ and $c$, but a common reasonable choice, as used in, e.g., AES-GCM, is 96-bit $n$ and 32-bit $c$, which limits messages to $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits. (The extra two blocks are used inside AES-GCM to choose the GHASH key for authentication.) It is generally a bad idea to use very large messages anyway—the largest message size you accept is the largest amount of memory an adversary can waste in a denial of service attack before you can reject a forgery.

(There are also CTR variants that involve the sum $n + c$, where $n$ is chosen pseudorandomly rather than sequentially, instead of the concatenation $n \mathbin\| c$; for example, AES-GCM-SIV does this. But the security story for that is a little more complicated and getting a bit afield from the question.)