# The Tag Verified, the Cipher Held, the Forgery Went Through: A Field Guide to Message Authentication and Safe Composition

> Why HMAC, KMAC, GMAC, and Poly1305 never broke -- but Flickr, Lucky Thirteen, and 184 GCM servers did. A field guide to MACs and Encrypt-then-MAC.

*Published: 2026-07-10*
*Canonical: https://paragmali.com/blog/the-tag-verified-the-cipher-held-the-forgery-went-through-a-*
*© Parag Mali. All rights reserved.*

---
<TLDR>
A MAC makes forgery hard; three deployment assumptions keep it hard, and every famous break -- Flickr [@flickr-advisory], Lucky Thirteen [@cve-2013-0169], POODLE [@cve-2014-3566], the SSH plaintext-recovery attack [@apw-2009], and 184 nonce-repeating HTTPS servers [@woot16-bock] -- broke one of those assumptions, not the math. Pick the right family (PRF-based HMAC and KMAC take a reusable key and need no nonce; Wegman-Carter GMAC and Poly1305 run at line rate but demand a one-time key [@wc-1981]), verify in constant time, and always Encrypt-then-MAC over the ciphertext with an independent key and a strongly unforgeable tag [@bn-2000]. This guide traces the primitive from Carter-Wegman universal hashing in 1979 [@cw-1979] to committing AEAD in 2025 [@rfc-9771], names every failure by root cause, and ends with a decision tree and a paste-in review checklist. The one rule underneath all of it: authenticate the ciphertext, the length, and the context -- not just the message.
</TLDR>

## 1. A Forgery Without a Broken Cipher

In 2009, two researchers forged valid Flickr API signatures without knowing Flickr's secret key, without finding a single MD5 collision, and without touching a cipher [@flickr-advisory]. Flickr had done what feels obviously correct -- prepend a secret to each request and hash the result -- and that one instinct silently handed signing power to anyone who had ever seen a single signed URL. The hash worked exactly as designed. The way Flickr *used* it was the vulnerability.

That gap -- between a primitive that is sound and a deployment that is not -- is the subject of this article, and it is worth stating as a claim you can test against every page that follows.

> **Key idea:** A message authentication code makes forgery hard; keeping it hard is the surrounding protocol's job. Every deployed MAC ships a proof, and every proof quietly assumes three things the deployment must supply: (1) the right **key discipline** for its family, (2) a **constant-time verify**, and (3) **composition over the right bytes, in the right order, binding the right context**. Read that way, the entire failure catalogue is one sentence repeated -- the math never broke; a deployment broke one of these three assumptions.

Before we can prove that thesis, we need the object it is about. Informally, a MAC is a small tag you attach to a message so the receiver can tell the message came from someone who holds the shared secret key, and that nobody altered it in transit.

<Definition term="Message Authentication Code (MAC)">
A MAC is a keyed algorithm that takes a secret key and a message and produces a short fixed-size tag. Anyone holding the same key can recompute the tag to verify that the message is authentic and unmodified. Unlike a plain hash, a MAC is keyed, so an attacker without the key cannot produce a valid tag; unlike a digital signature, the same secret both makes and checks the tag, so there is no public verifiability and no non-repudiation.
</Definition>

Now pair Flickr with a second break that fails a *different* assumption. In 2013, Lucky Thirteen recovered plaintext from TLS connections that used a perfectly correct HMAC -- the attack timed *how* the MAC was checked, not whether the MAC was strong [@cve-2013-0169]. Two production systems, two respected primitives, two failures -- and in neither case did the cryptography break. Flickr fed the hash the wrong bytes in the wrong construction; TLS checked a correct tag on a timing-leaky path.

> **Note:** MD5 is badly broken for collision resistance, yet the Flickr forgery did not use a collision. HMAC was and is unbroken, yet Lucky Thirteen still bled plaintext. In both cases the primitive met its specification and the deployment violated an assumption the specification silently depended on. Hold onto that pattern -- it is the whole catalogue in miniature.

By the end of this field guide you will have a decision procedure and a review checklist that catch every failure in this article before it ships.<Sidenote>The original Flickr advisory by Duong and Rizzo is no longer served from its source host; the citation here points to a 2009 Wayback Machine snapshot, which is the durable primary record [@flickr-advisory].</Sidenote> But a checklist without the underlying model is just cargo-culting. So start with the model. If the hash was not broken, what exactly is a MAC supposed to promise, and against whom?

## 2. What a MAC Actually Is

Strip away the mystique and a MAC is three algorithms and one game.

The three algorithms are `KeyGen`, `Tag`, and `Verify`. `KeyGen` samples a secret key $k$. `Tag` maps a key and a message $m$ to a tag $t$. `Verify` takes $k$, $m$, and a candidate $t$ and returns accept or reject. The whole design question is: how hard is it for someone without $k$ to make `Verify` say accept on a message the key-holder never authorized?

"How hard" was made precise in 1988. Shafi Goldwasser, Silvio Micali, and Ronald Rivest gave the first rigorous adversarial definition of authentication -- existential unforgeability under adaptive chosen-message attack -- while analyzing digital signatures, and MACs inherit it directly [@gmr-1988]. The game is deliberately generous to the attacker.

<Definition term="Existential Unforgeability (EUF-CMA)">
The adversary may ask for tags on any messages it likes, adaptively, as many as it wants. It wins if it then outputs a valid tag on any *new* message it never queried. A MAC is EUF-CMA secure if every efficient adversary wins only with negligible probability. The name is exact: "existential" means the forgery can be on any message the attacker chooses, and "adaptive chosen-message" means it sees each answer before picking its next query.
</Definition>

EUF-CMA is the usual bar, but composition needs a slightly stronger one, and the difference will decide whether a whole protocol stands or falls in Section 6.

<Definition term="Strong Unforgeability (SUF-CMA)">
SUF-CMA forbids even a *new tag on an old message*. The adversary wins if it outputs any message-tag pair that verifies and was not itself the result of a tag query -- including a second, different valid tag on a message it already asked about. Every SUF-CMA MAC is EUF-CMA, but not conversely: a MAC with malleable tags can be existentially unforgeable yet still let an attacker maul a valid tag into another valid tag.
</Definition>

Formally, if we write the tag oracle as $\mathsf{Tag}_k(\cdot)$ and let $Q$ be the set of message-tag pairs it returned, the strong-forgery advantage is

