§9 Message Authentication Codes

Message Authentication Code (MAC): Definition

• A Message Authentication Code (MAC) consists of three probabilistic polynomial-time algorithms $(Gen, Mac, Vrfy)$ such that:
  1. $Gen$ takes as input the security parameter $1^n$ and outputs a key $k$ with $|k| \ge n$.
  2. $Mac$ is the tag-generation algorithm that takes as input a key $k$ and a message $m \in \{0,1\}^*$ and outputs a tag $t$, i.e., $t \leftarrow Mac_k (m)$.
  3. $Vrfy$ is a deterministic verification algorithm that takes as input a key $k$, a message $m$, and a tag $t$. It outputs a bit $b$, with $b = 1$ meaning the tag is valid and $b = 0$ meaning the tag is invalid, i.e., $b := Vrfy_k (m, t)$.
• Correctness: It is required that for every $n$, every key $k$ output by $Gen (1^n)$, and every $m \in \{0,1\}^*$, it holds that $Vrfy_k (m, Mac_k (m)) = 1$.

Message Authentication Experiment $\text {Mac-forge}_{\mathscr{A}, \Pi}(n)$

• For a Message Authentication Code $\Pi = (Gen, Mac, Vrfy)$, an adversary $\mathscr A$, and security parameter $n$, define the message authentication experiment $\text {Mac-forge}_{\mathscr{A}, \Pi}(n)$ as follows:
  1. A key $k$ is generated by running $Gen (1^n)$.
  2. Adversary $\mathscr A$ is given input $1^n$ and oracle access to $Mac_k ( \cdot )$. Let $\mathscr Q$ denote the set of all queries that $\mathscr A$ asked its oracle. Adversary eventually outputs $(m, t)$.
  3. $\mathscr A$ succeeds and the experiment outputs $1$ if and only if
     1. $Vrfy_k (m, t) = 1$, and
     2. $m \notin \mathscr Q$.

MAC Security: Formal Definition

• Definition. A Message Authentication Code $\Pi = (Gen, Mac, Vrfy)$ is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all probabilistic polynomial-time adversaries $\mathscr A$, there is a negligible function $\epsilon$ such that:

  $$\Pr \left[ \text {Mac-forge}_{\mathscr{A}, \Pi}(n) =1\right] \le \epsilon(n)$$

Replay Attacks

• The MAC security definition does not prevent Replay Attacks
  • Replay Attack: Attacker simply replays a message transmitted by the sender.
  • No stateless mechanism can prevent replay attacks: $Vrfy$ cannot distinguish whether it is being given $(m, t)$ that it has seen before since it does not maintain state.
• Need to protect against replay attacks at a higher level than the MAC, by something that maintains state (typically sequence numbers (synchronized counters) and time-stamps).

A Fixed-Length MAC Construction

• Construction ${MAC}_1$: Let $F$ be a pseudorandom function. Define a fixed-length MAC for messages of length $n$ as follows:
  • $Mac$: Given input a key $k \in \{0,1\}^n$ and a message $m \in \{0,1\}^n$, output the tag $t := F_k(m)$. If $|m| \ne |k|$ then output nothing.
  • $Vrfy$: Given input a key $k \in \{0,1\}^n$, a message $m \in \{0,1\}^n$, and a tag $t \in \{0,1\}^n$, output $1$ if and only if $t = F_k(m)$. (If $|m| \ne |k|$, then output $0$.)

Security of the Fixed-Length MAC Construction

• Theorem. If $F$ is a pseudorandom function, then the Construction $MAC_1$ is a secure fixed-length MAC for messages of length $n$.

MAC for longer messages: CBC-MAC (CipherBlock Chaining) Construction

• Let $F$ be a pseudorandom function, and fix a length function $l > 0$. The basic CBC-MAC construction is as follows:
  • $Mac$: Given input a key $k \in \{0,1\}^n$ and a message $m$ of length $l(n) \cdot n$, do the following:
    1. Parse $m$ as $m = m_1, \ldots , m_l$ where each $m_i$ is of length $n$.
    2. Set $t_0 := 0^n$. Then, for $i = 1$ to $l$, set $t_i = F_k (t_{i-1} \oplus m_i)$.
    3. Output $t_l$ as the tag.
  • $Vrfy$: Given input a key $k \in \{0,1\}^n$, a message $m$, and a tag $t$, do:
    • If $m$ is not of length $l(n) ⋅ n$, then output $0$.
    • Otherwise output $1$ if and only if $t = Mac_k(m)$.

Security of the Basic CBC-MAC construction

• Theorem. Let $l$ be a polynomial. If $F$ is a pseudorandom function, then the Basic CBC-MAC construction is a secure MAC for messages of length $l(n) \cdot n$.

— Feb 21, 2023

§9 Message Authentication Codes by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.