Technische Universiteit Eindhoven

The HashClash Project HashClash started as Marc Stevens' TU/e Master Degree project.
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 Stevens' MSc Thesis Marc's MSc project has been very successful. Marc defended his MSc thesis in June 2007, and passed with flying colors. His grade was 10, which is the highest possible grade, which is awarded only very rarely.
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.
Fast Collision Finding The first deliverable of HashClash is a fast collision generating algorithm for MD5. This method finds collisions without any special properties (other than those that can be expected from the Wang-type methods). A paper, source code and a Win32 executable are available, see below.
Update: The new version is not only extended with V. Klima's tunnels, but also with additional differential paths to speed up collision finding.
Chosen-prefix Collisions The second deliverable of HashClash is a method for constructing Chosen-prefix Collisions for MD5.
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.
Application As an application we have a method of constructing a pair of colliding X.509 certificates for different identities.
Distributed Computing HashClash required extensive computational efforts, that can easily be parallelized.
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.
HashClash BOINC logo
The HashClash part done after Marc's graduation was mainly done on a (cluster of) Sony PlayStation 3(s).
Other applications Since Marc finished his thesis he has done some more work, especially when visiting Arjen Lenstra at EPFL for a summer project during September and October 2007. The result is a Nostradamus attack consisting of a multi-collision of 12 PDF files, and a pair of colliding executables.

Added January 1, 2009: the newest application is Creating a rogue CA certificate.
Papers and MSc thesis Marc Stevens, "Fast Collision Attack on MD5", March 2006 (pdf, 195 KB).
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).
Software Downloads Marc Stevens now maintains a code page: Hashclash - Framework for MD5 Differential Path Construction and Chosen-Prefix Collisions.

Available (older) software here: a fast "MD5 Collision Generator", version
Source Code (zipped, 27 KB)
Win32 Executable (zipped, 111 KB)
Software Copyright © M.M.J. Stevens, 2006-2007. All rights reserved.
Software Disclaimer This software is provided as is. Use is at the user's risk.
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.
Links Chosen-prefix collision website
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
Latest Modification August 22, 2009
Vanity Counter