# Exercise 4.14

### Problem

Prove that the following modifications of basic CBC-MAC do not yield a secure MAC (even for fixed-length messages):

1. Mac outputs all blocks $$t\_1, \ldots , t\_l$$rather than just $$t\_l$$. (Verification only checks whether $$t\_l$$ is correct.)
2. A random initial block is used each time a message is authenticated. That is, choose uniform $$t \in {0, 1}^n$$, run basic CBC-MAC over the “message” $$t\_0,m\_1, \ldots ,m\_l$$, and output the tag $$\langle t\_0, t\_l \rangle$$. Verification is done in the natural way.

### Solution

#### Part 1

Query

* $$m^1 = B\_0 || B\_1$$, $$t^1 = t\_0 || t\_1$$
* $$m^2 = B\_2 || B\_3$$, $$t^2 = t\_2||t\_3$$

We know $$F\_k(B\_0) = t\_0$$ and $$F\_k(B\_2) = t\_2$$. Hence 

$$
MAC\_k(B\_0 || B^*\_2) = F\_k(B\_0) || F\_k(F\_k(B\_0) \oplus B^*\_2) = t\_0 || F\_k(t\_0 \oplus B^\*\_2)
$$

Let $$t\_0 \oplus B^*\_2 = B\_2$$, i.e., $$B^*\_2 = t\_0 \oplus B\_2$$. Then

$$
MAC\_k(B\_0 || t\_0 \oplus B\_2) = t\_0 || F\_k(t\_0 \oplus t\_0 \oplus B\_2) = t\_0 || F\_k(B\_2) = t\_0 || t\_2
$$

Therefore, $$\langle B\_0 || t\_0 \oplus B\_2, t\_0 || t\_2 \rangle$$ is a valid pair of message and tag.

#### Part 2

Query

* $$m^1 = B\_0 || B\_1$$, $$t^1 = \langle r\_1, t\_1 \rangle$$
* $$m^2 = B\_2 || B\_3$$, $$t^2 = \langle r\_2, t\_2 \rangle$$

Hence for $$m^\* = B\_0 || B\_1 || t\_2 \oplus r\_2 || B\_2 || B\_3$$, $$t^\* = \langle r, t\_2 \rangle$$ should be a valid tag.