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

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 ^[1]. 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.

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.

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 ^[2]. 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.

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. 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 ^[1]. 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 ^[10]. The game is deliberately generous to the attacker.

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.

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). 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, and this article is the authentication half underneath it.

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.

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

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 ^[8].

Two years later, Wegman and Carter turned that object into an authenticator ^[6]. 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.

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.

So the airtight answer existed. Yet it authenticates only one message per key, which is impractical for a general-purpose MAC. The two ideas are separate papers: the 1979 work introduced universal classes of hash functions as a combinatorial tool ^[8]; the 1981 follow-up applied them to authentication and set equality ^[6]. Universal hashing came first; authentication was the application. 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 ^[11]. 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.

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

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

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.

# 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))

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.

The mirror construction, secret-suffix H(message || secret), resists length extension because the secret is absorbed last. 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 ^[11]. 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 ^[12]. 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 ^[13].

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 ^[14]. Standardized a year later as RFC 2104, HMAC computes two keyed passes ^[15]:

$\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.

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]

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 ^[16].

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.

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 ^{[17] [18]}. It is the block-cipher PRF-MAC, useful where a device already has AES hardware but no hash.

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 ^[19]. That single property makes the HMAC nesting trick unnecessary: you can key a sponge by simply absorbing the key first.

NIST SP 800-185 builds KMAC on cSHAKE this way: prepend the key, absorb, squeeze ^[20]. 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.

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 ^[24]. Run GCM with an empty plaintext and you get GMAC, an authentication-only MAC over associated data, standardized in NIST SP 800-38D ^[25]. 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 ^[26].

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]

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.

# 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)

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.

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 ^[7]. 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.

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 ^[7]. And the keys must be independent -- reusing one key for both encryption and authentication voids the proof.

A year later Krawczyk sharpened the verdict ^[27]. 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.

"[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 ^[27]

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 ^[27]. 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.

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

The diagram shows the mechanism behind every padding-oracle 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.

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.

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 ^[29]. 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.

import hmac, hashlib

key = b"server-side secret key, never sent"
def tag(msg):
  return hmac.new(key, msg, hashlib.sha256).digest()

real = tag(b"amount=10")

# The Keyczar bug: a compare that stops at the first mismatched byte. Its run time
# reveals HOW MANY leading bytes were correct -- a timer can read that off.
def leading_bytes_confirmed(guess):
  n = 0
  for x, y in zip(guess, real):
      if x != y:
          break            # early exit -- the timing leak lives right here
      n += 1
  return n

near_miss = real[:4] + bytes(28)          # first 4 tag bytes right, rest wrong
print("bytes an attacker can confirm by timing:", leading_bytes_confirmed(near_miss))

# The fix: hmac.compare_digest runs in time independent of where bytes first differ.
print("constant-time accept:", hmac.compare_digest(real, tag(b"amount=10")))
print("constant-time reject:", hmac.compare_digest(real, tag(b"amount=1000000")))

The naive compare confirms four bytes for a near-miss guess; repeat the probe and the whole tag falls out. The standard-library hmac.compare_digest closes it by taking time that depends only on length, not contents ^[30].

There is a subtler variant, and it is the one that made Lucky Thirteen famous. Even with a constant-time compare, the surrounding decrypt-and-pad-and-MAC path can leak, because a MAC-then-Encrypt receiver processes padding and computes the MAC over a variable number of bytes before it rejects ^[2]. The timing channel is in the path, not the comparison. Two distinct assumptions, then: the tag compare must be constant-time, and the entire verify path must be too.

The recipe is now fully specified: Encrypt-then-MAC, independent keys, a strongly unforgeable tag, a constant-time verify path, and authentication that covers the associated data and length. So why did the field keep bleeding named CVEs for another decade after all of this was known?

7. The Failure Catalogue#

Every entry below is the same sentence wearing a different costume: the primitive held, and a deployment broke one of the three assumptions. Read the catalogue as a proof of the thesis, not a parade of trivia. The column that matters is not the year -- it is which assumption failed.

Table 3 -- Named breaks, by the assumption they violated.

Walk the assumption-three group first, because it is the largest. Flickr's secret-prefix MAC fed the hash the wrong construction and leaked resumable state ^[1]. The MAC-then-Encrypt family -- Vaudenay's 2002 padding oracle and its timing-channel revival as Lucky Thirteen, plus POODLE's SSLv3 variant -- all decrypt or unpad attacker bytes before verifying, so they violate order and the constant-time-path assumption at once ^{[31] [2] [3] [35]}.

SSH's Encrypt-and-MAC put the tag over the plaintext and, fatally, over an encrypted length field the receiver had to act on before authentication could fail, which Albrecht, Paterson, and Watson turned into full plaintext recovery in 2009 ^[4].

