datmt.com

MACs, Length Extension, HMAC, and AEAD: A Complete Walkthrough

Thu Sep 10 2026

MACs, Length Extension, HMAC, and AEAD

Every authenticated communication needs a way to prove two things: the message came from someone who knows the secret key, and it hasn’t been altered in transit. A Message Authentication Code (MAC) delivers that guarantee.

But not all MAC constructions are equal — some have subtle but devastating weaknesses like length extension, others require careful one-time key management, and composing them with encryption introduces its own set of pitfalls. This post walks through each layer with runnable code.

What a MAC actually guarantees

A MAC is a keyed function tag = MAC(K, message) that produces a fixed-length authentication tag. The security goal is unforgeability: given any number of (message, tag) pairs under the same key, an adversary who does not know K cannot produce a valid tag for any new message they haven’t seen before.

This is stronger than collision resistance (which only prevents finding two messages with the same tag). Unforgeability requires that even observing thousands of valid tags gives zero advantage in forging one more.

Why prefix-MAC fails: length extension

The simplest idea is to prepend the key to the message and hash it:

prefix_mac(K, M) = H(K || M)

This looks reasonable until you realize that SHA-256 and SHA-1 use a Merkle-Damgård construction — blocks processed sequentially, with each block’s output feeding into the next. The internal state after processing K || M is exactly the MAC tag (well, the hash of it). That means anyone who sees the tag can continue hashing from that point.

Here’s a demonstration using a mock Merkle-Damgård hash:

HMAC defeats length extension with a double-hash

HMAC (RFC 2104) breaks the chain between inner and outer hash by using two independent keys derived from the original key:

inner_key = K \u2295 ipad
outer_key = K \u2295 opad
HMAC(K, M) = H(outer_key || H(inner_key || M))

Even if an attacker knows H(inner_key || M) (the inner hash output), they cannot continue the outer hash without knowing outer_key. The Merkle-Damgård chain is broken at the boundary.

Let’s verify that a manual HMAC implementation matches Python’s standard library:

Three composition orders for encryption + MAC

When you need both confidentiality and authenticity, you combine encryption and a MAC. There are three natural compositions, each with different security properties:

  1. Encrypt-and-MAC (EtA): C = Enc(K₁, M), T = MAC(K₂, M) — tag on plaintext
  2. MAC-then-encrypt (MtE): T = MAC(K₁, M), C = Enc(K₂, M || T)
  3. Encrypt-then-MAC (EtM): C = Enc(K₁, M), T = MAC(K₂, C) — tag on ciphertext

Only EtM is provably safe in the general case. EtM verifies authentication before decryption, so a tampered ciphertext is rejected without any padding oracle or decryption error leaking information.

Here’s how each behaves with tampering:

Poly1305: a one-time-key MAC, and why AEAD exists

Poly1305 is a Carter-Wegman MAC defined by the formula:

f_k(m) = ((m' mod p) + r) \u00d7 s mod 2^128

where k = (r || s) is a 32-byte key, p = 2^130 - 5, and m' is the message split into blocks with high bits appended. The key insight: the same (r, s) must never be reused. Poly1305’s security relies on (r, s) being a one-time pad — if two messages share a key, an attacker who knows either plaintext can solve for r, then forge tags for any message.

This linearity is why Carter-Wegman MACs derive fresh (r, s) from a block cipher per-message nonce. In practice, this is how ChaCha20-Poly1305 works: ChaCha20 encrypts the nonce to produce a one-time Poly1305 key.

AEAD (Authenticated Encryption with Associated Data) modes like GCM and OCB integrate encryption and authentication into a single primitive rather than composing them externally. Here’s a comparison:

Takeaway

A MAC’s job is unforgeability, not just collision resistance. Prefix-MAC leaks the internal hash state through Merkle-Damgård chaining; HMAC fixes this with independent inner/outer keys. When combining encryption and authentication, always use encrypt-then-MAC or a proper AEAD mode — never roll your own composition. Poly1305’s one-time key requirement shows why nonce discipline matters: reuse destroys the MAC completely.