Exercise 4.7

Problem

Let $F$ be a pseudorandom function. Show that each of the following MACs is insecure, even if used to authenticate fixed-length messages. (In each case Gen outputs a uniform $k \in \{0, 1\}^n$. Let $\langle i \rangle$ denote an $n/2$-bit encoding of the integer $i$.)

1. To authenticate a message $m = m_1, \ldots ,m_l$ where $m_i \in \{0, 1\}^n$, compute $t := F_k(m_1) \oplus \cdots \oplus F_k(m_l)$.

2. To authenticate a message $m = m_1, \ldots ,m_l$ where $m_i \in \{0, 1\}^{n/2}$, compute $t := F_k(\langle 1 \rangle || m_1) \oplus \cdots \oplus F_k(\langle l \rangle || m_l)$.

3. To authenticate a message $m = m_1, \ldots ,m_l$ where $m_i \in \{0, 1\}^{n/2}$, choose uniform $r \leftarrow \{0, 1\}^n$, compute $t := F_k(r) \oplus F_k(\langle 1 \rangle || m_1) \oplus \cdots \oplus F_k(\langle l \rangle || m_l)$, and let the tag be $\langle r, t \rangle$

Solution

Part 1

Reorder the blocks in $m$ and the tag doesn't change.

Part 2

Query

• $m^1 = m_1 || m_2$, tag $t_1 = F_k(\langle 1 \rangle || m_1) \oplus F_k(\langle 2 \rangle || m_2)$

• $m^2 = m_3 || m_2$, tag $t_2 = F_k(\langle 1 \rangle || m_3) \oplus F_k(\langle 2 \rangle || m_2)$

• $m^3 = m_3 || m_4$, tag $t_3 = F_k(\langle 1 \rangle || m_3) \oplus F_k(\langle 2 \rangle || m_4)$

Thus $m^* = m^1 \oplus m^2 \oplus m^3 = m_1 || m_4$, tag $t = t_1 \oplus t_2 \oplus t_3 = F_k(\langle 1 \rangle || m_1) \oplus F_k(\langle 2 \rangle || m_4)$.

Part 3

Let $m \in \{0, 1\}^{n/2}$. When choosing $r = \langle 1 \rangle || m$, $t = F_k(r) \oplus F_k(\langle 1 \rangle || m) = 0^n$.

Thus $t = \left\langle \langle 1 \rangle || m, 0^n \right\rangle$ will be a valid tag for $m$.