Nonce Construction and the Reuse Limits of AEAD

An AEAD cipher takes a key, a nonce, associated data, and a plaintext, and returns a ciphertext and a tag. The interface is narrow, and almost every misuse of it is a violation of one requirement: for a fixed key, a nonce must never be used twice. The requirement is absolute in a way that key rotation schedules and length limits are not, because a repeated nonce does not degrade security gradually. It fails catastrophically, and the specific failure depends on the mode.

Protocols therefore cannot treat nonce generation as an implementation detail. The nonce construction has to be part of the design, with a stated uniqueness argument that survives counter wraparound, random number generator failure, key reuse across contexts, and connection resets.

RFC 5116 defines the AEAD interface these modes are expected to satisfy, and it makes the nonce requirement explicit at the level of the abstraction: the caller supplies a nonce for each invocation, and the security claims hold only when the nonce is unique per key. Everything below is a consequence of taking that sentence seriously.

What a repeat gives an attacker

For GCM the consequence is the most direct. GCM encrypts by generating a keystream from the counter block, which is built from the nonce and a 32-bit block counter, and authenticates with a polynomial hash keyed by $H = E_K(0^{128})$. Two messages encrypted under the same key and nonce use the same keystream, so their ciphertexts XOR to the XOR of their plaintexts. That alone recovers structure, and with a known or guessed plaintext it recovers the other one outright. Worse, two ciphertext-tag pairs under one nonce give the attacker two equations in the unknown authentication key $H$, and solving them yields $H$; with $H$ known, the attacker can forge tags for arbitrary messages under that key. The failure is not confined to the two affected messages. It extends to the whole key.

ChaCha20-Poly1305 fails differently. The ciphertext is a stream cipher XOR, so nonce reuse again exposes the XOR of plaintexts. Poly1305 keys are derived by encrypting the nonce with the ChaCha20 block function, so a repeated nonce repeats the Poly1305 one-time key, and two tags under one key give the attacker enough to recover the Poly1305 key and forge. Again the damage is to the key, not just the message.

The asymmetry that matters for design is that both modes fail on one repeat, with no grace period. There is no “up to N repeats” allowance, in contrast to the limits on the number of blocks per key, where exceeding the bound degrades the security margin gradually and can be budgeted.

The three constructions and their assumptions

Counter-based nonces. A 32-bit or 64-bit counter, prefixed with a fixed value derived from the connection, gives uniqueness by construction as long as the counter never repeats for a given key. The assumption is that the counter’s state is durable across process restarts and that its width exceeds any plausible number of messages under one key. A 64-bit counter at a million messages per second takes over a hundred thousand years to wrap; a 32-bit counter at the same rate wraps in about an hour. TLS 1.3 uses a 64-bit sequence number per direction, incremented for every record, and XORs it into the per-connection static IV to form the nonce, which is the counter construction with the sequence number as the counter and no wrapping concern within a connection.

Random nonces. A 96-bit random nonce per message gives a collision probability governed by the birthday bound: with $q$ messages, the probability of at least one collision is approximately $q^2 / 2^{97}$. For $2^{32}$ messages that is about $2^{-33}$, which is small; for $2^{48}$ messages it is about $2^{-1}$, which is not. The construction is therefore sound only with a stated message bound per key, and the bound has to be enforced rather than assumed. Random nonces also require a functioning random source at every encryption, which is a different trust assumption from a counter.

XOR-based nonces. A static per-connection IV XORed with a counter or sequence number combines the two: the IV is random, so two connections never share a nonce space, and the counter within a connection guarantees uniqueness even if the IV repeats. The weakness is that XOR is linear, so if the counter values of two connections overlap, the nonce sets overlap exactly when the IVs are equal. TLS 1.3 derives a fresh IV from the traffic secret for each direction and each key epoch, so the IV is pseudorandom under a key the attacker does not know, and the XOR construction inherits the uniqueness of the counter.

A useful sanity check on any of these: write down the maximum number of encryptions under one key, the width of the counter or the entropy of the random value, and the mechanism that prevents the same key being used in two contexts. If any of the three is missing, the construction is incomplete regardless of which mode is used.

/* TLS 1.3 style nonce: static per-key IV XOR 64-bit sequence number. */
static void build_nonce(uint8_t nonce[12], const uint8_t iv[12], uint64_t seq)
{
    for (int i = 0; i < 12; i++)
        nonce[i] = iv[i];
    /* The sequence number occupies the last 8 bytes, big-endian. */
    for (int i = 0; i < 8; i++)
        nonce[11 - i] ^= (uint8_t)(seq >> (8 * i));
}

The loop writes the sequence number into the trailing bytes because that is where the protocol places it; the leading four bytes of the IV remain untouched. An implementation that XORs into the leading bytes produces a valid nonce that no peer can reproduce.

