# Why is $Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$ not a secure MAC?

I am preparing for an exam and trying to solve the following question I found on the internet:

Let $F_k$ be a pseudorandom function. Show that the following MAC for messages of length $2n$ is insecure. The shared key is a random key $k \in \{0, 1\}^n$.

$\operatorname{Mac}_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$

where $m_1, m_2$ are binary strings of length $n$ and $\overline{m_2}$ is $m_2$with all its bits inverted. What is the minimum number of queries that the adversary has to make to the MAC-oracle to forge a MAC?

To solve both questions I have tried to construct two messages for which the attacker requests tags and then combine the messages and corresponding tags in a way that gives a valid message and tag. Regrettably, this didn't work out since the second part of the tag combines both parts of the original message. Am I on the wrong track with my approach?

• what does minimum means though? this is randomised as far as i can tell so if an adversary is really really lucky he could forge a mac with one query. – mandragore Mar 6 '16 at 11:08
• If you can provide a way to forge a tag with requesting only a single tag that should be a legitimate answer. But how would you do that? I am looking for a concrete solution how to forge a valid message and tag. – Lemon Mar 6 '16 at 11:40
• As i said this is randomised. You can not say the exact numbers of queries needed, not even the minum numbers because even if you try random strings as a mac you may well forge a mac on your first try. – mandragore Mar 6 '16 at 11:41
• @mandragore In what way is this randomized? In addition, being able to forge a mac on your first try with low probability doesn't matter. – Yehuda Lindell Mar 6 '16 at 11:44
• $⟨x,y⟩$ is supposed to be a tuple? – CodesInChaos Mar 6 '16 at 11:46

## 2 Answers

We want to forge the tag for $m = m_1 \oplus m_2$. The tag we need to produce is:

$$\operatorname{Mac}_k(m_1||m_2)=⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$$

We'll query the oracle with the message $m_1^\prime || m_2^\prime$, which needs to be different from $m_1||m_2$ to count as forgery. Consider $m_1^\prime || m_2^\prime = (m_1 \oplus \overline{m_2}) || m_2$, which is different from $m_1||m_2$ iff $\overline{m_2} \neq 0$.

This message has the tag:

\begin{align} \operatorname{Mac_k(m_1^\prime||m_2^\prime)} &=⟨F_k(m_1^\prime),F_k(m_1^\prime \oplus \overline{m_2^\prime})⟩ \\ &=⟨F_k(m_1 \oplus \overline{m_2}),F_k((m_1 \oplus \overline{m_2})\oplus \overline{m_2})⟩ \\ &=⟨F_k(m_1 \oplus \overline{m_2}),F_k(m_1)⟩ \end{align}

swapping the two outputs produces the tag for $m=m_1||m_2$.

Thus we can produce forgeries using only a single query to the MAC oracle.

• Cool! This is a very nice answer. – Yehuda Lindell Mar 6 '16 at 11:53
• The tag for $m\prime$ is $<F_k(m_1 \oplus \overline{m_2}), F_k( m_1 \oplus \overline{m_2} \oplus \overline{m_1})> =<F_k(m_1 \oplus \overline{m_2}), F_k(m_2)>$. And then you can get a tag for $m = m_2 || m_1$ – mandragore Mar 6 '16 at 12:04
• @mandragore Fixed. – CodesInChaos Mar 6 '16 at 13:21
• To make sure that I understood it correctly: I request a tag for message $m = m_1 || m_2$ which gives me $t = ⟨t_1, t_2⟩$. My forged message and tag are $m' = (m_1 \oplus \overline{m_2})||m_2$, $t = ⟨t_2, t_1⟩$. Correct? – Lemon Mar 6 '16 at 13:32
• @Lemon I explained it the other way round (querying $m^\prime$ and forging $m$), but that works as well. – CodesInChaos Mar 6 '16 at 13:37

Consider $$m_1 = 0^n || 0^n$$, then: $$Mac_k(0^n || 0^n) = \\ = $$

Now consider $$m_2 = 0^n || 1^n$$, then: $$Mac_k(0^n || 1^n) = \\ = $$

so you would not even have to query for $$m_2$$ as you already know the output would be the first part of $$m_1$$ twice. This is a break of security.