# Prove that the following MAC is insecure

I am trying to prove that the following MAC is insecure, but I don't know how to exploit the properties of the pseudorandom function $F$ involved:

Gen generates a uniform $k \in \{0, 1\}^n$.

To authenticate a message $m_1 || m_2$ with $|m_1| = |m_2| = n$, compute the tag $F_k(m_1)||F_k(F_k(m_2))$.

Any help?

• What is Gen? It is not clear in your question. – ddddavidee May 4 '16 at 14:39
• I think Gen is a function used to sample the key $k$ used in the $F$. – user3794796 May 4 '16 at 14:54
• following poncho's hint you do not have to use any property of the pseudorandom function... – Hilder Vitor Lima Pereira May 4 '16 at 15:00

Suppose you learn the tags for $m_1 || m_2$ and $m_3 || m_4$; what other messages could you deduce the tags for?
• Do you mean if I am eavesdropping a conversation and I take $m_1||m_2$, $F_k(m_1)||F_k(F_k(m_2))$, $m_3||m_4$, and $F_k(m_3)||F_K(F_k(m_4))$ ? – user3794796 May 4 '16 at 15:12
• @user3794796: yes; for any secure MAC, with that information, you would not be able to guess (except with trivial probability) the MAC of any message other than the two messages $m_1||m_2$ and $m_3||m_4$ – poncho May 4 '16 at 15:15
• Ah, ok, so I could send a message $m_1||m_4$ using the tag $F_k(m_1)||F_k(F_k(m_4))$ ... Thanks – user3794796 May 4 '16 at 15:15
• @user3794796: yes, that shows that this is not a secure MAC. Now, it might not be the answer the professor was hoping for; he may have wanted something like "given the MAC of $m_1, m_1$, I can compute the MAC of $F_k(m_1), m_1$", but if so, it's his fault if he picked a question with multiple correct answers. – poncho May 4 '16 at 15:18