Counter Block Layout and the Nonce Budget in CTR Mode

Counter mode discards the idea of a block cipher as something applied to data. It uses the cipher only to produce pseudorandom bytes, then combines those bytes with the plaintext by XOR. The cipher never sees the plaintext, the plaintext never has to be aligned to a block boundary, and decryption is the identical operation. What the mode gives up in exchange is any notion of the ciphertext being self-contained: the receiver must be able to generate exactly the same byte stream, which means the receiver must know the counter block, which means the counter block has to be communicated and must never be reused.

That requirement is where CTR’s real engineering lives. The primitive is trivial to implement correctly; the nonce discipline around it is where implementations fail, and the failures are catastrophic rather than incremental.

The keystream as a function of position

Fix a key $K$. For a counter block $T_j$ — a full 16-byte block for AES — the keystream block is $S_j = E_K(T_j)$, and the ciphertext block is $C_j = P_j \oplus S_j$. Decryption is $P_j = C_j \oplus S_j$ with the same $T_j$. No inverse permutation is needed, which means the decryption circuit can be identical to the encryption circuit, and on hardware with a single AES pipeline the two directions have the same cost.

Because the operation is XOR, the mode is malleable in a precise way: flipping bit $i$ of ciphertext block $j$ flips bit $i$ of plaintext block $j$ and changes nothing else. There is no error propagation at all, in either direction. For a storage or transport layer that wants bit errors to be detectable by an outer checksum, this is convenient; for a protocol that assumes corruption spreads so that tampering is obvious, it is a hazard. CTR provides confidentiality only, and a single flipped ciphertext bit yields a precisely predicted plaintext change.

The first block is usually treated specially. Rather than encrypting $T_0$ directly, the specification allows an initial counter block to be derived by encrypting a nonce and truncating, but the common construction — used by GCM and by most protocol specifications — is simpler: the initial counter block contains the nonce in its high bits and a counter starting at a defined value in its low bits.

Splitting the block between nonce and counter

A 128-bit block has to hold two things: a value that distinguishes this message from every other message under the key, and a value that distinguishes this block position from every other position within the message. Any fixed split is a trade between the number of messages and the maximum message length.

RFC 3686, which specifies AES-CTR for IPsec ESP, chooses a 32-bit nonce, a 64-bit initial counter block, and a 32-bit block counter, so a single message can be at most $2^{32}$ blocks — 64 GiB — and the nonce space is $2^{32}$ values per key. GCM makes a different choice: a 96-bit nonce and a 32-bit counter, which caps a message at $2^{32}-2$ blocks, about 68 GB, and gives $2^{96}$ nonces. The 96-bit figure is a convention rather than a requirement; GCM also accepts nonces of other lengths, but only the 96-bit form avoids an extra GHASH invocation to derive the initial counter.

The arithmetic is worth doing explicitly because it is the whole design. With $n$ bits of counter, a message cannot exceed $2^n$ blocks, and the receiver must be able to reject a ciphertext that would overflow the counter rather than wrap. A wrap is not a graceful degradation: it reuses keystream within the same message, so two blocks of that message XOR to the XOR of their plaintexts.

#include <string.h>

/* Build the counter block for block index i: 12-byte nonce, then a 32-bit
   big-endian counter. Returns 0 if the counter would overflow. */
static int ctr_block(unsigned char out[16], const unsigned char nonce[12],
                     uint32_t i)
{
    if (i == 0xffffffffu)          /* last value is reserved as unusable */
        return -1;
    memcpy(out, nonce, 12);
    out[12] = (unsigned char)(i >> 24);
    out[13] = (unsigned char)(i >> 16);
    out[14] = (unsigned char)(i >> 8);
    out[15] = (unsigned char)i;
    return 0;
}

The uniqueness requirement, stated exactly

The security claim of CTR is that the keystream blocks $E_K(T_j)$ are indistinguishable from independent random blocks, provided every $T_j$ used across the entire lifetime of the key is distinct. This is a requirement on the set of counter blocks, not per message. Two messages under the same key may not share a single counter block, and within a message no counter block may repeat.

When two messages share a counter block, the two keystreams are equal at that position, so

$$C_1 \oplus C_1’ = (P_1 \oplus S) \oplus (P_1’ \oplus S) = P_1 \oplus P_1’$$

The attacker who has both ciphertexts recovers the XOR of the two plaintexts, with no key and no computation. For structured plaintext — ASCII text, protocol headers, HTML, source code — the XOR of two plaintexts is often enough to read both by crib-dragging, because the attacker can guess one and test the guess against the other. This is the same failure as reusing a one-time pad, and the mode is often described as a one-time pad with a pseudorandom pad; the description is exact, and so is the fragility.

The requirement explains why the nonce must be either randomly generated with enough width that collisions are negligible, or a deterministic counter maintained per key. A 96-bit random nonce gives a collision probability of roughly $q^2/2^{97}$ after $q$ messages under one key; at $2^{32}$ messages that is about $2^{-33}$, and at $2^{48}$ messages it becomes non-negligible. A deterministic counter avoids collisions entirely but requires the counter state to survive crashes and to be coordinated across any replicas that share the key.

Random generation and counting are not interchangeable in their failure modes. A random nonce fails silently with a probability that grows with message count; a counter fails catastrophically if state is restored from a snapshot, because the replay reuses every nonce since the snapshot. Systems that encrypt on many nodes with a shared key usually combine a per-node identifier with a per-node counter, which restores uniqueness as long as the identifier assignment is itself unique.

Length, alignment, and what the mode does not do

CTR has no padding. A plaintext of $L$ bytes produces a ciphertext of exactly $L$ bytes, with the final keystream block truncated. This is the property that made it attractive for protocols that carry length in the clear and for disk encryption, where sector sizes are fixed and expansion is impossible. It also means ciphertext length equals plaintext length exactly, so length-based inference is limited to the message length itself.

The absence of padding removes the padding-oracle class described in the article on CBC padding entirely: there is nothing to check after decryption, so there is no validity signal to leak. But it also removes the last vestige of structure that a receiver could use to detect tampering. A modified CTR ciphertext always decrypts to something, and the receiver has no way to know unless an outer MAC says so.

The conventional composition is therefore encrypt-then-MAC: compute a tag over the ciphertext and the associated data, transmit it, and verify it before decrypting anything. Doing this correctly, including verifying before releasing plaintext, is more subtle than it sounds and is the subject of releasing unverified plaintext. Folding the authentication into the mode itself is what GCM does, and the polynomial hash it uses is described in the GHASH construction; GCM’s counter block is exactly the nonce-plus-counter layout above, which is why GCM inherits CTR’s nonce uniqueness requirement in full and adds a forgery consequence on top of it.

CTR’s other practical constraint is that it parallelises perfectly. Every keystream block is independent, so a hardware implementation can keep several AES units busy, and this is why the mode outperforms CBC encryption by a wide margin on processors with AES instructions. The trade is that the mode has no internal integrity, no error containment, and a hard failure mode — keystream reuse — that is silent, retroactive, and total for the messages involved.