BOINC Projects

HashClash

Revision as of 13:03, 5 July 2026 by Al Piskun (talk | contribs) (update infobox stats)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)



HashClash is a completed BOINC volunteer computing project that searched for collisions in the MD5 and, later, the SHA-1 cryptographic hash functions.[1] The project was based at the Department of Mathematics and Computer Science of the Eindhoven University of Technology (TU/e) and was initiated by cryptography researcher Marc Stevens as part of his master's degree thesis.[1] Rather than a scientific outreach project aimed at the public, HashClash was a working research tool: volunteers donated idle CPU cycles through the standard BOINC client so that Stevens and his collaborators could perform the enormous number of hash computations needed to construct practical hash collisions, most famously the 2008 forgery of a rogue certificate authority certificate.[2]

HashClash
The MD5 message digest process. HashClash exploited structural weaknesses in this compression function to construct collisions.
Project
StatusCompleted
CategoryCryptography
ComputeCPU
RequiresBoost C++ Libraries
Development
DeveloperMarc Stevens
AuthorMarc Stevens
SponsorEindhoven University of Technology
MaintainerNone (project discontinued; source archive maintained by Marc Stevens)
Initial releaseNovember 24, 2005  (21 years ago)
CompletedJune 2007 (original MD5 phase)[1]
Discontinued2009 (last BOINC-distributed computation)[2]
Repositoryhttps://github.com/cr-marcstevens/hashclash
Software
Written inC, C++
Operating systemWindows, Linux
BOINC statistics
Stats as ofOctober 12, 2007  (2019 years ago)
Total users2,963
Active hosts284
Total hosts9,334
Metadata
Websitehttps://marc-stevens.nl/p/hashclash/
LicenseMixed (MIT-packaged; some components under GPL-3.0-or-later)[3]

Although the project's core computing phase ended in 2007, when Stevens defended his thesis, the HashClash software framework has continued to be developed and used for cryptanalytic research into SHA-1, culminating a decade later in the first published collision for the full SHA-1 algorithm.[4]

Background

A cryptographic hash function is expected to be collision resistant: it should be computationally infeasible to find two distinct messages M1≠M2 such that

MD5⁡(M1)=MD5⁡(M2)

In 2004, Xiaoyun Wang and Hongbo Yu announced the first practical collisions in MD5, a 128-bit hash function designed by Ronald Rivest in 1991.[5] Their attack relied on carefully constructed differential paths through MD5's four rounds of compression, and it renewed interest in whether such attacks could be extended, sped up, and turned into practical threats against real-world systems that still relied on MD5, such as X.509 digital certificates.[6]

History

Origins and MSc thesis (2006 to 2007)

 
The Eindhoven University of Technology, where Marc Stevens developed HashClash as part of his master's thesis.

Marc Stevens began work on improving MD5 collision-finding techniques as a master's student at TU Eindhoven, building on Wang and Yu's differential path methodology and on suggestions and support from Wang herself.[7] By refining the sufficient-condition analysis of MD5's compression function and applying Vlastimil Klima's "tunnel" technique, Stevens brought the time needed to compute a single MD5 collision down to a few seconds on ordinary desktop hardware.[8]

To scale this work up to the much larger search needed for chosen-prefix collisions, in which two colliding messages are allowed to begin with two completely different, attacker-chosen prefixes, Stevens launched HashClash as a BOINC project in early 2007.[9] Several hundred BOINC volunteers, combined with a high-performance cluster at TU/e, contributed cycles to the project, at times involving as many as 1,200 machines.[7] The project's initial computing phase concluded in June 2007 when Stevens defended his thesis, for which he was awarded top honors.[9] That same year, Stevens, Arjen Lenstra, and Benne de Weger published "Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities" at Eurocrypt 2007, demonstrating two X.509 certificates with different, attacker-chosen identities that nonetheless shared an identical MD5-based signature.[2]

Chosen-prefix collisions expressed formally

A chosen-prefix collision can be written as

MD5⁡(P1∥C1∥S)=MD5⁡(P2∥C2∥S)

where P1 and P2 are two arbitrary prefixes fixed in advance (for example, the distinguishing fields of two different certificates), C1 and C2 are specially crafted "near-collision" blocks computed by the HashClash software, and S is an identical suffix appended to both messages.[6] Because MD5 processes messages in 512-bit blocks using the Merkle-Damgard construction, once the internal chaining state has been forced back into agreement, any common suffix can be appended without affecting the collision.[5]

The rogue certificate authority attack (2008 to 2009)

In mid-2008, security researchers Alexander Sotirov, Jacob Appelbaum, and David Molnar approached Stevens with a plan to use chosen-prefix collisions to attack a real, commercially trusted certificate authority that was still signing certificates with MD5.[2] Stevens improved his collision-construction methods further, and, running the computation on a cluster of PlayStation 3 consoles belonging to Arjen Lenstra, the team produced the needed collision in October 2008.[2] The result was a forged intermediate certificate, purportedly issued by a trusted root certificate authority, that browsers would accept as a legitimate certificate authority capable of signing certificates for any website.[6]

The attack, titled "MD5 Considered Harmful Today: Creating a Rogue CA Certificate," was presented by Sotirov, Stevens, and Appelbaum at the 25th Chaos Communication Congress in Berlin on 30 December 2008.[10] The full academic write-up, "Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate," was published the following year at CRYPTO 2009 and won that conference's Best Paper award.[11]

SHA-1 work and later development (2009 to present)

