I'm working on some cryptography problems, found this and I'm not sure how to solve it:

Modify CBC-MAC so that all blocks $t_1,\dots,t_l$ are output rather than just $t_l$ and prove it is not secure.

  • 1
    $\begingroup$ Hint: show how to obtain a valid MAC for a 1-block(-after padding) message by submitting a 2-blocks(-after padding) message. $\endgroup$
    – fgrieu
    Mar 3, 2016 at 15:53
  • $\begingroup$ @fgrieu Ok, so basically if MAC(m1||0^n)=t then also should MAC(m1||m2)=t .Therefore , we could XOR m2 out by using a mask to obtain the same tag -but how do i apply this to the t's which are essentially outputs(and not inputs like the m's-they are only fed as inputs in the next block)? $\endgroup$
    – EOS
    Mar 3, 2016 at 16:53
  • 1
    $\begingroup$ The really good question though is to show that it isn't secure even as a FIXED-LENGTH MAC (so the forgery has to be the same length as the queries). $\endgroup$ Mar 3, 2016 at 17:40
  • $\begingroup$ @YehudaLindell maybe a question to add to the next version of Introduction to Modern Cryptography :) or maybe it already is. I need to get a copy of your book. $\endgroup$
    – mikeazo
    Mar 3, 2016 at 18:10
  • 2
    $\begingroup$ @mikeazo It's question 4.14 in the 2nd edition :-) $\endgroup$ Mar 3, 2016 at 19:13

2 Answers 2


Consider the following chosen-plaintext attack on the modified CBC-MAC function:

Send $m_1$, $m_2$, $m_3$, receive $t_1$, $t_2$, $t_3$.

Send $m_1$, $m'_2$, $m'_3$, receive $t'_1$, $t'_2$, $t'_3$.

Send $t'_2 \oplus m''_3$, $m''_2$, $m''_3$, receive $E_k(t'_2 \oplus m''_3)$, $t''_2$, $t''_3$.

Then you know the following (message, tag) pair will verify:

Send $m_1$, $m'_2$, $m''_3$: the tag will be the concatenation of values you have previously queried for: $t_1$, $t'_2$, $E_k(t'_2 \oplus m''_3)$. Therefore you can generate a valid (message, tag) pair that has not yet been sent through the modified CBC-MAC algorithm. This can be generalized for any number of blocks.


Recall what we mean when we talk about security of a MAC.

While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-plaintext attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages (which were not used to query the oracle) without performing infeasible amounts of computation.

So, you are given oracle access to something that you give it a message $m$ and it gives you the MAC. Your goal is to compute a valid MAC of some $m'\neq m$. How would you do that in this modified MAC?

Think about this, let's say I sent the message I EOS, give all my worldly belongings to mikeazo. Just kidding. to the oracle. Given the MAC of that message, can I generate a MAC for the message I EOS, give all my worldly belongings to mikeazo.?

In practice you will have to deal with block boundaries and padding, but both of those things are entirely deterministic and known to the attacker. In other words, they aren't much of a hurdle.


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.