Message Authentication Codes

A Message Authentication Code is a triple of algorithms `(Gen, MAC, Verify)`. `Gen` produces a secret key `k`. `MAC_k(m)` deterministically (in the constructions we study) maps a message `m` to a short tag `t`. `Verify_k(m, t)` outputs accept or reject, and for correctness must accept whenever `t = MAC_k(m)`. The security goal is existential unforgeability under chosen-message attack (EUF-CMA): an adversary who can query `MAC_k(·)` adaptively on messages of its choice should still be unable to produce a valid `(m, t)` pair for any `m*` it did not query, except with negligible probability. This is fundamentally different from encryption. A MAC says nothing about confidentiality — the message may be sent in the clear alongside its tag — and it is symmetric, unlike a digital signature, meaning anyone who can verify a tag also holds the key needed to forge one. That asymmetry matters: MACs authenticate data between parties who already share a secret (e.g., two ends of a TLS connection after a handshake), whereas signatures authenticate to arbitrary third parties. MACs are typically built either from a block cipher treated as a pseudorandom permutation (CBC-MAC, CMAC) or from a cryptographic hash function (HMAC), and their security proofs bottom out in the PRF/PRP assumption on the underlying primitive. A recurring theme is that naive constructions that look secure for fixed inputs often break for variable-length inputs. The chaining structure that makes CBC-MAC secure on fixed-length messages creates an exploitable linearity once message lengths vary, and the iterative Merkle–Damgård structure that makes hash functions efficient creates a length-extension vulnerability once you key them naively. Both CMAC and HMAC exist specifically to close these gaps while reusing the same underlying primitive and roughly the same performance envelope.

The EUF-CMA security game

Formally, security is defined via an experiment between a challenger and adversary `A`: ``` Experiment Forge_A(n): k ← Gen(1^n) A is given oracle access to MAC_k(·) A queries m_1, ..., m_q and receives t_1, ..., t_q A outputs (m, t) A wins if Verify_k(m, t) = accept AND m ∉ {m_1, ..., m_q} ``` `MAC` is EUF-CMA secure if, for every probabilistic polynomial-time `A`, ``` Pr[A wins Forge_A(n)] ≤ negl(n) ``` This single definition covers replay of an old (message, tag) pair as not a forgery (since `m` must be new) — replay protection is a separate concern usually handled with sequence numbers or timestamps layered on top of the MAC.

CBC-MAC: chaining a block cipher

Given a block cipher `E` with block length `n` (a PRP), and a message split into full blocks `m_1, ..., m_ell`, raw CBC-MAC computes: ``` CBC-MAC(k, m_1, ..., m_ell): c_0 = 0^n for i = 1 to ell: c_i = E_k(m_i XOR c_{i-1}) return c_ell # the tag is the LAST ciphertext block only ``` This resembles CBC encryption but discards all intermediate blocks and outputs only the final one — releasing intermediate ciphertexts would leak enough structure to forge tags trivially.

Why raw CBC-MAC breaks for variable length. Suppose an adversary learns `t = CBC-MAC(k, m)` for a single one-block message `m`. Then `t = E_k(m)`. Consider the two-block message `m ‖ (t XOR m)`: ``` c_1 = E_k(m) = t c_2 = E_k((t XOR m) XOR c_1) = E_k((t XOR m) XOR t) = E_k(m) = t ``` So the tag for the crafted two-block message equals `t`, the same tag the adversary already obtained for the single-block message — an unqueried message with a known-valid tag, i.e. a forgery, with zero additional oracle calls. This is why raw CBC-MAC is only proven secure when all messages have the same, fixed, publicly known length.

CMAC: fixing variable length with derived subkeys

