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 '16 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 '16 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$ – Yehuda Lindell Mar 3 '16 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 '16 at 18:10
  • 1
    $\begingroup$ @mikeazo It's question 4.14 in the 2nd edition :-) $\endgroup$ – Yehuda Lindell Mar 3 '16 at 19:13

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, privacy policy and cookie policy

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