Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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?
