Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial

Poly1305 (and GMAC/GHASH) is a *one-time* MAC — tag = (m_1 r^k + ... + m_k r + s) mod 2^130-5 for Poly1305, with (r, s) required fresh per message; reuse the nonce so (r, s) (or GMAC's subkey H) repeats, and the tag equation collapses into a polynomial in the unknown key that two (message, tag) pairs are enough to solve — this is the "forbidden attack" against GCM (Joux) and its Poly1305 analogue.

The signal that betrays it

- ChaCha20-Poly1305 or AES-GCM in the challenge, plus anything implying the nonce isn't actually fresh: "you may encrypt twice", a hardcoded/static nonce or IV, a 12-byte nonce field fed by a counter that resets on service restart or wraps, a retry/resend path that re-encrypts under the same session parameters. - Concretely: the same nonce value attached to two distinct ciphertexts under the same key. That's the whole trigger condition — go looking for it explicitly (grep where the nonce is generated, not just where it's transmitted) rather than assuming randomness is fine. - Contrast with a plain stream cipher: repeated-nonce reuse there (CTR Nonce Reuse — when the counter mode keystream repeats, Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge) leaks only plaintext (many-time-pad). Reuse under a one-time MAC is worse in kind, not just degree — it breaks authentication itself: once the key is recovered you have a full forging oracle, not just a read primitive. - For the AEAD constructions this MAC is embedded in, one nonce collision typically buys you *both* breaks at once, because (r, s) and the encryption keystream derive from the same (key, nonce) computation: in ChaCha20-Poly1305, block counter 0 of the ChaCha20 keystream generates (r, s) and block counter 1 onward encrypts the message, both under the identical (key, nonce). Reusing the nonce hands you the many-time-pad confidentiality break for free alongside the tag-forgery break — don't treat them as two separate findings needing separate exploitation paths.

How to exploit

Core move: subtract the two tag equations computed under the same nonce. The additive pad (s for Poly1305, E_k(J0) — a block-cipher output keyed by the nonce — for GMAC) cancels, leaving a polynomial purely in the unknown authentication key, with coefficients built from the *difference* of the two messages/ciphertexts.

Poly1305 — prime field GF(2^130 - 5): ``python p = 2**130 - 5 # tag_i = sum_j m_block_j * r^(n-j+1) + s (mod p), RFC 8439 block ordering # tag1 - tag2 = sum_j (m1_j - m2_j) * r^(n-j+1) (mod p) -- s cancels # build the coefficient list from the block-wise message difference, then: # R.<x> = PolynomialRing(GF(p)); poly = R(coeffs); poly.roots() ` Do the root-finding in SageMath (GF(p)[x].roots()`) — factoring a polynomial over a 130-bit prime field by hand is not something worth reimplementing.

GMAC/GCM — GF(2^128) with the AES reduction polynomial: the same subtraction cancels the E_k(J0) term, leaving a polynomial in H. Factor over GF(2^128) with the standard pipeline: square-free factorization, then distinct-degree factorization, then equal-degree factorization to reach linear factors. This is the same GF(2)-linear machinery Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2 covers for other bit-level problems.

Disambiguating roots — the step people skip

a degree-d polynomial can have up to d roots, so factoring routinely returns *several* key candidates, not one. Field-tested resolution, in order of preference: 1. Get a third (message, tag) pair under the same nonce and intersect its candidate root set with the first — the true key is the one candidate common to both. 2. If a third pair isn't available, just forge with each candidate against a verifier (or check it reproduces a known tag): wrong candidates produce tags that fail immediately.

Don't stop at "found a root" and assume it's the key — that's the single most common way this attack silently produces a wrong forgery.

Once r/H is known, recover the additive pad by plugging the root back into either original tag equation, then compute a valid tag for any chosen message — that's a complete forging oracle. Hand it off to MAC Forgery — the construction, not the primitive, decides the attack for what to do with it.

What does NOT work

- Trying this with only one `(message, tag)` pair. The entire trick is subtracting two equations to cancel the additive pad; one sample is one equation with two unknowns tangled together and is underdetermined — there's nothing to solve yet. - Trusting the first root found without disambiguation. A wrong candidate looks exactly like a right one until you test it against a third pair or a forge attempt — see above. - Reaching for lattice/HNP machinery here. This is not a partial or biased leak the way biased ECDSA/DSA nonces are (see DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery): an exact nonce collision under a one-time MAC gives *total, immediate* key recovery from two samples, no accumulation of many small-bias samples and no lattice reduction. If you find yourself reaching for HNP tooling on a Poly1305/GMAC nonce-reuse challenge, you've misdiagnosed which technique applies. - Expecting this against a correctly-implemented AEAD. If nonces come from a monotonically-increasing counter that never wraps within the key's lifetime, or from a sufficiently wide random value at a message volume that keeps collision probability negligible (RFC 8439's own 96-bit-random guidance), there is no collision to exploit — the "one-time" requirement is exactly what's being satisfied. Forcing this attack onto data with no actual nonce collision wastes time; look elsewhere for the bug. - Confusing this with hash-based or chaining-based MAC forgery. Poly1305/GMAC are algebraic MACs over a finite field, not Merkle–Damgård hash constructions or block-cipher chains, so Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone and CBC-MAC Forgery — splice a new message onto a known tag without the key techniques (splicing, padding reconstruction) have no purchase here — the nonce-reuse polynomial is the only lever.

Related

MAC Forgery — the construction, not the primitive, decides the attack Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2 CTR Nonce Reuse — when the counter mode keystream repeats Block Cipher Modes of Operation — the mode carries the CTF vulnerability, not the primitive Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone