2.4.8 What are the most important attacks on MACs?
There are a variety of threats to the security of a MAC (see Question 2.1.7). First and most obviously, the use of a MAC should not reveal information about the secret key being used. Second, it should not be possible for an adversary to forge the correct MAC to some message without knowing the secret key - even after seeing many legitimate message/MAC pairs. Third, it should not be possible to replace the message in a message/MAC pair with another message for which the MAC remains legitimate. There are a variety of threat models that depend on different assumptions about the data that might be collected. For example, can an adversary control the messages whose MACs are obtained, and if so, can the choice be adapted as more data is collected?
Depending on the design of the MAC there are a variety of different attacks that might apply. Perhaps the most important class of attacks is due to Preneel and van Oorschot [PV95]. These attacks involve a sophisticated application of the birthday paradox (see Question 2.4.6) to the analysis of message/MAC pairs and the attacks have been particularly useful in highlighting structural faults in the design of many MACs. Some considerable work was spent in the early to mid-90's on designing MACs based around the use of a hash function. The attacks of Preneel and van Oorschot were instrumental in removing many of these flawed designs from consideration.