I'd like to know whether the following modified CBC-MAC is secure (given a fixed IV).

Modified CBC MAC

Source: an old course on Network Security

Are there some obvious attacks I can't see?

  • 8
    $\begingroup$ Hint: what happens to the tag when two blocks of plaintext are exchanged? $\endgroup$ – fgrieu Jul 22 '14 at 16:03
  • $\begingroup$ @fgrieu: why don't you convert your comment into an answer? That way, it can be upvoted and accepted. $\endgroup$ – poncho Jul 22 '14 at 17:18
  • 1
    $\begingroup$ What have you tried? What are your thoughts? What kinds of attacks have you considered? Have you tried to see if you could prove it secure? Have you looked at the special case where there are exactly 2 plaintext blocks? I don't think copy-pasting an exercise from an earlier course is a great fit for this site. We want to help clear up any confusions you might have, but as for doing an exercise problem for you -- well, maybe not so much. I don't think it benefits the world for us to be a site where people can paste exercises and have someone else produce a complete solution for them. $\endgroup$ – D.W. Jul 22 '14 at 21:27

This scheme is not worth the name MAC; it is horribly weak.

First and foremost, the tag/MAC is unchanged when two blocks of plaintext are exchanged (because of the commutativity and associativity of the $\oplus$ operation). If follows that from any message with at least two different blocks, we can make a different message for which we know the tag/MAC. This conclusively proves that this MAC is not secure, for any modern definition of security (which must include that a new message crafted by an adversary ignoring the key from other messages+MAC will pass verification with odds marginally above $2^{-n}$, where $n$ is the width of the MAC in bits).

Further, if we happen to know the tag/MAC of a message with two identical blocks, we can change these blocks to anything, and that will leave the MAC unchanged.

If the message length is allowed to vary, things get worse: the tag/MAC for the concatenation of messages is the XOR of the tag/MAC of the originals; and we can insert two identical blocks in a message leaving the tag/MAC unchanged.


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.