# 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$$.