$$\mathsf{Adv}^{\text{suf-cma}}_{\mathsf{MAC}}(\mathcal{A}) \;=\; \Pr\!\left[\,(m,t) \leftarrow \mathcal{A}^{\mathsf{Tag}_k(\cdot)} : \mathsf{Verify}_k(m,t)=\text{accept} \;\wedge\; (m,t)\notin Q\,\right].$$

A MAC is good when this probability stays negligible for every efficient $\mathcal{A}$. That single inequality is the promise Flickr's construction could not keep -- an attacker produced an accepted tag on a message that was never in $Q$.

Four primitives live near this definition, and confusing them is the source of real bugs. An **unkeyed hash** has no $k$, so anyone can recompute it -- it detects accidental corruption, never a motivated forger; this series covers hashes and their length-extension quirk in Part 10.

A **MAC** is symmetric: the same secret makes and checks the tag. A **digital signature** is asymmetric -- a private key signs, a public key verifies -- which buys public verifiability and non-repudiation that a MAC deliberately does not provide (Part 3 develops [what the authenticated bytes must actually cover](/blog/the-signature-was-valid-the-message-was-forged-a-field-guide/)). An **AEAD** bundles a MAC together with encryption so one call delivers secrecy and integrity at once; Part 7 is [the decision matrix for choosing among AEADs](/blog/the-aead-decision-matrix-seven-ciphers-three-edges-one-choic/), and this article is the authentication half underneath it.

> **Note:** Because a MAC key both signs and verifies, a valid tag proves only that *someone holding the shared key* produced it -- it cannot tell you *which* party, and it cannot be shown to a third party as proof. If you need "Alice, and only Alice, provably sent this," you need a signature, not a MAC. Reaching for a MAC where you needed non-repudiation is a design error no amount of key length fixes.

The definitions say a good MAC is unforgeable. Yet the very first keyed MACs people built were forgeable in ways the definition had not yet been written to outlaw. Stranger still, the airtight, provably unforgeable answer arrived *before* the practical, broken ones. Where did the idea come from?

## 3. Origins: Universal Hashing and One-Time Authentication

Here is the twist that reorders the whole story. The provably secure MAC was invented first, in 1979 and 1981, and then the field spent two decades shipping forgeable ones anyway. Keep that inversion in mind as the arc unfolds.

<Mermaid caption="The message-authentication arc, 1979 to 2025: the provable answer arrived first, followed by two decades of deployment breaks.">
timeline
    title Message authentication, 1979 to 2025
    1979 : Carter-Wegman universal hashing
    1981 : One-time authentication, tag is hash plus one-time pad
    1985 : CBC-MAC standardized in FIPS 113
    1996 : HMAC nests the hash to stop length extension
    2000 : Encrypt-then-MAC formalized by Bellare and Namprempre
    2001 : Krawczyk indicts the SSL and SSH orderings
    2004 : GMAC revives Wegman-Carter at line speed
    2005 : Poly1305 brings it to fast software
    2006 : HMAC proven a PRF without collision resistance
    2009 : Flickr forgery and the SSH plaintext recovery
    2013 : Lucky Thirteen timing oracle
    2016 : KMAC keyed sponge and 184 nonce-repeating servers
    2018 : TLS 1.3 record layer becomes AEAD-only
    2023 : Terrapin breaks a correct channel
    2025 : RFC 9771 standardizes commitment vocabulary
</Mermaid>

The starting point is a purely combinatorial object. Larry Carter and Mark Wegman, at IBM Research, asked what happens if you pick a hash function at random from a carefully built family, rather than fixing one function everyone knows [@cw-1979].

<Definition term="Universal Hash Function">
A universal family of hash functions has the property that, for any two fixed distinct inputs, a function drawn uniformly at random from the family maps them to the same output with only small, bounded probability. The bound comes from counting the functions in the family, not from any assumption about how much computing power an attacker has. It is combinatorial security, not cryptographic security -- which is exactly why it needs no unproven hardness conjecture.
</Definition>

Two years later, Wegman and Carter turned that object into an authenticator [@wc-1981]. The construction is startlingly small: draw a secret hash $h$ from a strongly universal family, draw a secret one-time pad $s$, and send

$$t \;=\; h(m) \,\oplus\, s.$$

The pad $s$ hides the value $h(m)$ completely, like a one-time pad hides a plaintext, and the universal property bounds an attacker's chance of guessing a valid tag for a *different* message. The result is unconditional: it holds against an adversary with unlimited computing power, assuming nothing about factoring, discrete logs, or the strength of any cipher.

<Definition term="Wegman-Carter One-Time Authentication">
Authenticate a message as the exclusive-or of a universal hash of the message and a fresh secret pad: the tag reveals nothing about the hash key, and forging a tag on a new message requires guessing a value the universal bound keeps small. The security is information-theoretic and tight -- but the pad must be used exactly once. Authenticate a second message under the same pad and the guarantee evaporates.
</Definition>

Take the smallest instance. Fix a prime $p$, keep a secret pair $(a, b)$, and tag a message $m$ as $t = (a\cdot m + b) \bmod p$. An attacker who sees one pair $(m_1, t_1)$ learns one linear equation in two unknowns; every candidate slope $a$ has exactly one consistent $b$, so the tag on any different $m_2$ stays uniform over all $p$ values. The best forgery succeeds with probability $1/p$. Beautiful, and useless twice: a second pair $(m_2, t_2)$ gives a second equation, the line is pinned, and every future tag is computable.

> **Note:** "One-time" is not a restriction bolted onto Wegman-Carter authentication -- it *is* the security proof. The pad's single use is what buys the information-theoretic guarantee. That makes it a feature in 1981 and a landmine in 2004, when the same construction is revived at network line speed and a fast deployment reuses the pad. Every GMAC and Poly1305 nonce rule you will ever read is this 1981 constraint wearing modern clothes.

So the airtight answer existed. Yet it authenticates only one message per key, which is impractical for a general-purpose MAC.<Sidenote>The two ideas are separate papers: the 1979 work introduced universal classes of hash functions as a combinatorial tool [@cw-1979]; the 1981 follow-up applied them to authentication and set equality [@wc-1981]. Universal hashing came first; authentication was the application.</Sidenote> If the unconditional construction was this good but this restrictive, what did engineers reach for instead -- and why did the "obvious" keyed hashes they built break?

