Abstract
In this paper, we present the first cryptographic preimage attack on the full MD5 hash function. This attack, with a complexity of 2116.9, generates a pseudo-preimage of MD5 and, with a complexity of 2123.4, generates a preimage of MD5. The memory complexity of the attack is 245 ×11 words. Our attack is based on splice-and-cut and local-collision techniques that have been applied to step-reduced MD5 and other hash functions. We first generalize and improve these techniques so that they can be more efficiently applied to many hash functions whose message expansions are a permutation of message-word order in each round. We then apply these techniques to MD5 and optimize the attack by considering the details of MD5 structure.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-01001-9_35
Chapter PDF
Similar content being viewed by others
References
Aoki, K., Sasaki, Y.: Preimage attacks on one-block MD4, 63-step MD5 and more. In: Workshop Records of SAC 2008, Sackville, Canada, pp. 82–98 (2008)
Aumasson, J.-P., Meier, W., Mendel, F.: Preimage attacks on 3-pass HAVAL and step-reduced MD5. In: Workshop Records of SAC 2008, Sackville, Canada, pp. 99–114 (2008) (ePrint version is avaliable at IACR Cryptology ePrint Archive: Report 2008/183), http://eprint.iacr.org/2008/183.pdf
De Cannière, C., Rechberger, C.: Preimages for reduced SHA-0 and SHA-1. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 179–202. Springer, Heidelberg (2008) (slides on preliminary results were appeared at ESC 2008 seminar), http://wiki.uni.lu/esc/
De, D., Kumarasubramanian, A., Venkatesan, R.: Inversion attacks on secure hash functions using SAT solvers. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 377–382. Springer, Heidelberg (2007)
den Boer, B., Bosselaers, A.: Collisions for the compression function of MD-5. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 293–304. Springer, Heidelberg (1994)
Dobbertin, H.: The status of MD5 after a recent attack. CryptoBytes The technical newsletter of RSA Laboratories, a division of RSA Data Security, Inc., 2(2) (Summer, 1996)
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)
Klima, V.: Tunnels in hash functions: MD5 collisions within a minute. In: IACR Cryptology ePrint Archive: Report 2006/105 (2006), http://eprint.iacr.org/2006/105.pdf
Leurent, G.: MD4 is not one-way. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 412–428. Springer, Heidelberg (2008)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptography. CRC Press, Boca Raton (1997)
Rivest, R.L.: Request for Comments 1321: The MD5 Message Digest Algorithm. The Internet Engineering Task Force (1992), http://www.ietf.org/rfc/rfc1321.txt
Sasaki, Y., Aoki, K.: A preimage attack for 52-steps HAS-160. In: Preproceedings of Information Security and Cryptology ICISC 2008 (2008)
Sasaki, Y., Aoki, K.: Preimage attacks on step-reduced MD5. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 282–296. Springer, Heidelberg (2008)
Sasaki, Y., Aoki, K.: Preimage attacks on 3, 4, and 5-pass HAVAL. In: Pieprzyk, J.P. (ed.) Advances in Cryptology - ASIACRYPT 2008. LNCS, vol. 5350, pp. 253–271. Springer, Heidelberg (2008)
U.S. Department of Commerce, National Institute of Standards and Technology. Federal Register, vol. 72(212) Friday, November 2, 2007/Notices, (2007) http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sasaki, Y., Aoki, K. (2009). Finding Preimages in Full MD5 Faster Than Exhaustive Search. In: Joux, A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01001-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-01001-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01000-2
Online ISBN: 978-3-642-01001-9
eBook Packages: Computer ScienceComputer Science (R0)