Abstract
In this paper, we present new generic attacks against HMAC and other similar MACs when instantiated with an n-bit output hash function maintaining a ℓ-bit internal state. Firstly, we describe two types of selective forgery attacks (a forgery for which the adversary commits on the forged message beforehand). The first type is a tight attack which requires O(2ℓ/2) computations, while the second one requires O(22ℓ/3) computations, but offers much more freedom degrees in the choice of the committed message. Secondly, we propose an improved universal forgery attack which significantly reduces the complexity of the best known attack from O(25ℓ/6) to O(23ℓ/4). Finally, we describe the very first time-memory tradeoff for key recovery attack on HMAC. With O(2ℓ) precomputation, the internal key K out is firstly recovered with O(22ℓ/3) computations by exploiting the Hellman’s time-memory tradeoff, and then the other internal key K in is recovered with O(23ℓ/4) computations by a novel approach. This tends to indicate an inefficiency in using long keys for HMAC.
Chapter PDF
Similar content being viewed by others
References
Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Dean, R.D.: Formal Aspects of Mobile Code Security. Ph.D Dissertation, Princeton University (January 1999)
Dinur, I., Leurent, G.: Improved Generic Attacks Against Hash-Based MACs and HAIFA. In: Garay, J., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 149–168. Springer, Heidelberg (2014)
Dodis, Y., Ristenpart, T., Steinberger, J., Tessaro, S.: To Hash or Not to Hash Again (In)Differentiability Results for H2 and HMAC. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 348–366. Springer, Heidelberg (2012)
Flajolet, P., Odlyzko, A.M.: Random Mapping Statistics. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 329–354. Springer, Heidelberg (1990)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)
Guo, J., Sasaki, Y., Wang, L., Wang, M., Wen, L.: Equivalent Key Recovery Attacks against HMAC and NMAC with Whirlpool Reduced to 7 Rounds. In: Cid, C., Rechberger, C. (eds.) Fast Software Encryption. LNCS. Springer (to appear, 2014)
Guo, J., Sasaki, Y., Wang, L., Wu, S.: Cryptanalysis of HMAC/NMAC-Whirlpool. In: [18], pp. 21–40
Hellman, M.E.: A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory 26(4), 401–406 (1980)
Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less Than 2n Work. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005)
Krawczyk, H., Bellare, M., Canetti, R.: HMAC: Keyed-Hashing for Message Authentication. Internet Engineering Task Force, IETF (1997), http://www.rfc-editor.org/rfc/rfc2104.txt
Leurent, G., Peyrin, T., Wang, L.: New Generic Attacks against Hash-Based MACs. In: [18], pp. 1–20
Mutafchiev, L.R.: The limit distribution of the number of nodes in low strata of a random mapping. Statistics & Probability Letters 7(3), 247–251 (1988)
Naito, Y., Sasaki, Y., Wang, L., Yasuda, K.: Generic State-Recovery and Forgery Attacks on ChopMD-MAC and on NMAC/HMAC. In: Sakiyama, K., Terada, M. (eds.) IWSEC 2013. LNCS, vol. 8231, pp. 83–98. Springer, Heidelberg (2013)
Peyrin, T., Sasaki, Y., Wang, L.: Generic Related-Key Attacks for HMAC. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 580–597. Springer, Heidelberg (2012)
Peyrin, T., Wang, L.: Generic Universal Forgery Attack on Iterative Hash-Based MACs. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 147–164. Springer, Heidelberg (2014)
Preneel, B., van Oorschot, P.C.: On the Security of Two MAC Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 19–32. Springer, Heidelberg (1996)
Sako, K., Sarkar, P. (eds.): ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 2013–2019. Springer, Heidelberg (2013)
SBI Net Systems: MonoCrypt home page, http://capg.sbins.co.jp/products/monocrypt/index.html .
U.S. Department of Commerce, National Institute of Standards and Technology: Secure Hash Standard (SHS) (Federal Information Processing Standards Publication 180-3) (2008), http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf
U.S. Department of Commerce, National Institute of Standards and Technology: Recommendation for Applications Using Approved Hash Algorithms (Federal Information Processing Standards Publication 800-107) (2012), http://csrc.nist.gov/publications/nistpubs/800-107-rev1/sp800-107-rev1.pdf
Yasuda, K.: “Sandwich” Is Indeed Secure: How to Authenticate a Message with Just One Hashing. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 355–369. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Guo, J., Peyrin, T., Sasaki, Y., Wang, L. (2014). Updates on Generic Attacks against HMAC and NMAC. In: Garay, J.A., Gennaro, R. (eds) Advances in Cryptology – CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44371-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-662-44371-2_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44370-5
Online ISBN: 978-3-662-44371-2
eBook Packages: Computer ScienceComputer Science (R0)