GHASH and the Structure of a GCM Tag

Most message authentication codes are built by iterating a compression function over successive blocks, mixing in a key, and reading off a state. GHASH does something different: it evaluates a polynomial whose coefficients are the message blocks, at a point determined by the key. This is not an optimisation or a stylistic choice. It is what lets the authenticator be computed at high speed in a mode where the ciphertext itself is being produced in parallel, and it is also what makes the algebraic attacks on nonce reuse possible.

The design is worth understanding in its own right because it is the standard illustration of a hash keyed by evaluation, and because every parameter of GCM’s tag — its length, its truncation, its handling of partial blocks, its treatment of associated data — is a consequence of the polynomial structure.

The field, and why binary

GHASH operates in the field with $2^{128}$ elements. Elements are 128-bit strings, addition is bitwise XOR, and multiplication is carry-less polynomial multiplication modulo the irreducible polynomial

$$x^{128} + x^7 + x^2 + x + 1$$

written in GCM’s bit-reflected convention. Choosing a field of characteristic two buys three things. Addition is a single XOR instruction. Multiplication maps onto the carry-less multiply instruction that x86 provides as PCLMULQDQ and ARM provides as PMULL, so a 128-bit field multiplication is a handful of instructions plus a reduction. And the reduction polynomial is sparse — four nonzero coefficients below the top term — so the modular reduction is a few shifts and XORs rather than a division.

The trade is that a binary field has no useful notion of ordering or magnitude, so a polynomial over it cannot be evaluated by Horner’s rule using anything cheaper than a full field multiply per block. GHASH therefore costs one field multiplication per 16 bytes of input. On hardware with a carry-less multiplier, that is on the order of a few cycles per block when several blocks are processed in parallel; without one, it is a table-driven software multiplication that is markedly slower than AES itself.

The recurrence

For blocks $X_1 \dots X_m$, GHASH computes $Y_0 = 0$ and $Y_i = (Y_{i-1} \oplus X_i) \cdot H$, with $H = E_K(0^{128})$. Expanding,

$$Y_m = X_1 H^m \oplus X_2 H^{m-1} \oplus \dots \oplus X_m H$$

which is a polynomial in $H$ with the message blocks as coefficients, evaluated at the secret point $H$. If $H$ were a random field element known to nobody, this would be a universal hash: for two distinct messages of the same length, the difference of their hashes is a nonzero polynomial of degree $m$, which has at most $m$ roots, so a random $H$ makes the difference zero with probability at most $m/2^{128}$.

That bound is the heart of the security argument, and it is why GCM’s forgery probability is stated in terms of message length rather than being a flat $2^{-128}$. A forgery attempt succeeds if the attacker’s guessed tag happens to match, or if the polynomial difference happens to vanish at $H$; the latter has probability about $2^{-128}$ times the number of blocks, which for a message of $2^{20}$ blocks is negligible but is not the same number as $2^{-128}$.

The hash key is derived from the cipher rather than generated independently. This keeps the mode a single-key construction, which matters for protocols that derive one key per direction and for hardware that wants one key schedule. It also couples the two halves: any weakness in the cipher that reveals $E_K(0)$ breaks the authenticator, and any nonce reuse that exposes the hash key breaks the cipher’s confidentiality only indirectly, through forged messages.

/* One GHASH step: Y <- (Y xor X) * H in GF(2^128). The multiply is
   carry-less with reduction by x^128 + x^7 + x^2 + x + 1. */
static void ghash_step(uint8_t y[16], const uint8_t x[16],
                       const uint8_t h[16], void (*mul)(uint8_t*, const uint8_t*))
{
    for (int i = 0; i < 16; i++)
        y[i] ^= x[i];
    mul(y, h);                 /* y = y * H, reduction included */
}

The length block and why it exists

A polynomial hash over concatenated blocks has an obvious ambiguity: different splits of the input into blocks, or different combinations of associated data and ciphertext, could produce the same block sequence. If the associated data were hashed as a variable number of blocks followed by the ciphertext as a variable number of blocks, then moving 16 bytes from the end of the associated data to the start of the ciphertext would leave the block sequence unchanged — a length-extension-style collision in the authenticator that would let an attacker shift the boundary between authenticated-but-unencrypted data and encrypted data.

