MACs and authenticated encryption

Every cipher so far has had the same weakness: it hides a message, but doesn’t stop it being changed. Mallory rewrote the account number in Alice’s encrypted message on the first page without ever knowing the key, and the modes of operation let Mallory cut, paste and flip bits. This page builds the tool that stops all of that, and then puts it together with encryption.

1 · A check only the key-holder can make

A message authentication code, or MAC, is a short value computed from the message and a secret key that Alice and Bob share: the tag. Alice sends the message with its tag. Bob computes the tag again from what arrived and the key, and compares. If anything in the message changed, the tags won’t match. And without the key, Mallory can’t work out the right tag for the changed message.

Alice’s message with its tag (made with HMAC, section 3), and what Mallory sends instead: the same message with the account changed to Mallory’s own. Keep Alice’s tag, make one up, or make one with a key of Mallory’s own: Bob refuses them all. Put Alice’s message back exactly and Bob accepts it again.

A MAC doesn’t hide anything: here the message travels as it is, and anyone can read it. It’s about integrity and authenticity, the other two of the three things we want. What makes it secure is a demanding standard: even after seeing the tags of as many messages as they like (messages they chose, even), an attacker can’t make a valid tag for any message they haven’t seen one for.

2 · The obvious MAC, and how it fails

A hash function turns any message into a short fingerprint, such as SHA-256’s 32 bytes. The obvious MAC is to hash the key and the message together:

tag = SHA-256(key ‖ message)

(‖ means “followed by”.) Mallory doesn’t have the key, so can’t compute it. It looks fine. It isn’t, because of how SHA-256 works inside. It pads the message to a whole number of 64-byte blocks: a 1 bit, zeros, and finally the message’s length. Then it starts from a fixed state of 32 bytes and mixes in one block after another. The hash is the state after the last block.

So the tag is SHA-256’s state at the end of key ‖ message ‖ padding. Mallory can start from it and carry on mixing in more blocks, exactly as SHA-256 would have if the message had been longer. The result is the correct tag for a longer message: the original, then the padding, then whatever Mallory adds. This is a length-extension attack. The only thing Mallory needs to know is the key’s length, to get the padding right, and that can simply be guessed.

A payment request, pay=20&acct=4821, tagged with SHA-256(key ‖ message) by a server with a secret key of a secret length. Mallory adds &acct=6666, after the padding SHA-256 would have used (shaded), and continues the hash from the tag. With the right guess at the key’s length, the server’s own check passes: it reads the request field by field, the later acct wins, and it pays Mallory. Try every length guesses each in turn, as Mallory would. (Checked in the tests for 20 random keys of 8 to 32 bytes; a wrong length always fails.)

The padding sits in the middle of the forged request, as unprintable bytes. Plenty of software reads past that. In 2009 Thai Duong and Juliano Rizzo showed exactly this against the signed requests of Flickr’s programming interface, which used MD5 (a hash built the same way) of a secret followed by the request.

Not every hash gives its state away like this. SHA-3, built differently, doesn’t. But the safe answer, for any hash, is to stop using it so naively.

3 · HMAC: hashing twice

HMAC (Mihir Bellare, Ran Canetti and Hugo Krawczyk, 1996) hashes twice:

tag = SHA-256(key ⊕ opad ‖ SHA-256(key ⊕ ipad ‖ message))

The key is padded to a block and XORed with two different constants (ipad is the byte 0x36 repeated, opad 0x5c), making two different keys from one. The inner hash covers the message; the outer one hashes the inner result. Mallory can still extend the inner hash, but never sees it: only the outer one is sent. And extending the outer hash gives the tag of something the server never computes, the outer key followed by an inner hash and more.

HMAC’s two passes on the same payment request, and Mallory’s length extension aimed at it: the forged tag and what the server actually computes for the forged request differ, so it’s refused. Switch to RFC 4231’s test case 2 to check the page’s HMAC against the published answer.

HMAC comes with a proof: it’s as strong as the hash’s inner mixing (its compression function), even if the hash as a whole has weaknesses like length extension. It signs requests to many web services, and many other protocols build on it.

4 · Checking a tag, carefully

There’s one more way to get a tag wrong, and it’s not in the maths at all. The obvious way to compare Bob’s tag with the one that arrived is a byte at a time, stopping at the first difference:

for i in range(len(tag)):
    if tag[i] != expected[i]:
        return False      # stops early: sooner the earlier the difference
return True

It’s correct, but how long it takes depends on how many bytes match. Mallory sends a message with a guessed tag, and times the refusal. Of the 256 possible first bytes, the right one takes a little longer to refuse, because the comparison gets one byte further. Fix that byte, and do the same for the next.

A hidden 16-byte tag, and Mallory guessing it a byte at a time. The time is simulated as a count of how many bytes the comparison looked at, without the noise of real timings. For each byte, the right guess (orange) is the one that gets one byte further before it’s refused; for the last byte, it’s the one that’s accepted. A tag that would take 2¹²⁸ guesses all at once takes at most 16 × 256 = 4,096 this way (checked in the tests).

Real timings are noisy, so a real attacker repeats each guess many times and averages, but the difference is there to be found. The fix is a comparison that always looks at every byte, combining the differences with OR and checking only the result at the end. Leaks through time, power or other physical effects are called side channels, and they’ve broken many systems whose mathematics was sound.

5 · Polynomial MACs