## 4. Early Approaches and Why They Broke

When engineers needed a keyed MAC in the 1990s, most reached for the hash they already had and glued a secret to it. The most natural glue is to put the key in front: compute `H(secret || message)` and ship the digest as the tag. It looks unforgeable -- you cannot compute the hash without the secret. It is also exactly what Flickr shipped, and it is broken by a property of the hash that has nothing to do with its collision resistance.

The property is length extension, and it is a direct consequence of how Merkle-Damgard hashes -- MD5, SHA-1, and most of SHA-2 -- are built [@length-ext-wiki]. Such a hash absorbs the message block by block into an internal state, and it emits *that entire internal state* as the digest. The digest is therefore a complete, resumable snapshot: given `H(secret || message)`, you can set a fresh hash's state to that value and keep absorbing more bytes, as if you had known the secret all along.

<Definition term="Length Extension Attack">
Given the digest of `secret || message` and the length of the secret, an attacker can compute the digest of `secret || message || padding || extra` for attacker-chosen `extra`, without knowing the secret. The attack works because a Merkle-Damgard digest is the hash's full internal state, so it can be resumed. The only wrinkle is the glue `padding` the original hash appended internally, whose bytes are fully determined by the known lengths.
</Definition>

The forgery is mechanical once you see the state as resumable.

<Mermaid caption="Secret-prefix length extension: the attacker resumes the Merkle-Damgard state carried in the tag and appends new data, forging a valid tag with no key.">
sequenceDiagram
    participant A as Attacker
    participant V as Verifier
    A->>V: Observe one signed request, message m and tag t
    Note over A: The tag t is the full hash state after absorbing key and m
    A->>A: Resume from t, append glue padding then chosen extra bytes
    A->>A: Keep hashing to get t2 for the extended message, no key used
    A->>V: Submit extended message with tag t2
    Note over V: Verifier recomputes over key plus the extended message
    V-->>A: State matches, forged request accepted
</Mermaid>

The demonstration below builds a toy Merkle-Damgard hash whose digest is its internal state -- the essential property -- and forges a secret-prefix tag with no secret, then shows that nesting the hash (the HMAC idea) shuts the door.

<RunnableCode lang="python" title="Secret-prefix MAC is forgeable by length extension; nesting fixes it">{`
# Toy Merkle-Damgard hash: absorb one byte at a time; the digest IS the state.
# (The mixer is illustrative, not secure -- the STRUCTURE is the point.)
def compress(state, byte):
    return ((state * 1000003) ^ byte) & 0xFFFFFFFFFFFF   # 48-bit toy state

def toy_hash(data, iv=0xA5A5A5A5A5A5):
    state = iv
    for byte in data:
        state = compress(state, byte)
    return state                      # digest == resumable internal state

secret = b"opensesame"                # attacker does NOT know this...
def prefix_mac(msg):                  # ...but does know len(secret) == 10
    return toy_hash(secret + msg)

# 1) Attacker observes ONE legitimate (message, tag) pair:
seen = b"amount=10"
tag  = prefix_mac(seen)

# 2) Attacker resumes from the tag and appends -- the secret is never touched:
extra = b"&amount=1000000"
forged = tag
for byte in extra:
    forged = compress(forged, byte)

# 3) The verifier recomputes over secret + (seen + extra):
print("secret-prefix forgery accepted:", forged == prefix_mac(seen + extra))

# The HMAC-style fix: nest, so the outer pass re-absorbs the inner digest.
def nested_mac(msg):
    inner = toy_hash(secret + msg)
    return toy_hash(secret + inner.to_bytes(6, "big"))

resumed = nested_mac(seen)
for byte in extra:
    resumed = compress(resumed, byte)
print("nested (HMAC-style) forgery accepted:", resumed == nested_mac(seen + extra))
`}</RunnableCode>

The first line prints `True`, the second `False`. That single flip is the difference between the Flickr construction and HMAC, and it is Aha number one for this article.

> **Note:** `H(secret || message)` over any Merkle-Damgard hash is not a MAC. It authenticates nothing an attacker who has seen one tag cannot forge, regardless of how strong the underlying hash is. MD5's collision weakness is irrelevant here -- the Flickr forgery used no collision at all [@flickr-advisory]. If you find `md5(secret + data)` or `sha256(secret + data)` in a code review, you have found a length-extension forgery waiting to happen.

The mirror construction, secret-suffix `H(message || secret)`, resists length extension because the secret is absorbed last.<Sidenote>Secret-suffix is not safe either: since an attacker who finds two messages colliding under the raw hash gets a tag collision for free, `H(m || k)` reduces to the hash's collision resistance, so it dies with MD5 and SHA-1 -- the opposite failure mode from secret-prefix, same verdict [@length-ext-wiki].</Sidenote> Neither ad-hoc glue is a MAC.

The block-cipher world made a parallel mistake. CBC-MAC, standardized as FIPS 113 in 1985, runs a block cipher in CBC mode with a zero IV and keeps the final ciphertext block as the tag [@fips-113]. It carries an unstated assumption: every message is the same fixed length. Bellare, Kilian, and Rogaway turned the failure of that assumption into a theorem in 1994 -- secure for fixed-length messages, trivially forgeable once lengths vary [@bkr-1994].

The splice is mechanical. Query the tag of a one-block message $m_1$ to get $t_1 = E_k(m_1)$; then the two-block message $m_1 \,\Vert\, (m_1 \oplus t_1)$ has tag $E_k\big((m_1 \oplus t_1)\oplus t_1\big) = E_k(m_1) = t_1$ -- a valid tag on a message never queried, produced with no key.

Both failures teach the same lesson, and it organizes the rest of this guide: *a raw hash is not a MAC, and raw CBC-MAC is not a MAC for variable-length messages.* Both fixes point the same direction -- stop exposing resumable internal state, and make the tag depend on length. From here the field split into two lineages. Which one wins?

## 5. The Evolution: Two Lineages Diverge

The field did not pick one winner. It split into two families that both survive today, and choosing between them is still the single most consequential decision a practitioner makes about authentication. One family keeps a computational assumption and buys a reusable key; the other keeps the 1981 one-time pad and buys blazing speed.

### The PRF lineage: HMAC and CMAC

