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.
Category / Keywords: secret-key cryptography / Message Authentication Codes, Birthday Attacks, Provable Security Date: received 10 Mar 2006, last revised 24 Feb 2009 Contact author: Martin Cochran at colorado edu Available formats: PDF | BibTeX Citation Note: Updated to full version of FSE 2009 proceedings. Version: 20090224:083331 (All versions of this report) Discussion forum: Show discussion | Start new discussion