×

New key-recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5. (English) Zbl 1149.94331

Smart, Nigel (ed.), Advances in cryptology – EUROCRYPT 2008. 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78966-6/pbk). Lecture Notes in Computer Science 4965, 237-253 (2008).
Summary: At Crypto ’07, Fouque, Leurent and Nguyen presented full key-recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5, by extending the partial key-recovery attacks of Contini and Yin from Asiacrypt ’06. Such attacks are based on collision attacks on the underlying hash function, and the most expensive stage is the recovery of the so-called outer key. In this paper, we show that the outer key can be recovered with near-collisions instead of collisions: near-collisions can be easier to find and can disclose more information. This improves the complexity of the FLN attack on HMAC/NMAC-MD4: the number of MAC queries decreases from \(2^{88}\) to \(2^{72}\), and the number of MD4 computations decreases from \(2^{95}\) to \(2^{77}\). We also improved the total complexity of the related-key attack on NMAC-MD5. Moreover, our attack on NMAC-MD5 can partially recover the outer key without the knowledge of the inner key, which might be of independent interest.
For the entire collection see [Zbl 1133.94008].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellare, M.; Canetti, R.; Krawczyk, H.; Koblitz, N., Keying hash functions for message authentication, Advances in Cryptology - CRYPTO ’96, 1-15 (1996), Heidelberg: Springer, Heidelberg · Zbl 1329.94051
[2] Bellare, M.; Dwork, C., New Proofs for NMAC and HMAC: Security without Collision-Resistance, Advances in Cryptology - CRYPTO 2006, 602-619 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.68437 · doi:10.1007/11818175_36
[3] den Boer, B.; Bosselaers, A.; Helleseth, T., Collisions for the Compression Function of MD5, Advances in Cryptology - EUROCRYPT ’93, 293-304 (1994), Heidelberg: Springer, Heidelberg · Zbl 0951.94508
[4] Contini, S.; Yin, Y. L.; Lai, X.; Chen, K., Forgery and partial key-recovery attacks on HMAC and NMAC using hash collisions, Advances in Cryptology - ASIACRYPT 2006, 37-53 (2006), Heidelberg: Springer, Heidelberg · Zbl 1172.94571 · doi:10.1007/11935230_3
[5] Fouque, P.-A.; Leurent, G.; Nguyen, P. Q.; Menezes, A., Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5, Advances in Cryptology - CRYPTO 2007, 13-30 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94046 · doi:10.1007/978-3-540-74143-5_2
[6] Kim, J.; Biryukov, A.; Preneel, B.; Hong, S.; De Prisco, R.; Yung, M., On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1, Security and Cryptography for Networks, 242-256 (2006), Heidelberg: Springer, Heidelberg · Zbl 1152.94428 · doi:10.1007/11832072_17
[7] Menezes, A.; van Oorschot, P.; Vanstone, S., Handbook of Applied Cryptography (1997), Boca Raton: CRC Press, Boca Raton · Zbl 0868.94001
[8] Rechberger, C., Rijmen, V.: Note on Distinguishing, Forgery and Second Preimage Attacks on HMAC-SHA-1 and a Method to Reduce the Key Entropy of NMAC. Cryptology ePrint Archive, Report, 2006/290 (2006)
[9] Rechberger, C.; Rijmen, V.; Dietrich, S.; Dhamija, R., On Authentication with HMAC and Non-Random Properties, Financial Cryptography 2007, 39-57 (2007), Heidelberg: Springer, Heidelberg
[10] Rivest, R. L.; Menezes, A.; Vanstone, S. A., The MD4 Message-Digest Algorithm, Advances in Cryptology - CRYPTO ’90, 303-311 (1991), Heidelberg: Springer, Heidelberg · Zbl 0800.68418
[11] Rivest, R.L.: The MD5 Message Digest Algorithm. Request for Comments (RFC 1321), Network Working Group (1992)
[12] Wang, X.; Lai, X.; Feng, D.; Chen, H.; Yu, X.; Cramer, R. J.F., Cryptanalysis of the Hash Functions MD4 and RIPEMD, Advances in Cryptology - EUROCRYPT 2005, 1-18 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94358
[13] Wang, X.; Yu, H.; Cramer, R. J.F., How to Break MD5 and Other Hash Functions, Advances in Cryptology - EUROCRYPT 2005, 19-35 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94359
[14] Wang, X.; Yu, H.; Yin, Y. L.; Shoup, V., Efficient Collision Search Attacks on SHA-0, Advances in Cryptology - CRYPTO 2005, 1-16 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94455
[15] Wang, X.; Yin, Y. L.; Yu, H.; Shoup, V., Finding Collisions in the Full SHA-1, Advances in Cryptology - CRYPTO 2005, 17-36 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94454
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.