Bellare, Canetti, and Krawczyk fixed the secret-prefix disaster in 1996 by nesting the hash so the attacker never sees a resumable inner state [@bck-1996]. Standardized a year later as RFC 2104, HMAC computes two keyed passes [@rfc-2104]:

$$\mathsf{HMAC}(k, m) \;=\; H\big((k \oplus \text{opad}) \,\Vert\, H((k \oplus \text{ipad}) \,\Vert\, m)\big).$$

The outer hash re-absorbs the inner digest, so a resumed inner state is useless -- length extension cannot reach the output.

<Spoiler kind="hint" label="The key-preprocessing detail HMAC hides">
RFC 2104 also fixes how the key becomes block-sized before those two XORs: a key longer than the hash's block size is first hashed down to a digest, and a shorter key is zero-padded up to the block size [@rfc-2104]. That is why HMAC accepts a key of any length -- it normalizes every key to exactly one block before mixing in `ipad` and `opad`.
</Spoiler>

<Mermaid caption="HMAC's nested construction: the inner digest is fed back into an outer keyed hash, so the resumable internal state never appears in the tag.">
flowchart TD
    K[Secret key k] --> IP[k XOR ipad]
    M[Message m] --> INNER[Inner hash of ipad key then message]
    IP --> INNER
    INNER --> ID[Inner digest, never emitted directly]
    K --> OP[k XOR opad]
    ID --> OUTER[Outer hash of opad key then inner digest]
    OP --> OUTER
    OUTER --> T[HMAC tag]
</Mermaid>

The deepest fact about HMAC is also the most misunderstood, and it took another decade to prove. In 2006 Bellare showed HMAC is a pseudorandom function under the *sole* assumption that the hash's compression function is a PRF -- collision resistance is not required at all [@bellare-2006].

<Definition term="Pseudorandom Function (PRF)">
A keyed function is a PRF if no efficient adversary, allowed to query it on inputs of its choice, can distinguish its outputs from those of a truly random function. A PRF makes an immediate MAC: to forge a tag on a fresh message is to predict a value that, by assumption, looks uniformly random, which succeeds only with negligible probability. Unforgeability falls out of pseudorandomness.
</Definition>

This is why the collision breaks of MD5 and SHA-1 never touched HMAC-MD5 or HMAC-SHA-1. Collisions attack collision resistance; HMAC never needed it.

> **Note:** The folklore "HMAC needs a collision-resistant hash" is false, and it has been false since 2006 [@bellare-2006]. HMAC needs the compression function to behave like a PRF -- a different, and for MD5 and SHA-1 still-standing, assumption. This is not a licence to use MD5 in new systems, but it is why the practical world did not catch fire when SHA-1 collisions arrived.

The block-cipher branch got the same repair. CMAC, from Iwata and Kurosawa's OMAC and standardized as NIST SP 800-38B, derives two subkeys from the block cipher and mixes one into the final block, killing the variable-length splice that sank raw CBC-MAC while keeping a single key [@omac-2003] [@sp-800-38b]. It is the block-cipher PRF-MAC, useful where a device already has AES hardware but no hash.

<Sidenote>The survival of HMAC-SHA-1 is the cleanest real-world confirmation of the 2006 proof: SHA-1's collision resistance collapsed publicly, yet no HMAC-SHA-1 forgery followed, because the security reduction never invoked collision resistance in the first place [@bellare-2006].</Sidenote>

### The sponge refinement: KMAC

SHA-3 changed the substrate. A Keccak sponge splits its state into a public rate and a secret capacity, and it never emits the capacity [@fips-202]. That single property makes the HMAC nesting trick unnecessary: you can key a sponge by simply absorbing the key first.

<Definition term="Keyed Sponge">
A sponge function absorbs input into a large internal state divided into a public "rate" (the bytes that interact with input and output) and a secret "capacity" (bytes never revealed). Because the capacity is never output, prepending a key and absorbing it yields a keyed authenticator with no length-extension surface and no double hashing -- the key is protected by the same hidden capacity that protects the hash.
</Definition>

NIST SP 800-185 builds KMAC on cSHAKE this way: prepend the key, absorb, squeeze [@sp-800-185]. Keying is native, domain separation is built in through customization strings, and the tag length is a free parameter because the sponge is an extendable-output function. It is, conceptually, the cleanest MAC in the standard catalogue -- but conceptual cleanliness is not deployment.

<Aside label="KMAC's honest deployment status">
KMAC is a real, standardized primitive [@sp-800-185], implemented in OpenSSL 3.0 and later (as the `KMAC-128`/`KMAC-256` EVP_MAC) [@openssl-kmac], as well as BouncyCastle [@bouncycastle-kmac] and Botan [@botan-kmac]. It is not academic-only. But its production footprint is thin next to HMAC, GMAC, and Poly1305, for reasons that are historical inertia rather than cryptography: SHA-2 and HMAC are welded into TLS, IPsec, JWT, HKDF, and hardware everywhere, and SHA-3 adoption trails. This guide gives KMAC full conceptual treatment and makes no claim about its market share -- no reliable quantitative figure exists in a primary source.
</Aside>

Both HMAC and KMAC share a decisive operational property: a reusable key, no nonce, an unbounded stream of messages under one secret. That is the easy side of assumption one. The other lineage trades it away for speed.

### The Wegman-Carter lineage: GMAC and Poly1305

In 2004 and 2005, two designs dragged the 1981 one-time construction into high-speed networking. Both keep the pattern `tag = universal_hash(m) + one_time_pad`, and both solve the "fresh pad per message" problem the same way -- derive the pad from a cipher keystream instead of shipping new randomness.

GHASH, the core of GCM, is a polynomial universal hash over the finite field $\mathrm{GF}(2^{128})$: it evaluates $\sum_i m_i \cdot H^{\,L-i+1}$ at a secret point $H = E_k(0)$, then masks the result with an AES-encrypted counter block [@mcgrew-viega-2004]. Run GCM with an empty plaintext and you get GMAC, an authentication-only MAC over associated data, standardized in NIST SP 800-38D [@sp-800-38d]. Poly1305 evaluates a message polynomial modulo the prime $2^{130}-5$ under a secret $r$, then adds a one-time pad $s$; deployed as ChaCha20-Poly1305, it draws a fresh $(r, s)$ from the cipher keystream for every message [@rfc-8439].

