1. Prove that the following modification of $\operatorname{CBC-MAC}$ does not yield a secure fixed-length $\operatorname{MAC}$:

    Modify $\operatorname{CBC-MAC}$ so that a random $IV$ is used each time a tag is computed (and the $IV$ is output along with $t_l$). I.e., $t_0 \leftarrow \{0, 1\}^n$ is chosen uniformly at random rather than being fixed to $0^n$, and the tag is $t_0, t_l$.

    Answer. The scheme is not secure. In particular, let $m$ be a one-block message and let $(IV, t)$ be its $\operatorname{MAC}$-tag received from the oracle. Then, the tag $(m, t)$ is a valid $\operatorname{MAC}$ for the message $IV$. (More generally, for any $m'$ the tag $(IV \oplus m', t)$ is a valid $\operatorname{MAC}$ for the message $m \oplus m'$. This means that it is possible to generate a forgery for any desired single-block message.)

From the paper CIS 5371 Cryptography, Home Assignment 4

My question is how is the tag $(m,t)$ a valid forgery. This is my understanding: my understanding If I used numbers so $m=101, IV=110, m\oplus IV=011$, but the forgery says that I can use m, so that $m=101, IV=101, m\oplus IV=000$, which is obviously not the case. Could someone explain?


2 Answers 2


Then, the tag (m,t) is a valid MAC for the message IV.

In other words, given a tag $(IV,t)$ for a message $m$, you can construct a tag $(m,t)$ for the message $IV$. So your understanding is wrong. It is not $m\oplus m$ in the forgery, it is $IV\oplus m$ which is the same as $m\oplus IV$.


Let $m_1 = 0^n, IV_1 = 011$ then, \begin{align}&F_k(m_1 \oplus IV_1)\\ =& F_k(0^n \oplus 011)\\ =& F_k(011).\end{align} Now, we can construct a different message $m_2 = 010$ and a valid tag for it in the following way: choose $IV_2 = 001$ and output \begin{align}&\langle m_2, IV_2, t_2\rangle\\ =&\langle010, 001,F_k(010 \oplus 001)\rangle\\ = &\langle010, 001,F_k(011)\rangle.\end{align} It's clear that for $m_1 \ne m_2$ we have produced a valid tag for $m_2$. We didn't need to know $F_k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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