Another look at HMAC

Neal Koblitz and Alfred Menezes
Journal of Mathematical Cryptology, 7 (2013), 225-251.

Abstract: HMAC is the most widely-deployed cryptographic-hash-function-based message authentication code. First, we describe a security issue that arises because of inconsistencies in the standards and the published literature regarding keylength. We prove a separation result between two versions of HMAC, which we denote HMACstd and HMACBel, the former being the real-world version standardized by Bellare et al. in 1997 and the latter being the version described in Bellare's proof of security in his Crypto 2006 paper. Second, we describe how HMACNIST (the FIPS version standardized by NIST), while provably secure (in the single-user setting), succumbs to a practical attack in the multi-user setting. Third, we describe a fundamental defect from a practice-oriented standpoint in Bellare's 2006 security result for HMAC, and show that because of this defect his proof gives a security guarantee that is of little value in practice. We give a new proof of NMAC security that gives a stronger result for NMAC and HMAC and we discuss why even this stronger result by itself fails to give convincing assurance of HMAC security.

Journal paper       Eprint paper

Related material:
  • The HMAC brawl, presentation by Dan Bernstein at the Fast Software Encryption (FSE) Rump Session (March 20, 2012).
  • Non-uniform cracks in the concrete, presentation by Dan Bernstein and Tanja Lange at the Eurocrypt 2012 Rump Session (April 17, 2012).
  • Another look at provable security, invited presentation by Alfred Menezes at Eurocrypt 2012 (April 18, 2012).
  • Non-uniform cracks in the concrete: the power of free precompuation, article by Dan Bernstein and Tanja Lange (June 4, 2012).
  • The exact prf-security of NMAC and HMAC, CRYPTO 2014 article by Peter Gaži, Krzysztof Pietrzak, Michal Rybár.
  • Our response to the Gaži-Pietrzak-Rybár CRYPTO 2014 paper.