<Mermaid caption="The Wegman-Carter one-time pattern behind GMAC and Poly1305: a keystream supplies a fresh hash key and pad per message, and reusing the nonce cancels the pad.">
flowchart TD
    N[Nonce and key] --> KS[Cipher keystream block]
    KS --> R[One-time hash key r]
    KS --> S[One-time pad s]
    M[Message m] --> P[Polynomial hash of m under r]
    R --> P
    P --> ADD[Add the one-time pad s]
    S --> ADD
    ADD --> T[Authentication tag]
    T -.reuse the same nonce.-> LEAK[Two tags cancel the pad, leaking hash of m1 minus hash of m2]
</Mermaid>

This is where the 1981 constraint re-enters as a deployment contract. The pad is safe only if the $(key, nonce)$ pair never repeats. Reuse it and the pad cancels out of the difference of two tags, exactly as the toy line did in Section 3 -- except now the "hash" is a polynomial an attacker can then start solving.

<RunnableCode lang="python" title="Reuse a one-time key and the pad cancels, exposing a key-independent relation">{`
# A one-time Wegman-Carter MAC: tag = poly_hash(m, r) + s (mod p). Use (r, s) ONCE.
p = (1 << 130) - 5                          # the Poly1305 prime, 2**130 - 5

def poly_hash(msg, r):
    acc = 0
    for i in range(0, len(msg), 16):
        chunk = msg[i:i+16]
        limb  = int.from_bytes(chunk, "little") + (1 << (8 * len(chunk)))
        acc   = ((acc + limb) * r) % p
    return acc

# In ChaCha20-Poly1305 both r and s come fresh from the keystream, per message.
r = 0x1bf54941aff6bf4afdb1f2a3c4d5e6f7
s = 0x0102030405060708090a0b0c0d0e0f10

def one_time_tag(msg):
    return (poly_hash(msg, r) + s) % p

# THE MISTAKE: two messages under the SAME (r, s).
m1, m2 = b"transfer 10 dollars now", b"transfer 9999 bucks now"
t1, t2 = one_time_tag(m1), one_time_tag(m2)

# The pad s cancels in the difference -- a relation that does not depend on s at all:
lhs = (t1 - t2) % p
rhs = (poly_hash(m1, r) - poly_hash(m2, r)) % p
print("pad cancelled, tag difference is key-independent:", lhs == rhs)
`}</RunnableCode>

It prints `True`: subtract two tags produced under the same one-time key and the secret pad vanishes, handing the attacker a clean algebraic relation in the hash key. That is the first step of the "forbidden attack" the failure catalogue will name -- and it is why the distinction below is not pedantry.

The **master key versus one-time key** split is the heart of the fork. HMAC and KMAC take a *master* key and authenticate forever under it. GMAC and Poly1305 take a *one-time* key per message; the ChaCha20-Poly1305 keystream manufactures that one-time key so the master key stays put, but the per-message pad is still strictly single-use. Confuse the two and you get a catastrophe, not a slow degradation.

The whole construction catalogue, side by side:

**Table 1 -- MAC constructions, and what each one assumes.**

| Construction | Year | Core idea | Key model | Strength | Weakness | Status |
|---|---|---|---|---|---|---|
| Carter-Wegman one-time [@wc-1981] | 1981 | $\mathsf{UH}(m) \oplus \text{pad}$ | One-time pad per message | Information-theoretic, no hardness assumption | Pad is strictly single-use | Foundational, revived |
| Secret-prefix $H(k \Vert m)$ [@length-ext-wiki] | 1990s | Prepend key, hash | Reusable | Trivial to build | Length-extension forgeable | Superseded, insecure |
| Secret-suffix $H(m \Vert k)$ [@length-ext-wiki] | 1990s | Append key, hash | Reusable | No length extension | Reduces to a hash collision | Superseded, insecure |
| CBC-MAC [@fips-113] | 1985 | CBC chain, keep last block | Reusable | First standardized block-cipher MAC | Variable-length splicing forgery | Historical |
| HMAC [@rfc-2104] | 1996 | Nested keyed hash | Reusable, no nonce | PRF not collision resistance, length-ext immune | Serial, no line-rate shortcut | Active, default PRF-MAC |
| CMAC [@sp-800-38b] | 2005 | CBC-MAC plus final subkey | Reusable, no nonce | Fixes CBC-MAC with one key | Block-cipher birthday ceiling | Active, niche |
| GMAC / GHASH [@sp-800-38d] | 2004 | Polynomial hash over $\mathrm{GF}(2^{128})$ | One-time pad per message | Carry-less-multiply hardware (PCLMULQDQ/PMULL) | Nonce reuse is fatal | Active, inside GCM |
| Poly1305 [@rfc-8439] | 2005 | Polynomial hash mod $2^{130}-5$ | One-time key per message | Fast in pure software, cipher-agnostic | One-time key per message | Active, inside ChaCha20-Poly1305 |
| KMAC [@sp-800-185] | 2016 | Keyed sponge, cSHAKE | Reusable, no nonce | Native keying, domain separation, XOF tag | Lightly deployed | Active, niche |

You can now build an unforgeable tag two ways: a reusable-key PRF or a one-time-key universal hash. But a perfect tag attached in the wrong place, in the wrong order, or over the wrong bytes is still useless. How do you *combine* a MAC with a cipher without reopening the door you just closed?

## 6. Composition Done Right, and the Verification Contract

SSL chose one order for combining its cipher and its MAC. SSH chose another. Both were quietly indicted by a theorem years before either was broken in the field. This section is where the second aha moment lands: strength was never the variable -- discipline and order were.

Bellare and Namprempre formalized the question in 2000 by splitting integrity into two notions [@bn-2000]. Integrity of plaintexts (INT-PTXT) says an attacker cannot make the receiver accept a plaintext the sender never sent. Integrity of ciphertexts (INT-CTXT) is stronger: the attacker cannot even produce a *new ciphertext* the receiver will accept. Their result is the load-bearing one: applying the MAC to the ciphertext -- Encrypt-then-MAC -- yields both IND-CCA confidentiality and INT-CTXT, and it is the only one of the three generic orders that reaches those strong notions.

