Message Authentication Code

Also known as MAC. A keyed function that produces a short tag $t$ for a message $m$, proving the message came from a holder of the key and was not altered.

The sender transmits $(m, t)$. The receiver recomputes $\text{MAC}_k(m)$ and accepts iff it equals $t$.

History

Early MACs came from banking, where interbank transfers needed to be authenticated.

• 1981
  ANSI X9.9 defines a DES based MAC for wholesale banking.
• 1985
  FIPS 113 standardizes CBC-MAC.
• 1996
  Bellare, Canetti and Krawczyk propose HMAC.
• 1997
  HMAC is published as RFC 2104.
• 2000
  Bellare, Kilian and Rogaway prove CBC-MAC secure for fixed-length messages.
• 2002
  HMAC is standardized in FIPS 198.
• 2005
  CMAC is standardized in NIST SP 800-38B.

Properties

• Integrity
  Any change to $m$ changes the tag.
• Authenticity
  Only a holder of the shared key $k$ can produce a valid tag.
• No non-repudiation
  Both parties hold $k$, so a tag cannot prove which of them created it.

A hash function alone gives no authenticity, since an attacker can alter $m$ and recompute the public digest.

Forgery Security

A MAC is secure iff it is existentially unforgeable under a chosen-message attack.

The attacker may request tags for any messages of their choice. The attacker wins by producing a valid tag for any message not yet queried, even a meaningless one.

The tag length bounds security. An $n$-bit tag lets a random guess succeed with probability $2^{-n}$.

Verification Requirements

MAC verification confirms authenticity and integrity. It does not confirm that a message is new.

• Constant time comparison
  Comparing tags byte by byte and stopping at the first mismatch leaks the matching prefix length through timing, letting an attacker forge a tag one byte at a time.
• Replay
  An attacker can capture a valid $(m, t)$ pair and send it again. The receiver accepts it because both $m$ and $t$ are unchanged. Include a sequence number or timestamp in $m$. The receiver rejects a repeated sequence number or an expired timestamp.

Block-Cipher MACs

CBC-MAC

Encrypts the message with a block cipher in CBC mode using a zero IV. The tag is the final ciphertext block.

It is secure only when all messages have the same fixed length. For variable lengths, an attacker forges as follows.

• Obtain $t_1 = \text{MAC}_k(m_1)$ and $t_2 = \text{MAC}_k(m_2)$ for single-block messages.
• The message $m_1 \,\|\, (m_2 \oplus t_1)$ has tag $t_2$.

The forged message has 2 blocks. CBC-MAC processes the first block $m_1$ before processing the second block $m_2 \oplus t_1$.

Fixes:

• Length prefix
  Prepend the message length as the first block.
• CMAC Also known as OMAC. XOR a key derived subkey into the last block before the final encryption.
• ECBC-MAC
  Encrypt the final tag again under a second key.

Hash-Based MACs

Hash functions are faster than block ciphers in software and were freely exportable, so MACs built from them were attractive. Turning a keyless hash into a keyed one needed care.

• Secret prefix
  $H(k \,\|\, m)$ breaks under length extension on Merkle–Damgård hashes. Knowing $H(k \,\|\, m)$ gives a valid tag for $m \,\|\, \text{pad} \,\|\, x$.
• Secret suffix
  $H(m \,\|\, k)$ resists length extension. A collision $H(m) = H(m')$ still gives $H(m \,\|\, k) = H(m' \,\|\, k)$, so the MAC is only as strong as the collision resistance of $H$.
• Envelope
  $H(k \,\|\, m \,\|\, k)$ was an early patch. Its security was not proved, which led to HMAC.

HMAC

Also known as Hash-based MAC. Nests 2 hash calls under 2 keys derived from $k$.

The outer hash hides the inner digest, which defeats length extension.

Bellare, Canetti and Krawczyk proved HMAC secure if the compression function of $H$ is a pseudorandom function. Collision resistance of $H$ is not required. HMAC-MD5 and HMAC-SHA-1 therefore stayed unbroken after collisions were found in MD5 and SHA-1, though new designs use HMAC-SHA-256.

HMAC is used in TLS, IPsec, JWT and as the core of HKDF in key derivation functions.

Universal Hash MACs

Faster than HMAC for small messages. Compresses the message using a secret key, then a block cipher or stream cipher masks the result. This is the Carter–Wegman construction.

Examples:

• Poly1305 by Daniel Bernstein, 2005
• GMAC, the authentication part of AES-GCM, 2004

Encryption and Authentication

Encryption alone does not detect tampering. See malleability.

• Encrypt-then-MAC
  Encrypt $m$ to $c$, then send $(c, \text{MAC}_{k_2}(c))$. This is the secure composition. The receiver rejects tampered ciphertext before decrypting.
• MAC-then-encrypt
  Used in older TLS. Padding errors during decryption leaked information, enabling padding oracle attacks.
• Encrypt-and-MAC
  Used in SSH. The tag of the plaintext can leak information about the plaintext.

The encryption key and the MAC key must be different.