Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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. –  Paŭlo Ebermann Mar 17 '12 at 23:10

1 Answer 1

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?

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.