Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
2  
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 at 13:53

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.