1
$\begingroup$

In the following problem:

Prove that the following modifications of basic CBC-MAC do not yield a secure MAC (even for fixed-length messages):

(b) A random initial block is used each time a message is authenticated. That is, choose uniform $t_0 \in \{0, 1\}^n$, run basic CBC-MAC over the “message” $t_0, m_1, m_2, \cdots, m_l$ and output the tag $\left<t_0, t_l\right>$. Verification is done the natural way.

I can prove it for variable-length messages, but for fixed-length messages, I had the following argument that it is indeed secure:

By way of contradiction let $D$ be an attacker that breaks the security of this MAC scheme of messages of length $l$. We construct another attacker $A$ that breaks the security of CBC-MAC for messages of length $l + 1$ using $D$ as a subroutine as follows:

  1. For every message $m_i$ that $D$ sends to the modified MAC oracle for tagging, $A$ take it instead and sends to the CBC-MAC oracle the message $t_0||m_i$ for some uniformly random $t_0$.
  2. $A$ receives the tag for each message $t_0||m_i$ and sends it back to $D$ (for $D$'s perspective, it is the same as the modified MAC oracle).
  3. After a polynomial number of queries, $D$ sends the message $m$ and the tag $\left<t_0, t\right>$ for verification where the probability that Vrfy$(m, \left<t_0, t\right>)$ returns true is not negligible.
  4. $A$ then sends the message $t_0||m$ and the tag $t$, and it easily follows that $\text{Vrfy}(t_0||m, t) = \text{Vrfy}(m, \left<t_0, t\right>)$

this suggests that CBC MAC is not secure for fixed-length messages, which raises a contradiction. So, our assumption must be wrong and this modified CBC-MAC is secure.

Now, is there anything wrong about this argument?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ @fgrieu exactly, it proves the opposite (that it is secure given that the normal CBC-MAC is secure). But the question is asking for the opposite. Just to be clear, there are 2 MAC schemes in the problem, the modified CBC-MAC and the normal CBC-MAC, and it is known and can be proved that the normal CBC-MAC is secure for fixed-length messages $\endgroup$ Commented Jan 11 at 13:45
  • 1
    $\begingroup$ @fgrieu why is my counterargument wrong? $\endgroup$ Commented Jan 11 at 18:09
  • $\begingroup$ I had misread the question , and there was some nonsense in earlier (delected) comments, sorry. $\endgroup$ Commented Jan 12 at 10:41

2 Answers 2

Reset to default
0
$\begingroup$

After more careful reading, I now side with the question's proof that the modified MAC is secure for fixed-length message, for a definition of secure such that CBC-MAC is secure for fixed-length message. I conclude the problem statement is incorrect when it adds even for fixed-length messages.

Perhaps we want to detail step 2: $A$ is made such that $D$ receives $\left<t_0,t\right>$ where $t_0$ is as generated by $A$ in step 1, and $t$ is as generated by the CBC-MAC oracle following the query in step 1.

And we should additionally argue that if $m$ generated by $D$ in step 3 is distinct from any $m$ that $D$ generated in an earlier step 1 (which depending on security definition is either a requirement for $D$ to be valid, or a necessary condition for $D$ to win the game), then $t_0\mathbin\|m$ generated by $A$ in step 4 will be distinct from any $t_0\mathbin\|m$ that $A$ generated in an earlier step 1 (thus making $A$ valid, or insuring a necessary condition for $A$ to win the game). Combined with $\mathsf{Vrfy}(t_0\mathbin\|m,t)=\mathsf{Vrfy}(m,\left<t_0,t\right>)$, this completes the proof that $A$ wins (at least) as often as $D$ does.

Improve this answer
$\endgroup$
0
$\begingroup$

See the errata for the textbook where this (homework) question came from.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.