Message authentication code

A Message Authentication Code (MAC) allows a user holding a secret key to authenticate messages by attaching a short tag. Anyone with the same key can verify the tag’s authenticity; anyone without the key cannot forge a valid tag, even after seeing many legitimate message-tag pairs.

Syntax

A MAC is a triple of efficient algorithms $\mathsf{MAC}=(\mathsf{KeyGen},\mathsf{Tag},\mathsf{Vrfy})$ with respect to keyspace $\mathcal{K}$, message space $\mathcal{M}$, and tag space $\mathcal{T}$:

• $\mathsf{KeyGen}(1^{\lambda })\to k,$ is a randomized algorithm that samples a key $k\in \mathcal{K},$
• $\mathsf{Tag}(k,m)\to t,$ is a (possibly randomized) algorithm that takes a key $k\in \mathcal{K}$ and message $m\in \mathcal{M}$, outputting a tag $t\in \mathcal{T},$
• $\mathsf{Vrfy}(k,m,t)\to b,$ is a deterministic algorithm that takes a key $k\in \mathcal{K}$, message $m\in \mathcal{M}$, and tag $t\in \mathcal{T}$, outputting a bit $b\in \{0,1\}$ indicating whether the tag is valid.

Properties

Correctness

A MAC $\mathsf{MAC}$ is correct if for all $k\in \mathcal{K}$ and $m\in \mathcal{M}$,

$$\mathsf{Vrfy}(k,m,\mathsf{Tag}(k,m))=1.$$

Unforgeability

The following is the unforgeability under chosen message attacks (UF-CMA) game. This security notion requires that an adversary cannot produce a valid tag for any message it did not previously query, even after seeing arbitrarily many message-tag pairs.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\ufcma}_{\MAC,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$
\State $\calQ \gets \{\}$
\State $(\hat{m}, \hat{t}) \gets \calA^{\calO}(1^\secpar)$
\If{$\hat{m} \in \calQ$}
\Comment{$\hat{m}$ cannot repeat}
\Return $0$
\EndIf
\Return $[\Vrfy(k, \hat{m}, \hat{t}) = 1]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m)$}
\begin{algorithmic}
\State $\calQ \gets \calQ \cup \{m\}$
\State $t \gets \Tag(k, m)$
\Return $t$
\end{algorithmic}
\end{algorithm}

A MAC $\mathsf{MAC}$ is UF-CMA secure if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{MAC},\mathcal{A}}^{\mathrm{uf}\text{-}\mathrm{cma}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{MAC},\mathcal{A}}^{\mathrm{uf}\text{-}\mathrm{cma}}(\lambda )=1\right]$$

is negligible.

Variations

Deterministic MACs

When $\mathsf{Tag}$ is deterministic, security still holds under the same UF-CMA game. In this case the tag is a pure function of the key and message.

PRF-based MACs

A simple and common construction: set $\mathsf{Tag}(k,m):=\mathsf{Eval}(k,m)$ for a PRF $(\mathsf{KeyGen},\mathsf{Eval})$. The UF-CMA security of the resulting MAC follows directly from the PRF’s pseudorandomness.

Other results

• MACs can be constructed from PRFs
• CPA-secure SKE can be boosted to CCA-secure SKE using a MAC (encrypt-then-MAC construction)