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.

  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Apr 26 '14 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.