Abstract
We present a refined chosen-prefix collision construction for MD5 that allowed creation of a rogue Certification Authority (CA) certificate, based on a collision with a regular end-user website certificate provided by a commercial CA. Compared to the previous construction from Eurocrypt 2007, this paper describes a more flexible family of differential paths and a new variable birthdaying search space. Combined with a time-memory trade-off, these improvements lead to just three pairs of near-collision blocks to generate the collision, enabling construction of RSA moduli that are sufficiently short to be accepted by current CAs. The entire construction is fast enough to allow for adequate prediction of certificate serial number and validity period: it can be made to require about 249 MD5 compression function calls. Finally, we improve the complexity of identical-prefix collisions for MD5 to about 216 MD5 compression function calls and use it to derive a practical single-block chosen-prefix collision construction of which an example is given.
Chapter PDF
Similar content being viewed by others
References
den Boer, B., Bosselaers, A.: Collisions for the compression function of MD5. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 293–304. Springer, Heidelberg (1994)
Diffie, W.: Personal communication (January 2009)
Dobbertin, H.: Cryptanalysis of MD5 Compress (May 1996), http://www-cse.ucsd.edu/~bsy/dobbertin.ps
Halevi, S., Krawczyk, H.: Strengthening Digital Signatures via Randomized Hashing. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 41–59. Springer, Heidelberg (2006), http://tools.ietf.org/html/draft-irtf-cfrg-rhash-01
Klima, V.: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, Cryptology ePrint Archive, Report 2005/102
Klima, V.: Tunnels in Hash Functions: MD5 Collisions Within a Minute, Cryptology ePrint Archive, Report 2006/105
McDonald, C., Hawkes, P., Pieprzyk, J.: SHA-1 collisions now 252. In: Eurocrypt 2009 Rump session
Mendel, F., Rechberger, C., Rijmen, V.: Update on SHA-1. In: Crypto 2007 Rump session
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12(1), 1–28 (1999)
Rechberger, C.: Unpublished result (2006)
Stevens, M.: Fast Collision Attack on MD5, Cryptology ePrint Archive, Report 2006/104
Stevens, M.: On collisions for MD5, Master’s thesis, TU Eindhoven (June 2007), http://www.win.tue.nl/hashclash/
Stevens, M., Lenstra, A., de Weger, B.: Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 1–22. Springer, Heidelberg (2007)
Stevens, M., Lenstra, A., de Weger, B.: Predicting the winner of the 2008 US presidential elections using a Sony PlayStation 3 (2007), http://www.win.tue.nl/hashclash/Nostradamus/
Stevens, M., Lenstra, A., de Weger, B.: Chosen-Prefix Collisions for MD5 and Applications (in preparation)
Wang, X., Lai, X., Feng, D., Yu, H.: Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD. In: Crypto 2004 Rump Session (2004)
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)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Wang, X., Yao, A., Yao, F.: New Collision Search for SHA-1. In: Crypto 2005 Rump session
Xie, T., Liu, F., Feng, D.: Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5?, Cryptology ePrint Archive, Report 2008/391
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
Stevens, M. et al. (2009). Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)