GCM closes this with a final block that encodes the bit lengths: 64 bits for the associated data length, then 64 bits for the ciphertext length. This block is appended before the final multiplication, so it is part of the polynomial and its position is fixed relative to the end. Two inputs with different associated-data or ciphertext lengths now differ in that final block, and the polynomial difference is nonzero. The same technique appears in Merkle–Damgård padding and in CMAC’s length encoding; the point is always to make the encoding of the message length part of the hashed data rather than implicit in the framing.

Associated data is hashed but not encrypted. This is what makes GCM usable for protocols that must authenticate a header — sequence numbers, addresses, protocol versions — while leaving it readable by intermediaries. The cost is that the associated data contributes to the polynomial and therefore to the length-dependent forgery bound, and that an implementation must zero-pad it to a block boundary in exactly the way the specification prescribes, since a different padding convention produces a different tag for the same logical input.

Truncation, and what the tag length means

The full tag is 128 bits. GCM allows truncation to 128, 120, 112, 104, or 96 bits, and to 64 or 32 bits under restrictions. Truncation is not a linear loss of security in a useful sense: an attacker forging by guessing succeeds with probability $2^{-t}$ per attempt for a $t$-bit tag, but the algebraic route through the polynomial is unaffected by truncation, since the attacker only needs the truncated tag to set up the difference equation.

The 32-bit case is the one with practical consequences. At $2^{-32}$ per attempt, an attacker making $2^{20}$ forgery attempts has roughly a $2^{-12}$ chance of success — which sounds small, but the attempts can be cheap and parallel, and the target is not a single message but any message the receiver will accept. NIST’s guidance limits 32-bit and 64-bit tags to constrained environments and short messages, and requires the deployment to bound the number of failed verification attempts. The binding constraint is not the tag length alone but the product of tag length and the number of attempts an adversary can make.

There is a second truncation hazard specific to how tags are compared. Verification must compare the full received tag against the computed one in constant time. A byte-by-byte comparison that returns early on the first mismatch leaks the length of the matching prefix, which over many attempts allows the tag to be recovered a byte at a time — the same shape of attack as the CBC padding oracle described in the padding oracle article, applied to a different comparison. Libraries that expose a tag comparison primitive generally implement it with a constant-time equality function for this reason.

Where GHASH sits relative to other authenticators

A CBC-MAC, and its length-hardened variant CMAC, chains the block cipher: each block is encrypted under the previous output. That construction is sequential — block $i$ depends on block $i-1$ — and it reuses the cipher’s decryption or encryption circuit for every block of the message. GHASH is parallel across blocks when the field multiplications are, since the polynomial can be evaluated with a tree of partial products rather than a chain, and it uses a separate, much cheaper arithmetic unit. The result is that GCM’s authentication cost is small relative to its encryption cost, whereas a CBC-MAC roughly doubles the cipher work.

The price of that choice is algebraic structure. A CBC-MAC has no known efficient attack from a repeated input beyond the generic ones; GHASH’s polynomial form is exactly what allows the nonce-reuse attack in recovering the GCM authentication key to reduce key recovery to root-finding. Structure that makes a function fast and parallel also makes it analyzable, and GCM’s design accepted that trade because the nonce discipline was supposed to make the algebraic route unreachable. Constructions that do not rely on that assumption, such as the synthetic-IV modes in SIV and deterministic authenticated encryption, use a keyed hash over the plaintext to derive the nonce instead of trusting the caller to supply a fresh one.

GHASH also has a length-dependent cost that shows up in hardware design: a very long message is a high-degree polynomial, and the forgery bound grows with the degree. The mitigation is the same as for the nonce — keep messages to a size where the bound stays negligible, which in practice means well under the $2^{32}$-block counter limit, and in protocol design means bounding record sizes rather than letting a single AEAD invocation span an arbitrary stream.