International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: MAC Reforgeability

John Black
Martin Cochran
Search ePrint
Search Google
Abstract: Message Authentication Codes (MACs) are central algorithms deployed in virtually every security protocol in common usage. In these protocols, the integrity and authenticity of messages rely entirely on the security of the MAC; we examine cases in which this security is lost. In this paper, we examine the notion of “reforgeability” for MACs. We first give a definition for this new notion, then examine some of the most widely-used and well-known MACs under our definition. We show that for each of these MACs there exists an attack that allows efficient forgeries after the first one is obtained, and we show that simply making these schemes stateful is usually insufficient. For those schemes where adding state is effective, we go one step further to examine how counter misuse affects the security of the MAC, finding, in many cases, simply repeating a single counter value yields complete insecurity. These issues motivated the design of a new scheme, WMAC, which has a number of desirable properties. It is as efficient as the fastest MACs, resists counter misuse, and has tags which may be truncated to the desired length without affecting security (currently, the fastest MACs do not have this property), making it resistant to reforging attacks and arguably the best MAC for constrained environments.
  title={MAC Reforgeability},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Message Authentication Codes, Birthday Attacks, Provable Security},
  note={ 14299 received 10 Mar 2006, last revised 24 Feb 2009},
  author={John Black and Martin Cochran},