Cryptology ePrint Archive: Report 2006/290

On Authentication with HMAC and Non-Random Properties

Christian Rechberger and Vincent Rijmen

Abstract: 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.

Category / Keywords: secret-key cryptography /

Publication Info: A shortened version appears in the proceedings of FC 2007.

Date: received 24 Aug 2006, last revised 20 Apr 2007

Contact author: Christian Rechberger at iaik tugraz at

Available format(s): PDF | BibTeX Citation

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".

Version: 20070420:122701 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]