Recovering the GCM Authentication Key from a Repeated Nonce

Reusing a CTR nonce leaks the XOR of two plaintexts. Reusing a GCM nonce is worse: it leaks the authentication key, and with it the ability to forge any message under the key with a valid tag. The difference is structural. In GCM the same nonce determines both the keystream and the input to the polynomial hash, and the tag is the one place where the secret hash subkey appears in a form an attacker can manipulate algebraically.

The recovery is not a search over $2^{128}$ values. It is a root-finding problem on a polynomial whose degree equals the number of blocks in the shorter message, and it completes in time polynomial in that degree. A repeated nonce is therefore not a degradation of security; it is the end of authentication for that key.

What the tag is a function of

GCM encrypts with CTR using a counter block derived from the nonce, and authenticates with GHASH, a polynomial evaluation over the field $\mathrm{GF}(2^{128})$ with a fixed irreducible polynomial. The hash subkey is $H = E_K(0^{128})$ — the encryption of the all-zero block, which the attacker never sees but which is fixed for the key.

GHASH processes a sequence of 16-byte blocks $X_1, \dots, X_m$ as

$$Y_0 = 0, \qquad Y_i = (Y_{i-1} \oplus X_i) \cdot H$$

so by induction the final value is $Y_m = \sum_{i=1}^{m} X_i H^{m-i+1}$. The blocks are the associated data, then the ciphertext, then a final length block encoding the bit lengths of both. The tag is

$$T = \mathrm{GHASH}_H(A, C) \oplus E_K(J_0)$$

where $J_0$ is the initial counter block, which for a 96-bit nonce is the nonce followed by the 32-bit value 1. The tag is then truncated to the configured length, most commonly 128 bits.

Two facts about this structure drive the attack. The term $E_K(J_0)$ depends only on the key and the nonce, so it is identical for two messages that share a nonce. And $\mathrm{GHASH}_H$ is a polynomial in $H$ with coefficients that are entirely public — the attacker knows the associated data and the ciphertext, and therefore knows every $X_i$.

Differencing two tags

Take two messages with the same nonce, ciphertexts $C$ and $C’$, associated data $A$ and $A’$, and tags $T$ and $T’$. XOR the tags:

$$T \oplus T’ = \mathrm{GHASH}_H(A, C) \oplus \mathrm{GHASH}_H(A’, C’)$$

because $E_K(J_0)$ cancels. The right-hand side is a polynomial in $H$ over $\mathrm{GF}(2^{128})$ with known coefficients, and its value is known. The attacker now has a polynomial equation $f(H) = 0$ and needs its roots.

Over a field of characteristic two, XOR is addition, so the difference of two GHASH evaluations is the GHASH of the XOR of the inputs, taken block by block with length blocks aligned. Concretely, if both messages are $m$ blocks including the length block, then

$$f(H) = \sum_{i=1}^{m} (X_i \oplus X_i’) H^{m-i+1}$$

Each coefficient $X_i \oplus X_i’$ is computable from public data. The zero coefficients at positions where the two messages agree drop out, which is why the degree is often much smaller than $m$ — and why the attack is cheapest when the two messages are similar in length and differ in few blocks.

Finding the roots

A polynomial of degree $d$ over $\mathrm{GF}(2^{128})$ has at most $d$ roots, and they can be found without any search over the field. The standard method uses the fact that the roots of $f$ are exactly the common roots of $f$ and $x^{2^{128}} - x$, since every element of the field satisfies the latter. Computing $g = \gcd(f, x^{2^{128}} - x)$ isolates the product of the distinct linear factors of $f$. The remaining work is splitting $g$ into linear factors, which is done with a randomized equal-degree factorization: pick a random polynomial $a$, compute $\gcd(g, a^{(2^{128}-1)/2} - 1)$, and recurse on the two factors. The expected number of splits is small, and the arithmetic is in a field where multiplication is a handful of carry-less multiplies plus a reduction.

The practical consequence is the number that matters: the cost grows with the degree, not with the field size. A pair of short messages — a few blocks — produces a polynomial of degree in the single digits, and the roots are found almost immediately. Implementations of the attack exist as short scripts; the algebra is textbook finite-field computation rather than a cryptanalytic tour de force.

Because the field is large, $f$ usually has exactly one root in the field, and the degree-$d$ bound means there are at most $d$ candidates. Verifying a candidate costs one GHASH evaluation against a third message under the same nonce, or against a message under a different nonce once $E_K(J_0)$ has been recovered. The verification step is what turns a candidate into a certainty.

# Outline only: roots of the differenced GHASH polynomial.
# field ops: mul(a, b), add(a, b) == a ^ b, pow_x_2_128_minus_x()
def candidate_hash_keys(f, field):
    g = field.gcd(f, field.x_to_q_minus_x())      # product of linear factors
    return field.split_into_linear_factors(g)     # at most deg(f) candidates

From the hash key to arbitrary forgery

Once $H$ is known, the attacker computes $\mathrm{GHASH}_H(A, C)$ for any chosen associated data and ciphertext, because that computation needs no key material beyond $H$. It also recovers $E_K(J_0)$ from the tag of either observed message, since $E_K(J_0) = T \oplus \mathrm{GHASH}_H(A, C)$. With both pieces, the tag for a new message under the same nonce is directly computable:

$$T_{\text{new}} = \mathrm{GHASH}H(A{\text{new}}, C_{\text{new}}) \oplus E_K(J_0)$$

The attacker can therefore modify a ciphertext — flipping bits in the plaintext it controls, extending it, replacing it entirely — and attach a tag that verifies. No key recovery is needed for the block cipher itself, and the forgery does not require the receiver to reveal anything beyond the tags it normally sends.

For nonces other than the one that repeated, the attacker does not know $E_K(J_0)$ and cannot forge. But the same nonce will recur in any system that generates it badly, and in systems that use a counter, a crash-and-restore event produces exactly this situation for a whole range of nonces.

Why this failure mode is common

The repeated nonce arises from three patterns, and none of them involves a broken cipher. Random 96-bit nonces collide when enough messages are produced under one key, with the birthday bound making the collision probability noticeable well before $2^{96}$ messages — at $2^{32}$ messages the chance is on the order of $2^{-33}$, and the risk is a per-key, cumulative quantity that no single message reveals. Deterministic counters reuse nonces after a state rollback, after a clone of a virtual machine, or when two hosts share a key and each maintains its own counter. And protocol-level reuse, where an implementation derives the nonce from a sequence number that wraps or repeats, has occurred in deployed TLS stacks.

The mitigation is at the mode level rather than the implementation level. AES-GCM-SIV, specified in RFC 8452, derives the counter and the hash key from a synthetic IV computed over the plaintext with a keyed hash, so a repeated nonce costs the attacker only the ability to tell whether two messages were identical — the plaintext XOR leak and the hash-key recovery both disappear. That construction, and the general class of misuse-resistant modes, is covered in SIV and deterministic authenticated encryption. For plain GCM, the discipline is the same as for CTR: uniqueness of the counter block set across the key’s lifetime, as described in the CTR counter layout, with the added consequence that a violation compromises authenticity as well as confidentiality.

GCM’s tag length is a separate and independent parameter with its own failure modes. A 32-bit tag permits a forgery with probability $2^{-32}$ per attempt, which is far too high for a protocol that answers many attempts; NIST’s guidance restricts short tags accordingly, and the reasons are discussed in the GHASH tag construction. The nonce, though, is the parameter whose misuse is silent and unrecoverable: no amount of tag length compensates for a repeated counter block once the polynomial has been written down.