MAC Reforgeability
Venue
Fast Software Encryption, Springer (2009), pp. 345-362
Publication Year
2009
Authors
John Black, Martin Cochran
BibTeX
Abstract
Message Authentication Codes (MACs) are core 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, and motivate its utility in the context of {power,
bandwidth, CPU}-constrained computing environments. We first give a definition for
this new notion, then examine some of the most widely-used and well-known MACs
under our definition in a variety of adversarial settings, finding in nearly all
cases a failure to meet the new notion. We examine simple counter-measures to
increase resistance to reforgeability, using state and truncating the tag length,
but find that both are not simultaneously applicable to modern MACs. In response,
we give a tight security reduction for a new MAC, WMAC, which we argue is the "best
fit" for resource-limited devices.