HMAC hashes everything twice. There’s a faster kind of MAC built on a polynomial, and it’s easiest to see with small numbers. Work modulo a prime, p = 101 (so every number is 0 to 100; multiply or add, then keep the remainder on dividing by 101). The key is two numbers, r and s. The message is a list of numbers. Starting from 0, for each number add it to the running total and multiply by r. At the end, add s.

A polynomial MAC with small numbers, step by step. With the message 3, 1, 4 and the key r = 10, s = 50: 3 × 10 = 30; (30 + 1) × 10 = 310, which is 7 mod 101; (7 + 4) × 10 = 110, which is 9; and 9 + 50 gives the tag 59. Change the message, or the key.

Written out, the running total is the message’s numbers as the coefficients of a polynomial, evaluated at the secret point r: here 3r³ + r² + 4r. Mallory’s changed message is a different polynomial. Two different polynomials of degree k can agree at no more than k points, so the chance that Mallory’s tag happens to be right is at most k out of p. With a prime as large as the real ones, that’s negligible. And adding s hides the polynomial’s value completely, just as a one-time pad hides a message.

Which is also the catch: like a one-time pad, the key must be used once.

One key (r, s) used for two messages of one number each. Each tag is m × r + s, so two of them are two equations in two unknowns: subtracting one from the other gets rid of s and gives r, and then s follows. With the key solved, Mallory tags any message, and Bob accepts it. (Checked in the tests for every r.)

Poly1305, designed by Daniel J. Bernstein (2005), is this idea with real numbers. The prime is 2¹³⁰ − 5, close enough to a power of two to make the remainders fast. The message is read 16 bytes at a time, each block as a number with an extra 1 above its top byte (so trailing zero bytes still count). Some bits of r are set to zero, which makes fast code simpler at a small cost in security. The key is used once: wherever Poly1305 is used, a fresh (r, s) is made for every message.

Poly1305 with the key from RFC 8439’s worked example, block by block: each block as a number, and the running total after it. The tag is the total plus s, cut to 16 bytes. On the RFC’s own message, the tag matches its published answer; type your own message to see every block change.

AES-GCM’s MAC, GHASH, is the same again in a different kind of arithmetic: blocks of 128 bits as polynomials whose coefficients are bits, as on the finite fields page, multiplied modulo x¹²⁸ + x⁷ + x² + x + 1. Its r is AES’s encryption of a block of zeros under the key, and its s is a fresh AES output for each nonce: here r stays the same for every message, and s is the part used only once. So reusing a nonce with GCM repeats s, and subtracting two tags gets rid of it, as above, leaving an equation for r (a polynomial one, harder to solve than the division above, but solvable). With r, Mallory can forge.

6 · Authenticated encryption

Most of the time a message needs both: hidden from Eve, and protected from Mallory. Putting a cipher and a MAC together sounds simple, but there are three orders to do it in, and they’re not equally safe:

Encrypt and MAC: encrypt the message, and tag the plaintext. The tag is sent in the open, and a tag of the plaintext can give things away (in general, the same message gets the same tag). SSH was designed this way.
MAC then encrypt: tag the plaintext, then encrypt both. Bob has to decrypt before checking, and everything done with unchecked data is a chance to leak. TLS worked this way until version 1.3, and the padding oracle attacks exploited exactly that.
Encrypt then MAC: encrypt, then tag the ciphertext. Bob checks the tag first, and refuses anything that fails before decrypting a single byte. Mihir Bellare and Chanathip Namprempre showed in 2000 that this is the order that’s safe in general.

Modern designs go one better and make one primitive that does both: authenticated encryption with associated data, or AEAD. It encrypts the message, and its tag covers both the ciphertext and any associated data: things that must be sent readable, such as an address or a sequence number, but mustn’t be changed. The two in everyday use are AES-GCM (AES in counter mode, with GHASH) and ChaCha20-Poly1305 (the stream cipher, with Poly1305). TLS 1.3, the latest version of the protocol behind the browser’s padlock, allows nothing else.

Alice’s message encrypted with AES-GCM, with “To: Bob” as associated data. Mallory tries the trick from the first page: XOR the account’s digits to turn 4821 into 6666. In counter mode alone it works (the row “without the check”), but AES-GCM checks the tag first and gives Bob nothing. So does every other change: a single flipped bit, the associated data, the tag itself. The page’s AES-GCM matches the published test cases (McGrew and Viega’s 1 to 4, in the tests) and, live, the browser’s own. The tests also check that every 7th bit flipped in the ciphertext is refused, and the page’s ChaCha20-Poly1305 against RFC 8439’s example.

One rule goes with all of these: nothing from a message may be used, or even shown, until its tag has checked. An AEAD that releases plaintext first, and checks after, has given Mallory a way in again.

Summary

A MAC is a tag only someone with the key can make: Bob recomputes it and refuses any change.
hash(key ‖ message) falls to length extension: the tag is the hash’s state, so Mallory carries on from it.
HMAC hashes twice, and doesn’t. Compare tags in constant time, or the timing gives the tag away a byte at a time.
Polynomial MACs evaluate the message at a secret point and hide the result with a one-time value: fast, and secure only if the key is never reused. Poly1305 and GHASH work this way.
Encrypt then MAC; better, use an AEAD (AES-GCM, ChaCha20-Poly1305), and use nothing until the tag checks.