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 ﬁnd 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.