The use of cryptographic hash functions like MD5 or SHA-1 for message authentication has become a standard approach in many
applications, particularly Internet security protocols. Though very easy to implement, these mechanisms are usually based
on ad hoc techniques that lack a sound security analysis.
We present new, simple, and practical constructions of message authentication schemes based on a cryptographic hash function.
Our schemes, NMAC and HMAC, are proven to be secure as long as the underlying hash function has some reasonable cryptographic
strengths. Moreover we show, in a quantitative way, that the schemes retain almost all the security of the underlying hash
function. The performance of our schemes is essentially that of the underlying hash function. Moreover they use the hash function
(or its compression function) as a black box, so that widely available library code or hardware can be used to implement them
in a simple way, and replaceability of the underlying hash function is easily supported.
This version of our paper has been truncated due to page limits. The full version is [3].