CMAC (and its precursor OMAC) repairs this by deriving two subkeys `k1, k2` from `k` via multiplication in `GF(2^n)`, and XOR-ing one of them into the last block before the final encryption — differently depending on whether the last block is a full block or needs padding. ``` CMAC-Gen(k): L = E_k(0^n) k1 = L << 1; if MSB(L) == 1: k1 = k1 XOR R_b # R_b is a fixed constant (e.g. 0x87 for n=128) k2 = k1 << 1; if MSB(k1) == 1: k2 = k2 XOR R_b return (k1, k2) CMAC(k, m): (k1, k2) = CMAC-Gen(k) split m into blocks m_1, ..., m_ell of size n if m is empty: ell = 1; m_1 = pad10(empty) # single padded block if last block m_ell is a full n-bit block: m_ell' = m_ell XOR k1 else: m_ell' = pad10(m_ell) XOR k2 # pad with 1 then 0s to length n c_0 = 0^n for i = 1 to ell - 1: c_i = E_k(m_i XOR c_{i-1}) c_ell = E_k(m_ell' XOR c_{ell-1}) return c_ell ``` The two distinct subkeys ensure that a full final block and a padded final block can never collide into the same input to the last encryption call, which is precisely the gap the earlier forgery exploited. CMAC is standardized (NIST SP 800-38B) and used in protocols like AES-CMAC for network authentication.

HMAC: keying a hash function safely

Most cryptographic hash functions (SHA-256, SHA-1) are built with the Merkle–Damgård construction, iteratively compressing fixed-size blocks. A naive MAC `H(k ‖ m)` is broken by the length-extension attack: because the internal state of a Merkle–Damgård hash is exactly its output, anyone who knows `H(k ‖ m)` can compute `H(k ‖ m ‖ pad ‖ m')` for chosen `m'` without knowing `k`, by resuming the compression function from the leaked state. HMAC avoids this with a nested structure: ``` HMAC(k, m): b = block size of H (e.g., 64 bytes for SHA-256) if len(k) > b: k = H(k) # shrink oversized keys k = k padded with zero bytes to length b ipad = 0x36 repeated b times opad = 0x5c repeated b times inner = H( (k XOR ipad) ‖ m ) return H( (k XOR opad) ‖ inner ) ``` Because the outer hash call's input is `(k XOR opad) ‖ inner`, and `inner` is already a finished hash digest (not an intermediate state that continues the same Merkle–Damgård chain from the attacker's chosen point), an attacker who only observes `HMAC(k, m)` cannot extend it the way they could extend `H(k ‖ m)`. The key is mixed in twice, at the very start of two logically separate hash computations, rather than once at the start of a single one.

Time and space.

• CBC-MAC / CMAC: `ell = ⌈|m| / n⌉` block-cipher calls, each `O(1)` time (a constant-size AES/DES operation), so total time is `O(|m|)`. Space is `O(n)` — only the running chaining value is kept, independent of message length. This is optimal: any MAC must read every bit of the message at least once, so `Ω(|m|)` time is a lower bound, matched here.
• HMAC: two hash computations, but the outer one hashes only a single already-fixed-size block plus a short digest, so total work is `O(|m|)` block-compressions plus `O(1)` extra compression, i.e. still linear in message length with a small constant-factor overhead (roughly one extra compression-function call versus a plain hash).
• Key/subkey derivation: CMAC's subkey generation costs one extra block-cipher call per key setup, amortized over all messages MAC'd under that key — effectively free in practice.

Correctness (verification agrees with generation). Both constructions are deterministic functions of `(k, m)`, so `Verify_k(m, t)` simply recomputes the tag and checks equality; correctness (accepting genuine tags) is immediate. The substance is the unforgeability argument.

Why CMAC is secure — proof sketch. Model `E_k` as a random permutation (the PRP assumption). The CBC chaining computes a function of the message blocks that, absent the final subkey step, is vulnerable exactly at points where two different messages can be engineered to produce colliding inputs to the last encryption call (as in the length-extension forgery shown above). CMAC's use of two distinct, key-derived subkeys `k1 ≠ k2`, applied conditionally based on whether padding was needed, provably eliminates such collisions between "clean-final-block" and "padded-final-block" cases — this is the core lemma in the OMAC/CMAC security proof, reducing forgery probability to roughly `O(q^2 ell_max / 2^n)` where `q` is the number of MAC queries and `ell_max` the maximum message length in blocks, via a standard PRP/PRF switching-lemma argument. As long as `q^2 ell_max ≪ 2^n`, forgery is negligible; for `n = 128` (AES) this holds for any realistic query budget.

