Message authentication code

From CRYPTUTOR

(Redirected from MAC)

A message authentication code (MAC) is a scheme for two parties who share a private key to achieve an unforgeable communication channel.

[edit]

Definition

A MAC scheme consists of the following 3 algorithms:

Key generation (KeyGen): a probabilistic algorithm that takes the implicit security parameter of the scheme as input, and outputs a key.
MAC: an algorithm that takes a key and a message as input, and outputs a tag. We generally write $\mathsf{MAC}(k,m)$ as $\mathsf{MAC}_k(m)$ .
Verification (Ver): An algorithm that takes a key, a message, and a tag as input, and outputs a bit. As above, we generally write $\mathsf{Ver}(k,m,\tau)$ as $\mathsf{Ver}_k(m, \tau)$ .

These algorithms must satisfy the following properties:

Efficiency: All three algorithms run in polynomial time in the security parameter.
Correctness: For all $k \gets \mathsf{KeyGen}$ , and all messages $m$ , $\mathsf{Ver}_k( m, \mathsf{MAC}_k(m) ) = 1$
Unforgeability: For all non-uniform PPT (polynomial in the security parameter) adversaries $A$ , the probability that $A$ succeeds in the following experiment is negligible (in the security parameter):

MAC Unforgeability Experiment:

We choose a key $k \gets \mathsf{KeyGen}$ .
$A$ is allowed to query oracles that compute $\mathsf{MAC}_k$ and $\mathsf{Ver}_k$ .
$A$ outputs a message/tag pair $(m,τ)$ , with the restriction that the $\mathsf{MAC}_k$ oracle was never queried on input $m$ .
We say that $A$ succeeds if $\mathsf{Ver}_k(m,\tau) = 1$ .

[edit]

Repudiation

MACs are natural to use for authenticated communcation. However, MAC schemes have an undesirable property called repudiation, which means that it is impossible to prove (to an outside party) that a particular person generated a MAC. Consider the following example:

Suppose Alice and Bob are using a MAC scheme, with a common private key. Alice sends Bob a message and "signs" it by giving a MAC of the message. If the MAC verifies, Bob can be convinced that the message came from Alice. But suppose that later, he needed to convince someone else that Alice sent this message.

Bob publishes the message, Alice's MAC, and their private key, as "proof" (which anyone can now easily verify) that Alice generated the MAC. However, since Bob was in posession of the same private key, he could have been the one who generated the MAC! Alice can legimitely deny (repudiate) the fact that she generated the MAC.

When non-repudiation is needed, it is necessary to use a digital signature scheme, which uses public keys.

[edit]