The Verification Split: Why a MAC Cannot Settle a Dispute

A message arrives with thirty-two bytes appended. The receiver recomputes a function over the message and a shared secret, compares the result against those thirty-two bytes, and accepts. Nothing in that procedure distinguishes the sender from the receiver, and nothing in it can be shown to anyone who was not given the secret. That is the entire difference between a message authentication code and a digital signature, and most of the design consequences in this cluster follow from it.

Both mechanisms answer the same narrow question: was this exact byte string produced by someone who holds a particular secret? They differ in who is allowed to ask the question. A MAC is checked by the party that can also produce it. A signature is checked by parties that cannot.

Two algorithms, one asymmetry

A message authentication code is a family of functions indexed by a key. The sender computes $t = \mathrm{MAC}_k(M)$ and transmits the pair $(M, t)$. The receiver, holding the same $k$, recomputes $\mathrm{MAC}_k(M)$ and compares. The tag is typically 16 to 32 bytes, and the comparison must be constant-time, because a byte-by-byte comparison that exits early hands the attacker a timing oracle with which to build a valid tag one byte at a time. In Python the standard library provides the comparison primitive directly:

import hmac

def verify(key: bytes, message: bytes, tag: bytes) -> bool:
    expected = hmac.new(key, message, "sha256").digest()
    # compare_digest runs in time independent of where the first difference is
    return hmac.compare_digest(expected, tag)

A signature scheme replaces the single key with a key pair. The signer holds a private key $sk$ and publishes $pk$. The signature is $\sigma = \mathrm{Sign}{sk}(M)$, and any party holding $pk$ can run $\mathrm{Verify}{pk}(M, \sigma)$. Verification requires public data only.

The asymmetry is not a matter of efficiency. It is a matter of capability. The MAC verifier is a second signer, whether it wants to be or not: given $k$ and any message, it can construct a tag that is bit-for-bit indistinguishable from one the sender would have produced. The signature verifier has no such capability. It holds $pk$, and forging requires solving the underlying problem, whether that is factoring a modulus or computing a discrete logarithm.

This is why the two primitives have different security definitions even though both are called “unforgeable”. The definition for signatures, existential unforgeability under chosen-message attack, gives the adversary the public key and a signing oracle, and asks it to produce a valid pair $(M^, \sigma^)$ for a message it never queried. The definition for MACs gives the adversary a tagging oracle and, depending on the model, a verification oracle, but never the key. The signature definition is the stronger one because the adversary already possesses everything a legitimate verifier possesses.

What the unforgeability game leaves out

The game models an outside attacker. It does not model the key holder. In the signature game the signer is the adversary, which is exactly the point: the property being proven is that nobody else can produce a signature. Whether the key holder can later deny having signed is outside the game entirely, because the game has already assumed the key holder is the attacker.

Non-repudiation is therefore not a cryptographic property of the signature primitive. It is a claim about key custody. A valid signature demonstrates that some process in possession of $sk$ processed a particular byte string. It does not demonstrate who controlled that process, whether the controller intended the message, or when the signature was made. Those are questions for access control, hardware boundaries, and timestamping, and they fail independently of the mathematics.

The practical consequence is that a signature is evidence only relative to an assumption: that the private key was not available to anyone else. An organization that generates one key pair and copies it into three services has converted its signature scheme into a MAC with extra steps, because any of the three services can now produce a signature that the others cannot repudiate. The cryptography is unchanged; the property is gone.

Why a shared tag is not evidence

Consider a dispute over a message $M$ carrying a valid tag under key $k$, where $k$ is known to both Alice and Bob. A third party asked to adjudicate must obtain $k$ to check the tag. Once it has $k$, it can produce the tag itself. The evidence is therefore consistent with three hypotheses at once: Alice sent $M$, Bob sent $M$, and the adjudicator fabricated $M$. No amount of arithmetic separates them, because the tag is a deterministic function of public data and a secret that all three now share.

This is not a defect that better MAC constructions repair. It is a consequence of the verification capability being symmetric. The only ways around it are to change who holds the key or to add a trusted party. If a server holds $k$ and clients do not, then a tag from a client is evidence that the client knew $k$, which reduces to an access-control claim. If an arbiter holds $k$ and both parties do not, the arbiter is trusted not to forge, and the scheme has merely relocated the trust assumption. A MAC can be turned into something resembling a signature by involving a notary that witnesses each tag, but the notary is now the security boundary.

Deniability is sometimes the goal rather than the obstacle. In a mutually authenticated channel between two peers who share a session key, neither peer can prove to an outsider what the other sent, because both could have computed the record tag. Protocols that want this property choose a MAC deliberately. Protocols that need a message to remain attributable after the connection closes cannot use one.

The price of public verification

Moving verification to the public side costs bytes and cycles. An HMAC-SHA-256 tag is 32 bytes, and producing or checking it costs two hash computations: the inner hash over the key pad and the message, and the outer hash over the other key pad and the 32-byte inner digest. Only the inner one scales with message length. An Ed25519 signature is 64 bytes with a 32-byte public key, and verification costs a double scalar multiplication on a 255-bit curve, which is thousands of times more expensive than a hash compression. An RSA-2048 signature is 256 bytes, the size of the modulus, and verification with a small public exponent is comparatively cheap because it needs only a handful of modular squarings and multiplications; signing is the expensive direction.

Key management scales differently as well. A group of $n$ parties using MACs needs $\binom{n}{2}$ pairwise keys if every pair must communicate, and every one of those keys is a forgery capability held by two parties. The same group using signatures needs $n$ key pairs and a mechanism for binding each public key to an identity, which is a naming and distribution problem rather than a secrecy problem. Public keys can be published; shared MAC keys cannot.

There is a middle ground worth naming. A MAC key can be derived per message from a master secret, so that compromise of one derived key does not compromise the others, and a signature can be produced by a service that holds the key on behalf of many users. Both arrangements are useful, and both move the trust boundary rather than removing it. The primitive determines what is mathematically possible; the deployment determines who is actually accountable.

Where the guarantee stops

A signature over a byte string says nothing about whether that byte string is a sensible message. Signature verification is separate from parsing, and the gap between them has produced real forgeries when a verifier accepted an encoding that the signer would never have produced. The same separation applies to MACs: a valid tag on a record does not establish that the record belongs to the current session, which is why authenticated channels bind a sequence number or nonce into the tagged data rather than tagging the payload alone. The construction details that make this binding sound are the subject of why HMAC hashes twice and of the block-cipher construction in CBC-MAC’s last block.

For signatures, the analogous failure is treating the signature bytes as an identifier. Several schemes admit more than one valid encoding of the same signature, so two byte strings can both verify for the same message. Any protocol that deduplicates or indexes by signature bytes must either canonicalize them or use a separate identifier. The nonce handling that determines whether this malleability exists in ECDSA is covered in ECDSA nonce reuse.

The guarantee that survives all of this is narrow and worth stating precisely. Given an uncompromised private key, a message encoding that both sides agree on, and a verifier that checks the encoding strictly, a valid signature is evidence that the private key was used on that byte string. Given an uncompromised shared key and the same conditions, a valid tag is evidence that some holder of the key processed that byte string. Everything else, including identity, authority, time, and intent, is supplied by systems outside the primitive. A MAC that is one-time, such as Poly1305, narrows the window in which the key can be abused; it does not widen what the tag proves.