HashClash
The purpose is to extend both theoretical and experimental results on collision generation for the MD5 and SHA-1 hash functions, based on the ideas of Xiaoyun Wang and her co-workers.
Marc got a nomination for the Joop Bautz Award in the area of information security.
On July 2, 2008 Marc received the "TU/e Afstudeerprijs 2008", i.e. the TU/e Best Master Thesis Award for the best final project in one of the TU/e master's programs completed in 2007.
Marc's thesis "On Collisions for MD5", June 2007 (pdf, 652 KB) is available for download.
Update: The new version 1.0.0.5 is not only extended with V. Klima's tunnels, but also with additional differential paths to speed up collision finding.
This means that for any targeted pair of distinct messages m1 and m2 we can effectively construct appendages b1 and b2 such that MD5(m1||b1) equals MD5(m2||b2). Said differently, we can cause an MD5 collision for any pair of distinct IHVs.
See the chosen-prefix collision website.
For Marc's MSc thesis he succeeded in producing one example of a chosen-prefix collision. This was done with the application below in mind. But see below for more spectacular results found after Marc's thesis was finished.
We have operated a grid, using BOINC. The HashClash Boinc Server now is offline (actually it ceased to exist physically) as it is not needed anymore.
The HashClash part done after Marc's graduation was mainly done on a (cluster of) Sony PlayStation 3(s).
Added January 1, 2009: the newest application is Creating a rogue CA certificate.
Published as Cryptology ePrint Archive, Report 2006/104.
Marc Stevens, Arjen Lenstra and Benne de Weger, "Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities", October 2006 (pdf, 340 KB).
Published as Cryptology ePrint Archive, Report 2006/360.
Marc Stevens, Arjen Lenstra and Benne de Weger, "Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities", February 2007 (pdf, 271 KB).
This paper was presented at the EuroCrypt 2007 conference in Barcelona on May 21, 2007, and was selected by the program committee as one of the three "notable papers".
The paper is published in the proceedings: Moni Naor (ed.), Advances in Cryptology - EUROCRYPT 2007, Springer Lecture Notes in Computer Science Vol. 4515, 2007, pp. 1-22.
Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger, "Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate", August 2009. This paper describes the new techniques used for our Rogue CA construction. It has appeared in the Proceedings of Crypto 2009, and won us the best paper award.
Marc Stevens, Arjen Lenstra and Benne de Weger, "Chosen-prefix Collisions for MD5 and Applications". This is the "full paper" including all the material of the other papers and descriptions of all the applications we have developed. It has been submitted to the Journal of Cryptology.
Marc's MSc thesis "On Collisions for MD5", June 2007 (pdf, 652 KB) (which has won him the award for the best TU/e Master Thesis for 2007).
Available (older) software here: a fast "MD5 Collision Generator", version 1.0.0.5-1.
Source Code (zipped, 27 KB)
Win32 Executable (zipped, 111 KB)
No guarantee whatsoever is given on how it may function or malfunction.
Support cannot be expected.
This software is meant for scientific and educational purposes only.
It is forbidden to use it for other than scientific or educational purposes.
In particular, commercial and malicious use is not allowed.
Further distribution of this software, by whatever means, is not allowed without our consent.
This includes publication of source code or executables in printed form, on websites, newsgroups, CD-ROM's, etc.
Changing the (source) code without our consent is not allowed.
In all versions of the source code this disclaimer, the copyright notice and the version number should be present.
Colliding X.509 certificates for different identities
Predicting the 2008 US presidential elections using a Sony PlayStation 3
Colliding executables - a software integrity and code signing vulnerability
Creating a rogue CA certificate
Single Block Chosen Prefix Collision
Old Colliding X.509 Certificates for identical identities
Marc Stevens' homepage
Arjen Lenstra's homepage
Benne de Weger's homepage
___
/ _ \
| / | |
| \_|/
\____
Marc Stevens
Arjen Lenstra
Benne de Weger