The field's own standards bodies wrote the epitaph.

"The MAC-then-encrypt mechanism has been the subject of a number of security vulnerabilities over a period of many years." -- RFC 7366, Encrypt-then-MAC for TLS and DTLS, 2014 ^[36]

RFC 7366 did not deprecate MAC-then-Encrypt because it was provably broken -- recall that Krawczyk showed it is secure for CBC and CTR. It deprecated it because a construction that is safe only when you can prove something extra about the cipher is a construction that will eventually be deployed with a cipher where you cannot, and the industry had a decade of CVEs proving the point.

The assumption-one group is the 1981 landmine detonating in production. Antoine Joux's 2006 "forbidden attack" showed that repeating a $(key, nonce)$ in GCM sets up a polynomial equation over $\mathrm{GF}(2^{128})$ whose roots are candidates for the GHASH subkey $H$ ^[32]. Ten years later, Bock, Zauner, Devlin, Somorovsky, and Jovanovic scanned the live internet and found 184 HTTPS servers actually repeating GCM nonces, then forged tags against them ^[5].

Handschuh and Preneel had already quantified how few queries it takes to recover a universal-hash key once the one-time discipline is violated ^[33]. Same theorem, three appearances, one lesson: the one-time key is one-time.

Two of these attacks recur in the literature with the wrong citation, and getting them right is part of expertise.

Assumption two owns a smaller but sharp group: the Keyczar byte-by-byte compare from Section 6, and the Lucky Thirteen path that leaks even when the compare is constant-time ^{[29] [2]}. And then the newest entry proves the catalogue is not closed history.

One famous attack is deliberately not in this catalogue. BEAST is a predictable-IV chosen-plaintext attack on CBC in TLS 1.0 ^[39] -- a confidentiality flaw in how the IV was chosen, not a composition or MAC failure. It is named here only so you do not misfile it: BEAST is not an Encrypt-then-MAC-versus-MAC-then-Encrypt story, and citing it as one is a category error.

The catalogue is settled. Every entry violated key discipline, constant-time verification, or correct composition -- and none broke AES, SHA-2, or a polynomial hash. So what does a practitioner actually reach for in 2026, now that the composition decision has largely been taken out of application hands?

8. State of the Art in 2026#

The single biggest change since the catalogue is that the composition decision has been removed from application code entirely. TLS 1.3's record layer is AEAD-only ^[28]: there is no cipher suite an application can pick that would let it choose MAC-then-Encrypt or Encrypt-and-MAC. The correct order is now a property of the primitive, not a choice the developer can get wrong.

But AEAD did not abolish the standalone MAC -- it narrowed it to the jobs where there is no ciphertext to bind. HMAC still dominates those: HKDF key derivation ^[40], JWT's HS256 ^[41], TOTP and HOTP one-time passwords ^{[42] [43]}, PBKDF2 ^[44], and IPsec integrity with per-algorithm truncation floors such as HMAC-SHA-256-128, chosen "in accordance with the birthday bound" ^[45].

The other families hold narrower ground. GMAC ships for authentication-only data such as MACsec framing ^{[25] [46]}. Poly1305, specified in RFC 8439 ^[26], rides inside ChaCha20-Poly1305 -- WireGuard's only AEAD ^[47], OpenSSH's default channel cipher ^[48], and a standardized option in TLS 1.3 ^[28] and QUIC ^[49], though AES-128-GCM is the TLS 1.3 mandatory-to-implement suite. KMAC serves Keccak and SHA-3 stacks and compliance contexts that need domain separation ^[20]. The reusable-key-versus-one-time-key fork did not disappear; it moved inside the AEAD.

The most decision-relevant number in modern authentication is not a speed -- it is a data ceiling, because an AEAD's underlying counter-mode cipher carries a birthday-type confidentiality budget on how much you may process under one key. That ceiling is set by the cipher's block or state size, not by GHASH or Poly1305 as hashes; the MAC's own forgery budget is the separate, and far larger, integrity limit.

Table 4 -- Per-key confidentiality ceilings from QUIC (RFC 9001, section 6.6).

Those figures come straight from RFC 9001 ^[49], and the contrast is stark: an AES-GCM key on a busy QUIC server must be rotated after about eight million packets, while a ChaCha20-Poly1305 key never realistically has to be. That single table decides more real deployments than any speed benchmark.

Three 2024-2026 signals round out the picture. First, NIST is refreshing HMAC itself: draft SP 800-224 folds in modern hash-selection, key-size, and truncation guidance, with FIPS 198-1 ^[50] proposed for withdrawal as SP 800-224 publishes -- HMAC is being re-issued, not retired ^[51]. Second, Ascon arrived as the lightweight standard for constrained devices in SP 800-232 ^[52]. Third, constant-time verification is moving from coding discipline to hardware guarantee.