Where the sequence number comes from

The counter must be part of the record layer’s state and must be incremented exactly once per record, in both directions, including for records that are discarded. A receiver that increments only on successful decryption diverges from a sender that increments on every send the moment a record is lost, and the connection fails with a tag error that looks like tampering. This is the intended behaviour: sequence numbers are not recoverable, and a gap is indistinguishable from an attack.

The 64-bit width makes wraparound a non-issue in practice, but the protocol still has to forbid it. TLS 1.3 requires that a connection be terminated before the sequence number wraps, and because the counter is per epoch and each KeyUpdate derives a fresh key and IV, the limit is never approached in a real connection. The rule exists because an implementation that rekeys by resetting the counter without changing the key would silently reuse nonces, and the specification wants that failure to be a protocol error rather than a security bug.

KeyUpdate introduces the case where a counter reset is safe. Each update derives a new traffic secret with the label traffic upd, so the new key and IV are unrelated to the old ones. Resetting the sequence number at that point is correct. What is not correct is deriving a new IV while keeping the old key, or keeping the IV while rotating the key, since either leaves a pair of contexts that share one component.

Key reuse across contexts

The nonce uniqueness requirement is per key, and the most common violation is not within a connection but across them. Three patterns recur.

One key, two directions. If a client and a server both encrypt under a key derived from a single shared secret, and both start their sequence numbers at zero, their nonce sets are identical. Any message from one direction collides with the corresponding message from the other. Deriving a key per direction, as TLS 1.3 does with the client_application_traffic_secret_N and server_application_traffic_secret_N labels, is the fix, and the reasoning is the same as in domain separation and labelled key derivation.

One key, two algorithms. A protocol that uses the same key for AES-GCM in one place and ChaCha20-Poly1305 in another has a key whose nonce space is shared between two modes with different failure characteristics. The fix is a separate derivation per algorithm, not a careful nonce allocator.

One key, resumption. A session ticket contains a PSK, and the PSK is used to derive the early traffic secret for the next connection. If a client resumes twice from the same ticket, the two connections derive early secrets from the same PSK. Because the early secret derivation includes the ClientHello transcript hash, the two secrets differ as long as the ClientHellos differ, which they do because each contains a fresh random and a fresh key share. The uniqueness here rests on the transcript, not on the ticket, and an implementation that cached the early secret across resumptions would break it.

Length limits and the interaction with nonce width

Both AES-GCM and ChaCha20-Poly1305 have per-invocation and per-key limits, and both are stated in terms of blocks or bytes rather than messages. GCM’s 32-bit counter within a message means a single invocation cannot exceed $2^{32}-2$ blocks, which is about 68 GB for a 128-bit block; NIST SP 800-38D sets the per-invocation plaintext limit at $2^{39}-256$ bits for the 96-bit nonce case, which is roughly 64 GiB. The per-key limit on total invocations is $2^{32}$ for random nonces and much larger for deterministic ones.

ChaCha20-Poly1305 in the IETF construction uses a 96-bit nonce and a 32-bit block counter, so a single message is limited to $2^{32}-1$ blocks of 64 bytes, about 256 GiB. The per-key message bound is not a round number taken from the specification but a consequence of the tag-forgery probability: each message yields a Poly1305 tag verification, and the chance that an adversary forges one grows with the number of attempts, so the usable message count per key is set by the forgery probability the application is willing to accept. TLS 1.3 states per-suite usage limits in its record protection section for exactly this reason, and a protocol that does not state a limit has left the bound to the implementer.

These numbers constrain the record layer. A protocol that allows a single record to be a gigabyte has to check the invocation limit explicitly; a protocol that allows unlimited records under one key has to rekey. TLS 1.3 caps records at $2^{14}$ bytes of plaintext plus AEAD expansion, which keeps each invocation far below the mode limit, and relies on KeyUpdate rather than on a message count for the long-run bound.

What to test

The tests that catch nonce bugs are structural rather than statistical. Encrypt two messages under one key with the same nonce and confirm that the ciphertexts XOR to the plaintext XOR, which proves the construction is a stream cipher and that reuse is fatal. Rotate the key and confirm that the nonce is recomputed from the new IV rather than carried over. Interrupt a connection mid-flight, reconnect, and confirm that the sequence number starts at zero under a new key. Derive two traffic keys from one secret with different labels and confirm that neither produces a valid tag under the other’s nonce sequence.

None of these are found by a fuzzer, because each requires the protocol’s state machine to be driven into a specific configuration. They are found by reading the construction and asking where the uniqueness argument comes from, which is why the nonce belongs in the specification rather than in the record layer’s private code. The surrounding decisions about which labels and contexts feed those keys are the ones in domain separation and labelled key derivation, and the confirmation that the key is the right one is the subject of key confirmation ordering.