On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1

HMAC is a widely used message authentication code and a pseudorandom function generator based on cryptographic hash functions such as MD5 and SHA-1. It has been standardized by ANSI, IETF, ISO and NIST. HMAC is proved to be secure as long as the compression function of the underlying hash function is a pseudorandom function. In this paper the authors devise two new distinguishers of the structure of HMAC, called differential and rectangle distinguishers, and use them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. They show how to distinguish HMAC with reduced or full versions of these cryptographic hash functions from a random function or from HMAC with a random function.