Why does the CBC-MAC require PRFs? I'm stuck on exercise 4.19 from Introduction to Modern Cryptography.


  Let $F$ be a keyed function that is a secure (deterministic) MAC for
  messages of length $n$. (Note that $F$ need not be a pseudorandom
  permutation.) Show that basic CBC-MAC is not necessarily a secure MAC
  (even for fixed-length messages) when instantiated with $F$.


My idea was to construct the secure MAC $F'_k = m \| F_k(m)$, which would leak information on $F_k(m_1)$.
However, that would double the size of the MAC with every step.

Is there another/better/working solution?

Why are PRFs required for the CBC-MAC domain extension?

Edit: basic CBC-MAC refers to the following construction:



The book states that basic CBC-MAC is secure for fixed length messages when instantiated with a PRF.
The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be.
But ignoring this fact for a moment, one of your observations was indeed crucial.
A MAC does in general not hide it's input message.
As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure.
However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values.
And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle.
The CBC-MAC for our query will be computed as follows:
\begin{align*}
  t_1 :=&amp; F_k(0^n)\\
  t_2 :=&amp; F_k(0^n\oplus t_1) = F_k(t_1)
\end{align*}
and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery.
We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$:
\begin{align*}
  t^*_1 :=&amp; F_k(m^*_1) = F_k(t_1) = t_2\\
  t^*_2 :=&amp; F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1
\end{align*}
And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$?
The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC.
Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$.
I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack.
For this, observe the values of $t_1,t_2$ in this instantiation.
\begin{align*}
  t_1 :=&amp; F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\
  t_2 :=&amp; F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1)
\end{align*}
I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$.
Therefore the attack sketched above works with this instantiation.