Following the rogue CA attack, Stevens extended the HashClash framework to support differential path construction and near-collision search for SHA-1, a hash function with a longer, more complex message schedule than MD5.[9] The project's source code, originally hosted in a Subversion repository, was migrated to Google Code in the years that followed and then to a custom Subversion server in 2015 after Google announced it would be shutting down Google Code.[12] In October 2017, the repository was migrated to GitHub, switching its build system to Autotools; support for CUDA and Cell processor acceleration was temporarily dropped from the main branch during that migration.[12]

Techniques developed for HashClash's SHA-1 support fed directly into "SHAttered," the first published collision for the full SHA-1 algorithm, announced by Stevens together with researchers from CWI Amsterdam and Google in February 2017.[4] That result won the CRYPTO 2017 Best Paper award and a 2017 Pwnie Award for Best Cryptographic Attack.[11]

Software

The HashClash source tree is organized around a shared library of routines for MD5 and SHA-1 differential path analysis, alongside a collection of command-line tools, including md5fastcoll for generating identical-prefix collisions, md5birthdaysearch for the birthday-style search used in chosen-prefix attacks, and a family of diffpath*_sha1 tools for constructing and connecting SHA-1 differential paths.[13] The software is written in C++ and depends on the Boost C++ Libraries; releases have historically included optional CUDA acceleration for GPU-assisted birthday search.[13] The project's shell script cpc.sh automates a full chosen-prefix collision attack given any two input files.[12]

The estimated computational cost of these attacks has fallen substantially over the life of the project: early collision searches required on the order of 239 MD5 compression function evaluations, while a subsequent optimized single-block collision attack published by Stevens in 2012 required approximately 250 compressions.[9][14]

Legacy

HashClash is generally credited with demonstrating, in a fully practical setting rather than a theoretical one, that MD5 was unsuitable for any application requiring collision resistance, including certificate signing.[6] Following public disclosure of the rogue CA attack, major commercial certificate authorities accelerated their transition away from MD5-based signatures.[10] The project's differential-path methodology and software also formed the technical foundation for later, unrelated cryptanalytic milestones against SHA-1, extending its influence well beyond its original 2007 completion date.[4]

Publications

The following papers are listed on the official BOINC publications page as scientific results arising from HashClash's BOINC-based computing.[15]

  1. Stevens, Marc, Arjen Lenstra and Benne de Weger. "Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities". (2006). PDF
  2. Stevens, Marc, Arjen Lenstra and Benne de Weger. "Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities". (2007). DOI: 10.1007/978-3-540-72540-4_1. Link
  3. Stevens, M. "On Collisions for MD5". International Journal of Human-Computer Studies (2007). PDF
  4. Sotirov, Alexander, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger. "MD5 Considered Harmful Today: Creating a Rogue CA Certificate". 25th Chaos Communication Congress (2008). PDF
  5. Stevens, Marc, 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". (2009). DOI: 10.1007/978-3-642-03356-8_4. Link
  6. Stevens, Marc, Arjen K. Lenstra and Benne De Weger. "Chosen-prefix collisions for MD5 and applications". International Journal of Applied Cryptography (2012). DOI: 10.1504/IJACT.2012.048084. PDF
  7. Stevens, Marc. "Single-block collision attack on MD5". Cryptology ePrint Archive (2012). Link
  8. Stevens, M. M. J. "Attacks on hash functions and applications". (2012). Link
  9. Stevens, Marc. "Fast Collision Attack on MD5". (2013). Link
  10. Karpman, Pierre, Thomas Peyrin and Marc Stevens. "Practical Free-Start Collision Attacks on 76-step SHA-1". (2015). DOI: 10.1007/978-3-662-47989-6_30. Link
  11. Stevens, Marc, Pierre Karpman and Thomas Peyrin. "Freestart Collision for Full SHA-1". (2016). DOI: 10.1007/978-3-662-49890-3_18. Link
  12. Stevens, Marc, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov. "The First Collision for Full SHA-1". Advances in Cryptology - CRYPTO 2017 (2017). Link

See also

References

  1. ↑ 1.0 1.1 1.2 HashClash. Wikipedia. Retrieved 4 July 2026.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 de Weger, Benne.Cryptology and Information Security. TU Eindhoven. Retrieved 4 July 2026.
  3. ↑ Package request: hashclash. GitHub. Retrieved 4 July 2026.
  4. ↑ 4.0 4.1 4.2 Marc Stevens (cryptology). Wikipedia. Retrieved 4 July 2026.
  5. ↑ 5.0 5.1 MD5. Wikipedia. Retrieved 4 July 2026.
  6. ↑ 6.0 6.1 6.2 6.3 X.509. Wikipedia. Retrieved 4 July 2026.
  7. ↑ 7.0 7.1 Stevens, Marc.Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities. Retrieved 4 July 2026.
  8. ↑ Stevens, M..(2007).On Collisions for MD5. International Journal of Human-Computer Studies.
  9. ↑ 9.0 9.1 9.2 9.3 HashClash. Grokipedia. Retrieved 4 July 2026.
  10. ↑ 10.0 10.1 (30 December 2008})."MD5 Considered Harmful Today: Creating a Rogue CA Certificate".In 25th Chaos Communication Congress.Berlin, Germany.link.
  11. ↑ 11.0 11.1 Marc Stevens. Centrum Wiskunde and Informatica. Retrieved 4 July 2026.
  12. ↑ 12.0 12.1 12.2 Project HashClash. Marc Stevens. Retrieved 4 July 2026.
  13. ↑ 13.0 13.1 cr-marcstevens/hashclash. GitHub. Retrieved 4 July 2026.
  14. ↑ Fast Collision Attack on MD5. Cryptology ePrint Archive. Retrieved 4 July 2026.
  15. ↑ Publications by BOINC Projects. BOINC. Retrieved 4 July 2026.
Retrieved from "https://boincsynergy.ca/wiki/index.php?title=HashClash&oldid=1697"