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:

basic CBC-MAC

The book states that basic CBC-MAC is secure for fixed length messages when instantiated with a PRF.

  • 2
    $\begingroup$ Did you see this? Security of CBC-MAC fixed length with zero padding $\endgroup$
    – kelalaka
    Nov 12 '18 at 21:20
  • $\begingroup$ @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. $\endgroup$
    – cisnjxqu
    Nov 12 '18 at 21:39
  • $\begingroup$ I know. There are many questions tagged CBC-MAC, around 90. $\endgroup$
    – kelalaka
    Nov 12 '18 at 21:42
  • 1
    $\begingroup$ @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). $\endgroup$
    – Maarten Bodewes
    Nov 12 '18 at 21:44
  • 1
    $\begingroup$ hint: You know the $IV$, and $m_1$, what can you do? $\endgroup$
    – 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 its 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 its output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible, and 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 preserving, 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.

  • $\begingroup$ I ended up with something similar, but way more complicated, thanks for your reply!! :-) $\endgroup$
    – 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.

  • 1
    $\begingroup$ 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! $\endgroup$
    – cisnjxqu
    Nov 14 '18 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.