Consider the following fixed length MAC for messages of length $\ell(n)=2n-2$ using a pseudorandom function $F$:

On input of a mesage $m_0||m_1$ ($|m_0| = |m_1| = n-1$) and a key $k \in \{0,1\}^n$, algorithm Mac outputs $t=F_k(0||m_0)||F_k(1,m_1)$. Algorithm Vrfy is defined in the natural way.

Is (Gen, Mac, Vrfy) existentially unforgeable under a chosen message attack? Why?

  • $\begingroup$ Welcome to Cryptography Stack Exchange. This is not a "do my homework" site, and your question with the "prove your answer" looked quite like a homework or exam question (this is why I changed this). If you actually want to understand this, you'll get more useful answers if you describe what you already tried (and which results you got), and where you hit your limits. $\endgroup$ Mar 17 '12 at 23:10

Forgeries can be made against this algorithm; here's how:

If the attacker gets the MAC with the two messages M0||M2 and M1||M3 as follows:

MAC(M0||M2) = Fk(0||M0) || Fk(1||M2)
MAC(M1||M3) = Fk(0||M1) || Fk(1||M3)

then, the attacker knows the values of Fk(0||M1) and Fk(1||M2), and thus can deduce the MAC of the message M1||M2 as:

MAC(M1||M2) = Fk(0||M1) || Fk(1||M2)

BTW: is this a homework assignment?


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.