Prove that the following MAC is insecure

Question

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?

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 Vítor Lima Pereira, May 4 '16 at 15:00

poncho · Accepted Answer · 2016-05-04 14:48:12Z

3

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?

answered May 4 '16 at 14:48

poncho

98.6k3 gold badges160 silver badges258 bronze badges

$\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

add a comment |

1 Answer 1