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?

  • $\begingroup$ yes its 64 for nonce and 64 for the counter, each block will hold 128 bit because ew are using AES encryption on each block and the key size would be 256 , $\endgroup$ – geektobe Nov 5 '19 at 8:59
  • $\begingroup$ the result is found in NIST to be the safe mode using this algorithm $\endgroup$ – geektobe Nov 5 '19 at 9:00
  • $\begingroup$ The leading b/2 bits (rounding up, if b is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining m bits to provide an index to the counter blocks for the message.The number of blocks, $n$, in any message must satisfy $n < 2^m$ NIST 800 38s page 26. What is your source? I think you are confusing with AES-GCM! $\endgroup$ – kelalaka Nov 5 '19 at 9:10

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

  • $\begingroup$ Great answer... $\endgroup$ – Woodstock Aug 4 '20 at 15:02
  • $\begingroup$ 2**64 blocks, isn't that (2**64)*16 bytes = 295 EXAbytes? aka 295148 petabytes? why keep it below 1 petabyte then? $\endgroup$ – hanshenrik Oct 22 '20 at 19:01
  • $\begingroup$ @hanshenrik to reduce the advantage of the attacker to a lower probability. Birthday attack calculation is reqired. $\endgroup$ – kelalaka Oct 22 '20 at 19:03

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.