Why HMAC is secure — proof sketch. The Bellare–Canetti–Krawczyk analysis shows HMAC is a secure PRF (hence a secure MAC, since any PRF is trivially a MAC via `MAC_k(m) = F_k(m)`) provided the underlying compression function, keyed appropriately, behaves as a PRF itself — a considerably weaker and more plausible assumption than requiring the whole hash to be collision-resistant. Intuitively: the inner hash randomizes the message into a fixed-length digest under a keyed compression function; the outer hash then re-randomizes that digest under an independently-keyed compression function. An adversary attempting length-extension against the outer call would need to extend from `inner`, but the outer call's own key material (`k XOR opad`) is unknown and distinct from what produced `inner`, so the chain the adversary can extend and the chain the challenger actually computed are keyed differently — breaking the exact symmetry length-extension needs.

Tradeoffs. CMAC needs a block cipher and subkey derivation logic (slightly more implementation surface, sensitive to correct padding-branch handling) but is very fast in hardware with AES-NI. HMAC reuses widely available, heavily optimized hash implementations and needs no dedicated block-cipher schedule, but pays roughly double a single hash call and inherits the (larger) hash's output/block-size parameters. Neither provides confidentiality; neither prevents replay by itself.

Trace HMAC-SHA256 conceptually (values abbreviated to illustrate structure, not literal SHA-256 output):

Now suppose an attacker, without the key, observes `(m, t)` and tries the naive-MAC length-extension attack that would work against plain `H(k ‖ m)`: they attempt to compute `H(k ‖ m ‖ pad ‖ "amt=999999")` by resuming from `t` as if it were an internal Merkle–Damgård chaining state. This fails against HMAC because `t` is the output of the outer hash call, keyed with `k XOR opad`, not the internal state of a hash chain that continues encoding `m`. There is no compression-function state the attacker can feed forward — `t` is a finished digest of an unrelated (from the attacker's view) short input `(k XOR opad) ‖ inner`. The attacker is stuck needing to invert or extend a keyed hash call whose key they don't know, which is exactly the PRF assumption HMAC relies on. Contrast with CBC-MAC on a fixed 16-byte AES block: if the attacker knows `t = E_k(m)` for one-block `m`, they can compute a valid tag for the crafted two-block message `m ‖ (t XOR m)` as derived earlier — no key needed, pure arithmetic on known values. This is the concrete forgery CMAC's subkeys are designed to prevent, since with subkeys the final input becomes `m_ell' XOR k1` or `m_ell' XOR k2` depending on padding, and the attacker's crafted second block no longer collides in the same exploitable way.

TLS record protection uses HMAC (in TLS 1.2 cipher suites and as part of HKDF key derivation in TLS 1.3) to authenticate every record exchanged between client and server. IPsec's AH and ESP protocols use HMAC-SHA variants to authenticate packets at the network layer. AES-CMAC secures Bluetooth Low Energy pairing and is used in banking and smartcard protocols (EMV) where a dedicated block cipher is already present in hardware. Authenticated encryption modes like AES-GCM and the encrypt-then-MAC composition in many VPN and messaging protocols rely on MAC-like tags (GCM uses a GHASH-based universal-hash MAC, conceptually related but distinct) to bind ciphertext integrity to the encrypted payload. API request-signing schemes (AWS Signature Version 4, webhook signature verification) use HMAC directly to let a client prove possession of a shared secret without transmitting it. Anywhere two parties share a symmetric secret and need tamper-evidence without the cost of public-key signatures, a MAC — almost always HMAC or CMAC in practice — is doing the work.

Ask the tutor: How does the security proof for CMAC formally handle the difference between full and padded final blocks using the PRP switching lemma?