Message Authentication Codes (MACs)

Core Idea

A MAC is a keyed function that takes a secret key and a message and produces a short tag. The sender transmits (message, tag); the receiver recomputes the tag with the shared key and checks for a match. Security requires existential unforgeability under chosen-message attack (EUF-CMA): an adversary who can obtain tags on messages of their choice still cannot forge a valid tag on any new message. HMAC (hash-based) and CBC-MAC (block-cipher-based) are the main constructions. MACs provide integrity and authenticity but not confidentiality — the message is sent in the clear alongside the tag.

Explainer

Encryption protects confidentiality — it hides what you said. But it does not protect integrity — it cannot tell you whether what arrived is what was sent. Standard encryption modes are malleable: an attacker can modify ciphertext in ways that produce controlled changes in the decrypted plaintext. Flipping a bit in CTR-mode ciphertext flips the corresponding plaintext bit. Without a separate integrity mechanism, the recipient decrypts tampered ciphertext into tampered plaintext and cannot detect the manipulation. A Message Authentication Code (MAC) fills this gap.

A MAC is a keyed function: Tag = MAC(key, message). The sender transmits both the message and the tag. The receiver, who shares the secret key, recomputes the tag and checks that it matches. If it does, the message has not been tampered with and was produced by someone who knows the key. The formal security definition is EUF-CMA (existential unforgeability under chosen-message attack): even an adversary who can request tags on any messages of their choosing cannot forge a valid tag on any message they haven't already queried. This is a strong guarantee — the attacker has adaptive access to a tagging oracle and still cannot cheat.

The two main constructions are HMAC and CBC-MAC. HMAC is built from a hash function: HMAC(k, m) = H((k XOR opad) || H((k XOR ipad) || m)), where ipad and opad are fixed constants. The nested structure prevents length extension attacks that plague the naive H(key || message) construction. HMAC is provably secure under the assumption that the hash's compression function is a pseudorandom function — a weaker assumption than collision resistance, which means HMAC can remain secure even if collision attacks on the hash are found. CBC-MAC encrypts the message in CBC mode and uses the final block as the tag. It is provably secure for fixed-length messages but requires modifications (CMAC, EMAC) for variable-length messages due to specific forgery attacks.

A critical limitation of MACs is that they provide authentication but not non-repudiation. Since both parties share the same key, either could have produced the tag — the receiver cannot prove to a third party that the sender specifically created the message, because the receiver could have forged it. Digital signatures, which use asymmetric cryptography, solve this by letting only the private key holder sign while anyone can verify. For many protocols, MACs suffice (two parties who already trust each other), but wherever proof of origin matters — legal documents, financial transactions, software distribution — signatures are needed instead.