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

• Did you see this? Security of CBC-MAC fixed length with zero padding – kelalaka Nov 12 '18 at 21:20
• @kelalaka No! Although, I don't see the connection? They seem to be having a padding problem, however in this exercise the message length is fixed and unpadded. – cisnjxqu Nov 12 '18 at 21:39
• I know. There are many questions tagged CBC-MAC, around 90. – kelalaka Nov 12 '18 at 21:42
• @ambiso Why is it necessarily unpadded? If $n$ is different from a multiple of the block size then you'll have to pad, right? I don't see it mentioned that no padding is to be used (unless you didn't fully state the question). – Maarten Bodewes Nov 12 '18 at 21:44
• hint: You know the $IV$, and $m_1$, what can you do? – kelalaka Nov 12 '18 at 22:44

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 :=& F_k(0^n)\\ t_2 :=& 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 :=& F_k(m^*_1) = F_k(t_1) = t_2\\ t^*_2 :=& 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 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\ t_2 :=& 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.

• I ended up with something similar, but way more complicated, thanks for your reply!! :-) – cisnjxqu Nov 14 '18 at 15:49

In general, CBC-MAC with fixed length is secure. However, in this example $$F$$ is "a secure (deterministic) MAC" which could mean that we can conduct the message authentication experiment MAC-forge on it and use that outcome for CBC-MAC.

• Iff $F$ is a secure MAC then there is no such adversary that succeeds in the MAC-forge game (with non-negligible probability). Am I misunderstanding something? Could you elaborate on your response? Thanks in advance! – cisnjxqu Nov 14 '18 at 1:31