Encryption, from the ground up · Puzzle 6 · 7 of 9

A hash with a secret

Puzzle 5 showed a fingerprint anyone can recompute, so an attacker who changes the data just sends a new fingerprint. Add a key that only the two sides have, and the fingerprint becomes something only they can make.

The problem

Puzzle 5's hash catches accidental changes. But an attacker who changes the data can hash the changed data and send that digest instead. If both sides already share a secret key (puzzle 3 got them one), can they make a fingerprint the attacker can't forge?

See it

The sender computes a tag from the data and the shared key and attaches it; the receiver recomputes it with the same key and compares; an attacker changes the data but cannot compute a matching tag without the key, so the receiver rejects it sender receiver pay 20 €tag recompute, compare: equal attackerpay 900 €, no key tag doesn't match: rejected
  1. The sender computes a MAC from the message and the shared key, and attaches it as a tag.

    Step 1 of 4
  2. The receiver has the same key: it recomputes the MAC and compares. Equal: unchanged.

    Step 2 of 4
  3. An attacker changes the amount, but has no key. Predict: can it make a matching tag?

    Step 3 of 4
  4. No: the receiver's tag won't match, and the message is rejected. HMAC is the usual recipe.

    Step 4 of 4

The building block

A MAC, message authentication code, is a short value computed from two inputs: the data and a secret key. The most common way to build one is HMAC: it runs a hash function like SHA-256 over the data mixed with the key, in a fixed recipe.

How it's used:

  1. The sender computes the MAC of the data with the shared key and attaches it: the tag.
  2. The receiver, who has the same key, computes the MAC of the data it received and compares it with the tag.
  3. Equal: the data is unchanged and came from someone with the key. Different: reject it.

An attacker who changes the data would need a new tag that matches, and making one needs the key. Without it, there's no known way.

Compare the tools so far: a hash anyone can compute; a MAC only key holders can compute. And both sides hold the same key, so a MAC proves "one of us made this", not which one: proving who, to anyone, needs puzzle 7.

The analogy

A wax seal pressed with a ring that only you and your friend own. Anyone can melt the seal and change the letter, but without the ring they can't press a new seal that looks right.

Check yourself

The attacker changes a message and computes a fresh SHA-256 digest of it. With a MAC in use, what happens?

Right. No key, no valid tag.

Not quite. Any change needs a new tag, and that needs the key.

Not quite. A plain digest isn't the check here; the tag needs the secret key.

Both sides share the MAC key. What can't a MAC prove?

Not quite. It proves that; it can't say which holder.

Not quite. That's exactly what it proves.

Right. One of us, not which one.

What's the difference between a hash and a MAC?

Not quite. That's the two swapped. Re-read that part ↑

Right. Public vs keyed.

Sources

  • RFC 2104, HMAC ("This document describes HMAC, a mechanism for message authentication using cryptographic hash functions")

What you now know

A MAC (message authentication code) is a short value computed from the data and a secret key together; HMAC builds one from a hash function. The sender attaches it as a tag; the receiver, who has the same key, recomputes it and compares. An attacker who changes the data can't compute the matching tag without the key, so any change is caught. TLS protects every chunk of your data this way.