Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that we want to develop a MAC scheme which is as secure as Triple-DES CBC-MAC and at the same time as efficient as Single-DES CBC-MAC. We come up with the following idea: Except the last plaintext block, we apply Single-DES CBC with key K1 and for the last one, we apply 2-key Triple-DES CBC-MAC using keys (K1, K2, K1). The result of the Triple-DES is output as the MAC.

a. Approximately how many (message, MAC) pairs would you need to observe in order to find two different messages with the same MAC value?

b. Describe how an attacker who has observed two different messages with the same MAC value can break this MAC scheme completely by recovering the keys with a time complexity about the same as that of breaking a Single DES encryption.

share|improve this question
Welcome and general comments as per your other question. Hints for this one: for any reasonable MAC scheme, to an adversary not knowing the key, the MAC values for different messages appear random, with matching odds of collision, which can be computed/approximated. Assuming that two (message, MAC) pairs have the same MAC, consider what similarities are bound to exist in the quantities involved when computing their respective MACs. – fgrieu Apr 26 '14 at 13:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.