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?

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

1 Answer 1

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?

$\endgroup$
5
  • $\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$ May 4, 2016 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, 2016 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$ May 4, 2016 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, 2016 at 15:18
  • $\begingroup$ Don't worry, it's not a homework, I'm studying by myself because I started to like crypto. $\endgroup$ May 4, 2016 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.