Paper 2006/290

On Authentication with HMAC and Non-Random Properties

Christian Rechberger and Vincent Rijmen


MAC algorithms can provide cryptographically secure authentication services. One of the most popular algorithms in commercial applications is HMAC based on the hash functions MD5 or SHA-1. In the light of new collision search methods for members of the MD4 family including SHA-1, the security of HMAC based on these hash functions is reconsidered. We present a new method to recover both the inner- and the outer key used in HMAC when instantiated with a concrete hash function by observing text/MAC pairs. In addition to collisions, also other non-random properties of the hash function are used in this new attack. Among the examples of the proposed method, the first theoretical full key recovery attack on NMAC-MD5 is presented. Other examples are distinguishing, forgery and partial or full key recovery attacks on NMAC/HMAC-SHA-1 with a reduced number of steps (up to 61 out of 80). This information about the new, reduced security margin serves as an input to the selection of algorithms for authentication purposes.

Note: Supersedes the earlier draft entitled "Note on Distinguishing, Forgery, and Second Preimage Attacks on HMAC-SHA-1 and a Method to Reduce the Key Entropy of NMAC".

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. A shortened version appears in the proceedings of FC 2007.
Contact author(s)
Christian Rechberger @ iaik tugraz at
2007-04-20: last of 2 revisions
2006-08-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Rechberger and Vincent Rijmen},
      title = {On Authentication with HMAC and Non-Random Properties},
      howpublished = {Cryptology ePrint Archive, Paper 2006/290},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.