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?

Improve this question
$\endgroup$
10
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 11:44
  • $\begingroup$ $⟨x,y⟩$ is supposed to be a tuple? $\endgroup$
    – CodesInChaos
    Mar 6, 2016 at 11:46

2 Answers 2

Reset to default
6
$\begingroup$

We want to forge the tag for $m = m_1 || 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Cool! This is a very nice answer. $\endgroup$
    – Yehuda Lindell
    Mar 6, 2016 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, 2016 at 12:04
  • $\begingroup$ @mandragore Fixed. $\endgroup$
    – CodesInChaos
    Mar 6, 2016 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, 2016 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, 2016 at 13:37
2
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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