<Definition term="Encrypt-then-MAC (EtM)">
Encrypt the plaintext, then compute the MAC over the resulting *ciphertext* (plus any associated data and length), and send ciphertext and tag together. On receipt, verify the tag *before* touching the ciphertext; if it fails, discard without decrypting. EtM is the only generic composition order that provably delivers integrity of ciphertexts, and it does so only under two preconditions: the MAC must be strongly unforgeable and the encryption and MAC keys must be independent.
</Definition>

Those two preconditions are not decoration. If the MAC is only EUF-CMA rather than SUF-CMA, the guarantee weakens from INT-CTXT down to INT-PTXT, because a malleable tag lets an attacker produce a different valid ciphertext for the same plaintext [@bn-2000]. And the keys must be independent -- reusing one key for both encryption and authentication voids the proof.

A year later Krawczyk sharpened the verdict [@krawczyk-2001]. He proved that any secure-channel protocol required to work with *any* secure cipher and *any* secure MAC must use Encrypt-then-MAC, and he built a perfectly secret cipher that becomes totally insecure under MAC-then-Encrypt -- SSL's order -- and under Encrypt-and-MAC -- SSH's order.

<PullQuote>
"[A]ny secure channels protocol designed to work with any combination of secure encryption ... and secure MAC must use the encrypt-then-authenticate method." -- Hugo Krawczyk, The Order of Encryption and Authentication for Protecting Communications, 2001 [@krawczyk-2001]
</PullQuote>

Here is the precision that separates an expert from a slogan-repeater: Krawczyk *also* proved that MAC-then-Encrypt is secure for specific cipher modes, namely [CBC and CTR](/blog/the-ciphertext-was-unbreakable-the-attacker-rewrote-it-anyw/) [@krawczyk-2001]. MtE is therefore *fragile* and *not generically secure* -- it holds only when you can prove something extra about the exact cipher -- but it was never unconditionally "broken." Say "MtE is broken" in an interview and you are wrong; say "MtE is not generically secure, so do not use it in new designs" and you are exactly right.

<Mermaid caption="Three composition orders and where verification happens: only Encrypt-then-MAC checks the tag before the ciphertext is ever decrypted or parsed.">
flowchart TD
    subgraph EtM["Encrypt-then-MAC, generically secure"]
        E1[Plaintext] --> E2[Encrypt]
        E2 --> E3[Ciphertext] --> E4[MAC the ciphertext]
        E4 --> E5[Receiver verifies tag first, then decrypts]
    end
    subgraph MtE["MAC-then-Encrypt, fragile"]
        M1[Plaintext] --> M2[MAC the plaintext]
        M2 --> M3[Encrypt plaintext and tag together]
        M3 --> M4[Receiver decrypts first, only then verifies]
    end
    subgraph EM["Encrypt-and-MAC, fragile"]
        A1[Plaintext] --> A2[Encrypt]
        A1 --> A3[MAC the plaintext, tag sent in the clear]
        A2 --> A4[Receiver decrypts, and the tag leaks plaintext]
    end
</Mermaid>

The diagram shows the mechanism behind every [padding-oracle](/blog/they-read-your-plaintext-without-breaking-your-cipher-a-fiel/) and SSH break at once: in the two fragile orders, the receiver must *decrypt or parse before it can verify*, so the very act of processing attacker-chosen bytes leaks information. Encrypt-then-MAC verifies first and refuses to decrypt a single byte of an unauthenticated ciphertext.

> **Key idea:** Authenticate the ciphertext, not the plaintext. Encrypt-then-MAC over the ciphertext -- with an independent key, a strongly unforgeable tag, and coverage of the associated data and length -- is the only generic order that lets the receiver reject a forgery before it decrypts anything. Every composition break in the catalogue is a system that decrypted or parsed before it verified.

**Table 2 -- Composition orders, ranked by what they generically guarantee.**

| Order | Idea | Generic security | Weakness | Status |
|---|---|---|---|---|
| MAC-then-Encrypt [@krawczyk-2001] | MAC the plaintext, then encrypt both | Not generic, secure only for CBC or CTR | Decrypt-before-verify padding and timing oracles | Superseded, fragile |
| Encrypt-and-MAC [@apw-2009] | Encrypt, and MAC the plaintext separately | Not generic | Tag over plaintext leaks, MAC-covered length field abused | Superseded, fragile |
| Encrypt-then-MAC [@bn-2000] | MAC the ciphertext | IND-CCA plus INT-CTXT | Needs SUF-CMA, independent keys, constant-time verify | Active, canonical |
| AEAD [@rfc-8446] | EtM internalized plus nonce management | IND-CCA plus INT-CTXT by construction | Key-commitment gap | Active, default |
| Committing AEAD [@rfc-9771] | AEAD plus key and context commitment | Adds commitment | Still standardizing, cost profiling | Frontier |

The order is only half of correct composition. The other half arrived not from a theorem but from a field disclosure. In 2009 Nate Lawson found that Google's Keyczar library compared HMAC tags byte by byte and returned as soon as two bytes differed [@keyczar-2009]. That early exit turns verification time into a side channel: a forged tag that matches more leading bytes takes measurably longer to reject, so an attacker can recover the correct tag one byte at a time by timing responses.