That hardware move is worth naming. Go 1.24 added subtle.WithDataIndependentTiming, which on Arm64 processors with FEAT_DIT enables that feature (PSTATE.DIT) for the duration of a function, so a compiler or speculative CPU cannot reintroduce data-dependent timing into a "constant-time" routine ^[53]. On every other architecture the call currently does nothing; Intel's analogous DOIT mode is real hardware, but it is not yet wired into this Go API. It is the practical answer to the old objection that constant-time compare is premature optimization.

AEAD papered over the order decision, but it did not erase the deeper fork underneath every MAC: reusable key versus one-time key. That choice is still yours, and it has a right answer per use case. What does the head-to-head actually look like?

9. PRF-MAC versus Universal-Hash MAC#

Put the two lineages head to head. Neither wins outright, and knowing exactly why is the mark of an expert rather than a partisan.

Table 5 -- The two families, side by side.

The split is clean. HMAC, KMAC, and CMAC take a reusable key, authenticate an unbounded number of messages, and need no nonce -- assumption one is nearly free -- but they are serial and comparatively slow. GMAC and Poly1305 run at line speed but demand a fresh one-time key per message and a hard nonce contract. That is the whole trade.

Speed is why AEADs chose the universal-hash side. Carry-less multiply hardware -- Intel PCLMULQDQ or Arm PMULL -- reduces GHASH's $\mathrm{GF}(2^{128})$ multiply to a few 64-bit carry-less-product instructions plus a fast modular reduction, replacing the large lookup tables of software GHASH; that is the step that lets AES-GCM reach about 3.5 cycles per byte on the first such processors, more than six times faster than table-based software ^[55]. Bernstein measured Poly1305-AES verifying a 1024-byte message in 3843 Athlon cycles and a 64-byte message in 1232 Pentium 4 cycles ^[56]. HMAC has no comparable algebraic shortcut; it is a serial double hash. Treat the exact cycle counts as indicative and the ordering as load-bearing: on bulk data, the universal-hash MACs beat serial HMAC by roughly an order of magnitude, and that gap, not any security difference, is what pushed them into every high-throughput AEAD.

The reuse column is the sharpest contrast. HMAC and KMAC have no nonce, so there is nothing to reuse -- assumption one costs them almost nothing. GMAC and Poly1305 have exactly one nonce, and reusing it is not degradation, it is collapse: the pad cancels and the catalogue's forbidden attack begins.

Both families sit near the same theoretical wall. What does that wall actually look like, and what does "provably secure" really rest on?

10. Theoretical Limits#

The per-attempt forgery problem is essentially solved, and that is precisely why the remaining gaps are interesting: they are not about making forgery harder, but about what "secure" quietly rests on.

Start with the floor. Against a $t$-bit tag, a blind forger who simply guesses succeeds with probability

$\Pr[\text{forge}] \;\ge\; 2^{-t},$

and no MAC can beat it. This is why truncation is a security dial, not a free saving: cutting a tag to 96 bits caps forgery resistance at $2^{-96}$ per attempt, which is why IPsec fixes explicit truncation floors "in accordance with the birthday bound for each algorithm" ^[45]. The floor is achieved unconditionally only by Wegman-Carter one-time authentication, the 1981 construction -- the information-theoretic optimum that GMAC and Poly1305 still structurally imitate.

The deployed algorithms sit near that floor. Poly1305's proven gap is $n/2^{102}$ per forgery attempt for $16n$-byte messages, and it reduces entirely to the cipher -- the only way to forge is to break AES or ChaCha ^{[56] [57]}. HMAC attains negligible advantage under the sole assumption that its compression function is a PRF ^[16]. The per-attempt problem is closed.

There is also a data ceiling. Constructions with a 128-bit block or state lose their margin near the birthday bound $2^{n/2} \approx 2^{64}$ processed blocks, ※ The birthday bound again: among roughly $2^{n/2}$ random values you already expect a collision, which is why a 128-bit primitive frays near $2^{64}$, not $2^{128}$. which is the theoretical origin of AES-GCM's $2^{23}$-packet-per-key budget from Section 8 ^[49]. The universal-hash MACs are near-optimal per attempt but bounded in total volume per key.

Four impossibility results fence the field. There is no sub-$2^{-t}$ forgery resistance for a $t$-bit tag. There is no unconditional reusable-key MAC -- authenticating many messages against an unbounded adversary provably needs fresh key material per message, which is why the computational escape exists at all. There is no single-pass misuse-resistant AE, because a misuse-resistant tag must depend on the whole message before any ciphertext is emitted, so AES-GCM-SIV is two-pass by necessity, not inefficiency ^[58]. And the one that seeds the final aha moment: unforgeability does not imply commitment.

