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?
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)}
  &amp;=⟨F_k(m_1^\prime),F_k(m_1^\prime \oplus \overline{m_2^\prime})⟩ \\
  &amp;=⟨F_k(m_1 \oplus \overline{m_2}),F_k((m_1 \oplus \overline{m_2})\oplus \overline{m_2})⟩ \\
  &amp;=⟨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.