2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mandragore Mar 6 '16 at 11:08
  • $\begingroup$ 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. $\endgroup$ – Lemon Mar 6 '16 at 11:40
  • $\begingroup$ 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. $\endgroup$ – mandragore Mar 6 '16 at 11:41
  • $\begingroup$ @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. $\endgroup$ – Yehuda Lindell Mar 6 '16 at 11:44
  • $\begingroup$ $⟨x,y⟩$ is supposed to be a tuple? $\endgroup$ – CodesInChaos Mar 6 '16 at 11:46
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cool! This is a very nice answer. $\endgroup$ – Yehuda Lindell Mar 6 '16 at 11:53
  • $\begingroup$ 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$ $\endgroup$ – mandragore Mar 6 '16 at 12:04
  • $\begingroup$ @mandragore Fixed. $\endgroup$ – CodesInChaos Mar 6 '16 at 13:21
  • $\begingroup$ 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? $\endgroup$ – Lemon Mar 6 '16 at 13:32
  • $\begingroup$ @Lemon I explained it the other way round (querying $m^\prime$ and forging $m$), but that works as well. $\endgroup$ – CodesInChaos Mar 6 '16 at 13:37
1
$\begingroup$

Consider $m_1 = 0^n || 0^n$, then: $$Mac_k(0^n || 0^n) = <F_k(0^n), F_k(0^n \oplus1^n)> \\ = <F_k(0^n), F_k(1^n)>$$

Now consider $m_2 = 0^n || 1^n$, then: $$Mac_k(0^n || 1^n) = <F_k(0^n), F_k(0^n \oplus 0^n)> \\ = <F_k(0^n), F_k(0^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.

$\endgroup$

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.