<RunnableCode lang="python" title="Why a byte-by-byte tag compare leaks, and how constant-time compare fixes it">{`

    Q0 -- Yes --> ASCON[Ascon, SP 800-232]
    Q0 -- No --> Q1&#123;"Is there a ciphertext to authenticate?"&#125;
    Q1 -- No --> HMAC[HMAC-SHA-256, reusable key, no nonce]
    Q1 -- Yes --> Q2&#123;"Can you guarantee a unique nonce per key?"&#125;
    Q2 -- No --> SIV[AES-GCM-SIV, misuse-resistant]
    Q2 -- Yes --> Q3&#123;"Is AES-NI hardware available?"&#125;
    Q3 -- Yes --> GCM[AES-GCM, rekey before the per-key ceiling]
    Q3 -- No --> CHACHA[ChaCha20-Poly1305]
</Mermaid>

Read the tree as the three assumptions in order. If there is no ciphertext to bind -- key derivation, a token, a one-time password -- use HMAC-SHA-256 with a key of at least 128 bits, a full-length tag, and a constant-time verify; there is no nonce to mismanage, so assumption one is nearly free. This is the right tool for HKDF [@rfc-5869], JWT's `HS256` [@rfc-7518], TOTP, HOTP, and PBKDF2.

If there *is* a ciphertext, do not hand-roll a MAC plus cipher -- reach for an AEAD, which internalizes Encrypt-then-MAC so you cannot mis-order it. Pick ChaCha20-Poly1305 when you lack AES hardware acceleration, especially on mobile and embedded targets, where its per-key budget is effectively unbounded [@rfc-8439]. Pick AES-GCM when you have AES-NI, and rekey before the $2^{23}$-packet ceiling on high-volume links [@rfc-9001]. If you cannot *guarantee* nonce uniqueness at scale, step down to AES-GCM-SIV, which degrades gracefully instead of catastrophically on reuse [@rfc-8452].

Two niche branches sit off the main tree. Use GMAC for authentication-only data, such as MACsec framing, with a guaranteed-unique nonce [@sp-800-38d] [@ieee-802-1ae]. Use KMAC when you are already in a Keccak or SHA-3 stack, or when you need domain separation or variable-length tags [@sp-800-185]. And on constrained or side-channel-sensitive hardware, use Ascon [@sp-800-232].

Then there are the rules that apply *always*, regardless of which box the tree lands in: Encrypt-then-MAC or an AEAD that internalizes it; independent encryption and MAC keys; a constant-time compare; a tag of at least 128 bits with documented truncation floors [@rfc-4868]; authentication that covers the associated data, the length, the version, and the session context; a committing AEAD when one ciphertext might be opened under multiple keys [@bellare-hoang-2022]; and a misuse-resistant AEAD when nonce uniqueness cannot be guaranteed [@rfc-8452].

> **Key idea:** Review authentication code against the checklist *and its negation*. The checklist tells you what a correct design does; the misuse list tells you what every named CVE did instead. Run any authentication path past both -- if it matches even one line of the misuse list, you have found your next vulnerability before an attacker does.

The negation is the misuse catalogue -- each row is a line of the checklist inverted, and it maps one-to-one onto a named break from Section 7.

**Table 6 -- Common misuse, the break it produced, and the fix.**

| Misuse in real code | Named break it caused | Fix |
|---|---|---|
| Secret-prefix $H(k \Vert m)$ MAC | Flickr length extension [@flickr-advisory] | Use HMAC or KMAC |
| Reusing a GCM nonce or Poly1305 one-time key | Joux, Nonce-Disrespecting [@woot16-bock] | Guarantee uniqueness or use AES-GCM-SIV |
| `==` or `memcmp` tag comparison | Keyczar timing leak [@keyczar-2009] | Use a constant-time compare |
| MAC-then-Encrypt or Encrypt-and-MAC in new code | Lucky Thirteen, POODLE, SSH recovery [@cve-2013-0169] | Use an AEAD (Encrypt-then-MAC) |
| Over-truncated tags | Forgery near the $2^{-t}$ floor [@rfc-4868] | Keep the tag at least 128 bits |
| One shared key for encryption and MAC | Voids the Encrypt-then-MAC proof [@bn-2000] | Derive independent keys |
| MACing the plaintext instead of the ciphertext | Padding oracles [@vaudenay-2002] | MAC the ciphertext |
| Forgetting AD, length, version, context | Terrapin [@terrapin-site] | Bind the full context |
| Treating "MAC verified" as "key committed" | Invisible salamanders [@bellare-hoang-2022] | Use a committing AEAD |

> **Note:** Run every authentication path past these ten lines: - Is the tag over the **ciphertext** (Encrypt-then-MAC), never the plaintext? - Are the encryption and MAC keys **independent**? - Is the MAC **strongly unforgeable** (SUF-CMA), not merely EUF-CMA? - Is the tag comparison **constant-time** (`compare_digest`, `timingSafeEqual`, `ConstantTimeCompare`)? - Is the **whole** decrypt-and-verify path constant-time, not just the compare? - Is the tag at least **128 bits**, with any truncation documented against the birthday bound? - For a one-time-key MAC (GMAC, Poly1305), is nonce uniqueness **guaranteed**, or are you on a misuse-resistant mode? - Does the authenticated data cover **length, version, ordering, and session context**? - Is there any **`H(secret || message)`** secret-prefix construction? (Replace with HMAC or KMAC.) - Could one ciphertext open under **two keys**? If so, use a committing AEAD. Any single failure here is a plausible next CVE.

That checklist and its negation are the working payoff of the whole field guide. Before the conclusion ties them back to the thesis, seven specific beliefs produce most of the remaining real-world authentication bugs -- and each is a corollary of the same one sentence.

## 13. Frequently Corrected Misconceptions

<FAQ title="Frequently asked questions">
<FAQItem question="Does HMAC need a collision-resistant hash?">
No. As Section 5 established, Bellare's 2006 proof rests HMAC's security on a single property of the underlying compression function -- that it is itself a PRF -- and not on collision resistance [@bellare-2006]. Since a collision attack targets a property the proof never relies on, HMAC-SHA-1 and HMAC-MD5 kept standing when the SHA-1 and MD5 collision breaks landed. Use HMAC-SHA-256 in new systems for margin, but understand that the reason is prudence, not a collision threat.
</FAQItem>
<FAQItem question="Are GMAC and Poly1305 just fast HMACs?">
No, and the difference is the most dangerous one to miss. HMAC takes a reusable key with no nonce. GMAC and Poly1305 are Wegman-Carter one-time-key MACs [@wc-1981]: they need a fresh, unique per-message key, and reusing it is catastrophic, not a gentle degradation. The 184 HTTPS servers caught repeating GCM nonces were forgeable precisely because a one-time construction was treated like a reusable one [@woot16-bock]. Same tag length, completely different key contract.
</FAQItem>
<FAQItem question="Does SHA-3 need HMAC?">
No. HMAC exists to defeat length extension on Merkle-Damgard hashes, but a Keccak sponge never emits its capacity, so it has no length-extension surface and keys natively -- just use KMAC [@sp-800-185]. In fact you cannot build HMAC on a SHAKE extendable-output function anyway; Python's `hmac` module notes that XOFs such as SHAKE-128 and SHAKE-256 cannot be used with HMAC [@python-hmac]. KMAC is the SHA-3-native answer.
</FAQItem>
<FAQItem question="Is MAC-then-Encrypt broken?">
No -- it is fragile, which is a different and more precise claim. Krawczyk proved MAC-then-Encrypt is *not generically secure*, yet also proved it *is* secure for CBC and CTR modes specifically [@krawczyk-2001]. So it was never unconditionally broken; it is simply deprecated for new designs, where a modern AEAD or Encrypt-then-MAC removes the cipher-specific precondition it depends on. Reach for one of those instead, but do not call MtE "broken."
</FAQItem>
<FAQItem question="Does one nonce reuse hand over the GCM key?">
Not by itself, and the overstatement matters. A single $(key, nonce)$ reuse immediately leaks a tag relation and the XOR of the two plaintexts [@joux-2006]. Recovering the subkey $H$ outright is a taller order: a single reuse leaves a root-finding equation with several possible solutions for $H$, so narrowing them to the one true value takes at least a second collision, and usually more. So "one reuse recovers the key" is wrong; "one reuse is already a break, and more reuse recovers the key" is right.
</FAQItem>
<FAQItem question="Is constant-time compare premature optimization?">
No -- there is a real-world counterexample. In 2009 Google's Keyczar library did a byte-wise tag comparison with an early exit, and that timing difference let an attacker recover valid tags one byte at a time [@keyczar-2009]. The comparison time leaked the secret the MAC existed to protect. Constant-time compare is a correctness requirement, not an optimization, and every major platform ships a named primitive for it.
</FAQItem>
<FAQItem question="Does using an AEAD mean I never touch a standalone MAC?">
No. AEAD handles the encrypted channel, but plenty of jobs have no ciphertext to bind and still need authentication. HKDF key derivation [@rfc-5869], JWT's `HS256` [@rfc-7518], TOTP and HOTP one-time passwords, and PBKDF2 are all standalone HMAC. The standalone MAC did not disappear with AEAD; it moved to the places where you are authenticating keys, tokens, or messages rather than protecting a ciphertext.
</FAQItem>
</FAQ>

Every myth here is a corollary of one sentence, which the conclusion now restates with the whole catalogue behind it.

## 14. The Math Never Broke

Return to Flickr, now fully understood. Two researchers forged valid API signatures with no key, no collision, and no cipher work, because Flickr's secret-prefix `H(secret || params)` construction handed out its resumable hash state as the tag [@flickr-advisory]. The hash met its specification exactly. The deployment broke assumption three -- the wrong construction over the wrong bytes -- and that was enough.

Line up the rest of the catalogue and the pattern is total. Lucky Thirteen and POODLE broke order and timing, decrypting before verifying [@cve-2013-0169] [@cve-2014-3566]. The SSH plaintext-recovery attack broke order, authenticating the plaintext and acting on a MAC-covered length field [@apw-2009]. The 184 nonce-repeating GCM servers broke key discipline, reusing a one-time pad [@woot16-bock]. Terrapin broke context, leaving the transcript and sequence numbers unbound even though the cipher, the MAC, and the order were all correct [@terrapin-site]. Not one of them broke AES, SHA-2, or a polynomial hash. Every single failure broke the contract around the primitive.

That is the whole thesis, proven by the evidence rather than asserted: a MAC makes forgery hard, and three deployment assumptions -- the right key discipline, a constant-time verify, and composition over the right bytes in the right order binding the right context -- are what keep it hard. The decision tree and the checklist in Section 12 are simply those three assumptions made executable. Carry them, and their negation, into every review.

The frontier moves the bar again: soon "the tag verified" should also mean "this ciphertext commits to one key and one context," the committing-AEAD work this series develops further in Part 7. And the deeper machinery lives in the siblings -- [the security definitions](/blog/secure-against-whom-the-security-definitions-every-protocol-/) of Part 1, [the one-time-key generation](/blog/predictable-or-repeated-the-only-two-ways-cryptographic-rand/) of Part 2, the canonicalization discipline of Part 3, the block modes of Part 5, the padding oracles of Part 6, and the AEAD decision matrix of Part 7. This part is the authentication spine that runs through all of them.

<PullQuote>
The math never broke; a deployment broke one of three assumptions. Authenticate the ciphertext, the length, and the context -- not just the message.
</PullQuote>

<StudyGuide slug="message-authentication-and-safe-composition" keyTerms={[
  { term: "Message Authentication Code (MAC)", definition: "A keyed algorithm producing a short tag so a shared-key holder can verify a message is authentic and unmodified" },
  { term: "EUF-CMA", definition: "Existential unforgeability under adaptive chosen-message attack; no forgery on a fresh message after querying tags" },
  { term: "SUF-CMA", definition: "Strong unforgeability; not even a new valid tag on a previously queried message, the notion Encrypt-then-MAC requires" },
  { term: "Universal hash function", definition: "A family whose random member collides any fixed pair with small, provable probability, with no hardness assumption" },
  { term: "Pseudorandom function (PRF)", definition: "A keyed function indistinguishable from random; the sole assumption HMAC's security rests on" },
  { term: "Keyed sponge", definition: "A sponge keyed by absorbing the key first; its hidden capacity gives native keying with no length extension, as in KMAC" },
  { term: "Encrypt-then-MAC", definition: "Compute the tag over the ciphertext and verify before decrypting; the only generically secure composition order" },
  { term: "One-time key", definition: "The per-message key of a Wegman-Carter MAC (GMAC, Poly1305); reuse is catastrophic, not a slow leak" },
  { term: "Key commitment", definition: "The property that a ciphertext decrypts validly under only one key; standard AEAD does not provide it" }
]} questions={[
  { q: "What are the three deployment assumptions every MAC relies on?", a: "Right key discipline for its family, a constant-time verify, and composition over the right bytes and order binding the right context." },
  { q: "Why did HMAC-SHA-1 survive SHA-1 collisions?", a: "HMAC's security reduces to the compression function being a PRF, not to collision resistance, as Bellare proved in 2006." },
  { q: "Why is reusing a Poly1305 or GMAC nonce catastrophic?", a: "The one-time pad cancels in the difference of two tags, leaking a key-independent relation that enables forgery." },
  { q: "Is MAC-then-Encrypt broken?", a: "No; it is fragile and not generically secure, though Krawczyk proved it secure for CBC and CTR. Avoid it in new designs." },
  { q: "What does Encrypt-then-MAC require to be secure?", a: "A strongly unforgeable (SUF-CMA) MAC, independent encryption and MAC keys, a constant-time verify path, and coverage of associated data and length." }
]} />