Message authentication codes and HMAC

Message authentication needs a function that generates an authenticator, a value used to authenticate a message, which a higher-level protocol then checks. Three classes of function can generate one:

Hash function alone. Insufficient on its own, an unprotected hash is exactly the person-in-the-middle weakness from the previous topic.

Symmetric message encryption. Encrypting with a shared key lets the receiver infer the message came from someone who knows the key, but an attacker can still flip bits of the ciphertext without knowing that key. If the plaintext happens to be an arbitrary bit sequence, the receiver has no way to tell the resulting decrypted garbage from a genuine message.

Public-key encryption. Plain public-key encryption gives confidentiality but not authentication: anyone can encrypt a forged message with the recipient’s public key and substitute it undetected. Encrypting with the sender’s private key instead gives authentication (only the sender could have produced it) but drops confidentiality, since anyone with the sender’s public key can decrypt it. Combining both, sign with the sender’s private key, then encrypt with the receiver’s public key, gives both properties, at the cost of running the public-key algorithm four times per message instead of two.

The MAC itself. A fixed-size tag, generated from the message and a secret key shared by both parties, and appended to the message. Also called a cryptographic checksum.

The receiver recomputes the MAC on the received message with the shared key and compares it to the one that was sent. Assuming the key is known only to sender and receiver, a match assures the receiver of three things: the message was not altered (an attacker without the key cannot produce a matching MAC for a modified message), the message’s origin (only a key holder could have generated a valid MAC), and, if a sequence number is included, that it was not tampered with either.

A MAC by itself provides none of this alongside confidentiality. Confidentiality is layered on separately, by encrypting either before or after the MAC computation.

A function used as a MAC must satisfy two requirements. First, it must have the resistance properties of a cryptographic hash function. Second, given a message $m$ and its MAC $t$, it must be computationally infeasible to predict a correct MAC for a different message $m' \neq m$, even when other $(m, t)$ pairs are known. A cryptographic hash function satisfies the first requirement on its own; mixing in a secret satisfies the second, provided the resistance properties still hold once the secret is added.

HMAC is the most widely used way to build a MAC from a hash function: published as RFC 2104, mandatory for IPsec, used in SSL, and standardised by NIST as FIPS 198.

In the notation the lecture uses for the structure: $b$ is the number of bits in one block, $L$ the number of blocks in $M$, $K^+$ is $K$ padded with zeros on the left to reach $b$ bits, $Y_i$ is the $i$-th block of $M$ for $0 \leq i \leq L-1$, and $n$ is the length of the hash code $H$ produces.

Security of HMAC. The security of any hash-based MAC depends on the strength of the underlying hash. What makes HMAC specifically appealing is that its designers proved an exact relationship between the strength of the embedded hash function and the strength of HMAC built on top of it.