# CBC-MAC insecure with random IV

1. Prove that the following modification of $$\operatorname{CBC-MAC}$$ does not yield a secure fixed-length $$\operatorname{MAC}$$:

Modify $$\operatorname{CBC-MAC}$$ so that a random $$IV$$ is used each time a tag is computed (and the $$IV$$ is output along with $$t_l$$). I.e., $$t_0 \leftarrow \{0, 1\}^n$$ is chosen uniformly at random rather than being fixed to $$0^n$$, and the tag is $$t_0, t_l$$.

Answer. The scheme is not secure. In particular, let $$m$$ be a one-block message and let $$(IV, t)$$ be its $$\operatorname{MAC}$$-tag received from the oracle. Then, the tag $$(m, t)$$ is a valid $$\operatorname{MAC}$$ for the message $$IV$$. (More generally, for any $$m'$$ the tag $$(IV \oplus m', t)$$ is a valid $$\operatorname{MAC}$$ for the message $$m \oplus m'$$. This means that it is possible to generate a forgery for any desired single-block message.)

From the paper CIS 5371 Cryptography, Home Assignment 4

My question is how is the tag $$(m,t)$$ a valid forgery. This is my understanding: If I used numbers so $$m=101, IV=110, m\oplus IV=011$$, but the forgery says that I can use m, so that $$m=101, IV=101, m\oplus IV=000$$, which is obviously not the case. Could someone explain?

In other words, given a tag $(IV,t)$ for a message $m$, you can construct a tag $(m,t)$ for the message $IV$. So your understanding is wrong. It is not $m\oplus m$ in the forgery, it is $IV\oplus m$ which is the same as $m\oplus IV$.
Let $$m_1 = 0^n, IV_1 = 011$$ then, \begin{align}&F_k(m_1 \oplus IV_1)\\ =& F_k(0^n \oplus 011)\\ =& F_k(011).\end{align} Now, we can construct a different message $$m_2 = 010$$ and a valid tag for it in the following way: choose $$IV_2 = 001$$ and output \begin{align}&\langle m_2, IV_2, t_2\rangle\\ =&\langle010, 001,F_k(010 \oplus 001)\rangle\\ = &\langle010, 001,F_k(011)\rangle.\end{align} It's clear that for $$m_1 \ne m_2$$ we have produced a valid tag for $$m_2$$. We didn't need to know $$F_k$$.