5
$\begingroup$

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?

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

I won't give the answer to homework questions, but I will give a hint.

Suppose you learn the tags for $m_1 || m_2$ and $m_3 || m_4$; what other messages could you deduce the tags for?

|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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))$ ? $\endgroup$ – user3794796 May 4 '16 at 15:12
  • $\begingroup$ @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$ $\endgroup$ – poncho May 4 '16 at 15:15
  • $\begingroup$ 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 $\endgroup$ – user3794796 May 4 '16 at 15:15
  • $\begingroup$ @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. $\endgroup$ – poncho May 4 '16 at 15:18
  • $\begingroup$ Don't worry, it's not a homework, I'm studying by myself because I started to like crypto. $\endgroup$ – user3794796 May 4 '16 at 15:22

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.