That last point is the crack. GCM and ChaCha20-Poly1305 are provably not committing, so a valid tag does not even guarantee the ciphertext binds to a single key or context ^{[59] [9]}. "The MAC verified" and "this ciphertext commits to one key" are different statements, and the gap between them is where current research lives.

So "the tag verified" does not even mean "this ciphertext commits to one key." Where does the field go from here?

11. Open Problems and Active Research#

Five honest frontiers remain, each one a place where "the MAC verified" is not yet the end of the story.

Beyond-birthday-bound MACs at line speed. On a 128-bit primitive, GHASH- and CMAC-style authentication erodes near $2^{64}$ processed blocks, whose concrete face is AES-GCM's $2^{23}$-packet-per-key budget ^[49]. Sum-of-PRP and double-block-hash-then-sum constructions are proven well beyond the birthday bound ^[60], and NIST's "accordion" mode effort is exploring wide, misuse-resistant modes ^[61] -- but none has displaced GHASH or Poly1305 in deployment. The practical answer on Monday is still "rekey before the ceiling."

Nonce-misuse resistance as the default. The universal-hash family's number-one foot-gun is nonce reuse, so why not make graceful degradation standard? AES-GCM-SIV delivers exactly that -- a repeated nonce leaks only message equality, not the key -- but it is two-pass by necessity, since Section 10's impossibility result forbids a single-pass misuse-resistant AE ^[58]. The open question is whether the misuse-resistance tax can be cut low enough to make it the default AEAD.

Committing AEAD, standardized and cheap. This is the live edge for authentication.

Post-quantum posture. The honest version is reassuring, with one caveat.

Leakage-resilient constant-time across the stack. Constant-time source is not constant-time execution once an optimizing compiler and a speculative CPU get involved. The architecture-level answer -- CPU data-independent-timing modes such as Arm64 FEAT_DIT, which Go exposes through subtle.WithDataIndependentTiming ^[53], and Intel's analogous DOIT -- is the current best partial result, but end-to-end, machine-checked constant-time guarantees across the whole decrypt-and-verify path remain open.

Research aside, you have to ship something on Monday. Here is the decision procedure that honors all three assumptions by construction.

12. A Practical Guide, and Its Mirror Image#

Everything above collapses into one decision tree, one checklist, and the checklist's negation -- the misuse list that reads like a table of contents for the failure catalogue.

flowchart TD
START[Choose an authenticator] --> Q0{"Constrained or side-channel-sensitive device?"}
Q0 -- Yes --> ASCON[Ascon, SP 800-232]
Q0 -- No --> Q1{"Is there a ciphertext to authenticate?"}
Q1 -- No --> HMAC[HMAC-SHA-256, reusable key, no nonce]
Q1 -- Yes --> Q2{"Can you guarantee a unique nonce per key?"}
Q2 -- No --> SIV[AES-GCM-SIV, misuse-resistant]
Q2 -- Yes --> Q3{"Is AES-NI hardware available?"}
Q3 -- Yes --> GCM[AES-GCM, rekey before the per-key ceiling]
Q3 -- No --> CHACHA[ChaCha20-Poly1305]

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 ^[40], JWT's HS256 ^[41], 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 ^[26]. Pick AES-GCM when you have AES-NI, and rekey before the $2^{23}$-packet ceiling on high-volume links ^[49]. If you cannot guarantee nonce uniqueness at scale, step down to AES-GCM-SIV, which degrades gracefully instead of catastrophically on reuse ^[58].

Two niche branches sit off the main tree. Use GMAC for authentication-only data, such as MACsec framing, with a guaranteed-unique nonce ^{[25] [46]}. Use KMAC when you are already in a Keccak or SHA-3 stack, or when you need domain separation or variable-length tags ^[20]. And on constrained or side-channel-sensitive hardware, use Ascon ^[52].

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 ^[45]; 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 ^[59]; and a misuse-resistant AEAD when nonce uniqueness cannot be guaranteed ^[58].

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.

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#

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 ^[1]. 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 ^{[2] [3]}. The SSH plaintext-recovery attack broke order, authenticating the plaintext and acting on a MAC-covered length field ^[4]. The 184 nonce-repeating GCM servers broke key discipline, reusing a one-time pad ^[5]. Terrapin broke context, leaving the transcript and sequence numbers unbound even though the cipher, the MAC, and the order were all correct ^[34]. 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 of Part 1, the one-time-key generation 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.

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