MACs, keyed hashes, and HMAC

A MAC is a hash with a key, and the key changes everything

A message authentication code is a small fixed-size block computed from the message and a shared secret key: MAC = F(K, M). The sender appends it to the message; the receiver, who holds the same K, recomputes it over what arrived and compares. On a match the receiver may conclude three things:

1. The message was not altered. An attacker who changed it could not recompute a matching code without K.
2. The message came from the alleged sender. Nobody else holds K.
3. The sequence is correct — but only if the message carries a sequence number, because then the attacker cannot alter that number undetectably either.

A MAC function need not be reversible, and that is a genuine advantage: there is less mathematical structure for an attacker to exploit than in an encryption function. Historically these were built from DES; AES is the appropriate modern base, CBC-based MACs have been superseded by CMAC, and typical tag lengths are now 256 bits or more.

There are also four plainly practical reasons to build authentication out of hashing rather than encryption: encryption in software is slow; encryption hardware costs money and that cost multiplies across every node in a network; encryption hardware is tuned for bulk data and wastes a large fraction of its time on per-invocation setup when the blocks are small; and an encryption algorithm may be encumbered by patents.

Worked example — the naive keyed hash, and why it fails

The obvious way to key a hash is to hash the key with the message: tag = H(K || M). It is wrong, and the reason is worth understanding because it is the whole motivation for HMAC's shape.

SHA-256, SHA-1 and MD5 are Merkle–Damgård constructions: they absorb the message block by block into an internal state, and the final digest is that state. So an attacker who sees M and tag = H(K || M) — without knowing K at all — can load tag back in as the internal state, continue absorbing blocks of their own, and emit a valid tag for K || M || padding || M_extra. That is a length-extension attack: a forged message with a valid tag, produced by somebody who never learned the key. Appending instead, H(M || K), shifts the problem onto the hash's collision resistance and is also weaker than it looks.

The pre-HMAC fix was to use the key at both ends: MD = H(K || M || K), transmitting M || MD. Prefix-only or suffix-only is measurably less secure than the sandwich. Notice, in passing, why preimage resistance is load-bearing here: if H were invertible, an observer who has M and MD computes H inverse of MD, reads off K || M || K, and now holds your key.

HMAC — the standardised construction

HMAC (RFC 2104) is the version that is specified, analysed and deployed: it is the mandatory-to-implement MAC in IPsec and is used throughout TLS. Its formula, with b the hash's block size in bits:

HMAC(K, M) = H[ (K+ XOR opad) || H[ (K+ XOR ipad) || M ] ]

Seven steps, in order:

1. Append zeros to the left end of K to make a b-bit string K+. (A 160-bit key with b = 512 gets 44 zero bytes.)
2. XOR K+ with ipad to give the b-bit block Si.
3. Append M to Si.
4. Apply H to that stream — the inner hash.
5. XOR K+ with opad to give the b-bit block So.
6. Append the step-4 result to So.
7. Apply H again. That output is the MAC.

The two pad constants come from RFC 2104, not from the textbook: ipad is the byte 0x36 repeated b/8 times, and opad is the byte 0x5C repeated b/8 times. They differ because XORing K+ with each one flips a different half of the key's bits, so passing Si and So through the hash pseudorandomly derives two keys from one.

The single most common reconstruction error in an exam is to write the outer hash over the message. It is not: the outer hash is over the inner hash's output, which is only n bits long. And because HMAC uses H strictly as a black box, swapping SHA-256 for SHA-512 changes only b and n — nothing in the construction itself. That replaceability was an explicit design objective, along with using an unmodified off-the-shelf hash, preserving its performance, handling keys simply, and having a security argument that can actually be analysed.

That argument is the last thing worth knowing here. Breaking HMAC requires either computing the compression function's output under a secret, unknown IV — effort $2^n$ — or finding collisions under a secret IV, the birthday case at $2^{n/2}$. But the attacker cannot generate message/MAC pairs on their own, because they have no key. They must observe them. Observing $2^{64}$ blocks under one unchanged key is roughly 150,000 years of continuous traffic on a 1 Gbps link. This is the course's cleanest illustration that a bound which looks broken offline can be untouchable online.

What a MAC cannot do

Both parties hold the same key. Therefore anything one of them can produce, the other could have produced too. A MAC proves integrity and origin to the holder of the key and to nobody else — it settles no dispute, in either direction, and it gives no non-repudiation; answering that question at all requires the public-key machinery introduced in Module 5, which is where the comparison is settled attack by attack. A MAC also does nothing at all about a replay — the replayed message and tag are genuine, and integrity was never the problem. The fix for replay is a sequence number, timestamp or nonce inside the authenticated data, so that a repeat is detectable as a repeat.