The MAC: an authentication code with a key

To tie a fingerprint to a sender, we replace the bare hash with a message authentication code, or MAC.

The definition

A MAC is a function that takes two inputs and produces a short tag:

tag = MAC(secret_key, message)

This tag is often called a tag or authentication code. The crucial point: without the key, you cannot compute the correct tag for a given message.

The full protocol

Alice and Bob share a same secret key K in advance. The exchange goes as follows:

   ALICE (key K)                         BOB (key K)
   ------------                          -----------
   tag = MAC(K, M)
        |
        |   sends   [ M ] [ tag ]
        +----------------------------------->  receives M, tag
                                               tag' = MAC(K, M)
                                               tag' == tag  ?
                                                 yes -> accepts
                                                 no  -> rejects

Bob recomputes the tag himself from the received message and his copy of the key. If his result tag' is identical to the received tag, he has proof of two things at once: the message has not changed (integrity) and it comes from someone who knows K, hence from Alice (authenticity).

Why Mallory fails

Let us return to the active attacker from the previous chapter. Mallory wants to substitute M'. She would need to attach MAC(K, M'). But she does not know K. She therefore cannot produce any valid tag, and Bob rejects the forged message.

MAC versus signature

MAC and digital signature are sometimes confused. Both authenticate, but the key model differs profoundly:

	MAC	Signature
Key type	symmetric (shared)	asymmetric (private/public)
Who can create a tag	both parties	only the holder of the private key
Who can verify	those who have the key	everyone (public key)
Non-repudiation	no	yes

Since Alice and Bob share the same key, a MAC does not prove which of the two sent the message: either one could have produced the tag. It therefore does not offer non-repudiation. In exchange, it is far faster than a signature and is enough when the two parties trust each other.

In summary

A MAC combines a secret key and a message to produce a tag that only a holder of the key can compute. The sender sends message + tag; the receiver recomputes the tag with the shared key and compares. This guarantees integrity and authenticity at once. Unlike a signature (asymmetric key, verifiable by all, non-repudiation), the MAC relies on a shared symmetric key: faster, but without proof of the exact sender.