What happens if you increment MAX counter in AES-CTR?

Question

Suppose you use a IV/counter = ffffffffffffffffffffffffffffffffin AES-CTR. What will happen if you encrypt the next block, and thereby increment the counter by one? Will it result in an overflow error of sorts?

Answer 1

In AES-CTR, the ‘IV’ and ‘counter’ are different concepts. To encrypt a message, you specify a nonce, like a message sequence number—sometimes called an ‘IV’. The nonce is usually 64 or 96 bits, but it could be anywhere from 0 to 128 bits long. For security, you must never reuse a nonce with a key. The length of the nonce for the particular AES-CTR system you're using determines the maximum message length: inside AES-CTR, the remainder of a 128-bit string after filling part of it with a nonce is used to count blocks within a message.

So, for example, if you send the message $m_1 \mathbin\| m_2 \mathbin\| m_3$, and then the message $m'_1 \mathbin\| m'_2$, you might in your protocol choose the nonce 42 for the first message, and the nonce 69 for the second, and the ciphertexts will be internally computed as:

\begin{align} c &= \bigl(m_1 \oplus \operatorname{AES}_k(42 \mathbin\| 0)) \mathbin\| (m_2 \oplus \operatorname{AES}_k(42 \mathbin\| 1) \mathbin\| (m_3 \oplus \operatorname{AES}_k(42 \mathbin\| 2)\bigr), \\ c' &= \bigl(m'_1 \oplus \operatorname{AES}_k(69 \mathbin\| 0)) \mathbin\| (m'_2 \oplus \operatorname{AES}_k(69 \mathbin\| 1)\bigr). \end{align}

(Here the $m_i$ and $m'_i$ are exactly 128 bits long apiece; it is inside AES-CTR that the block counter 0, 1, 2, …, is maintained.)

For (say) AES-CTR with a 96-bit nonce, the maximum message length is $2^{32}$ 128-bit blocks, or $2^{36}$ bytes. What happens if you try to encrypt a $(2^{36} + 1)$-byte message? It's simply not defined in that case—like dividing by zero. You should avoid designing a protocol in which this question might even arise; what an implementation might do may vary: it could silently wrap around, effectively encrypting messages with a two-time pad; it could fail noisily and abort the computation; it could make demons fly out of your nose.

What if you use a 0-bit nonce, so that the maximum message length is $2^{128}$ 128-bit blocks, or $2^{132}$ bytes? You don't have that many bytes and you don't have enough time to wait for all the computers in the world to encrypt that many bytes.

What if—internal block counter aside—you use a 64-bit message sequence number as a nonce? Will you have to worry about wrapping around? Hint: You are doing this in sequence. Let's say it takes you a nanosecond to encrypt each message. How many centuries do you have to wait for a 64-bit message counter to overflow?

Answer 2

What do you expect to generate the overflow error? The AES function certainly doesn't know about the way you construct the 16 byte cleartext block.

AES-CTR is usually done with 64 bits of nonce and 64 bits of counter, so it will overflow much sooner, after $ 2^{64} - 1 $. The counter value will either wrap around, or raise an error / throw an exception, or will just become $ 2^{64} $ and then $ 2^{64} + 1 $, depending on the programming language you use (sometimes, depending on whether you're compiling in debug or release mode!).

For C unsigned integer type like uint64_t, it will wrap around to 0. For a hypothetical signed C type that is big enough to fit that value, because signed overflow is undefined, the compiler is allowed to generate whatever code it wants (this would be very bad).

Java plain doesn't have unsigned 64 bit ints, only signed ones, but the language spec says what happens to them at overflow.

Python has only bigints (no fixed sized ints except as part of typed arrays), so it will happily be a 65 bit value (or a 6,500 bit value).

Consult your programming language reference manual (or CPU ISA manual if programming in assembly).

Depending on your authentication scheme or AEAD, you don't want to wait for that counter to wrap around, because you are supposed to re-key earlier. For example AES-GCM should use 96 bits nonce and 32 bits counter, for reasons.

Answer 3

To ignore the (important) security issues and to just answer the question:

It depends. The 128-bit block can be separated into a "nonce" and a "counter", and then you would wrap around only on the counter. For example, if the counter is 32 bits, then you would go back to ffffffffffffffffffffffff00000000.

However, the vast majority of implementations see the entire block as a counter, therefore you would go back to 00000000000000000000000000000000.