View source for MD5CRK

In [[cryptography]], '''MD5CRK''' was a [[volunteer computing]] effort (similar to [[distributed.net]]) launched by Jean-Luc Cooke and his company, CertainKey Cryptosystems, to demonstrate that the [[MD5]] [[message digest]] [[algorithm]] is insecure by finding a [[Hash collision|collision]]{{snd}} two messages that produce the same MD5 hash. The project went live on March 1, 2004. The project ended on August 24, 2004, after researchers independently demonstrated a technique for generating collisions in MD5 using analytical methods by [[Xiaoyun Wang]], Feng, [[Xuejia Lai]], and Yu.<ref name=collisions2004>{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xuejia Lai |author4=Hongbo Yu |date=17 August 2004 |title=Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2004/199 }}</ref> CertainKey awarded a 10,000 [[Canadian Dollar]] prize to Wang, Feng, Lai and Yu for their discovery.<ref>{{cite press release |title=Popular, Yet Obsolete, Banking Algorithm Broken |date=17 February 2005 |work=CertainKey News |url=http://www.certainkey.com/news/?13 |url-status=usurped |archiveurl=https://web.archive.org/web/20110513090927/http://www.certainkey.com/news/?13 |archivedate=13 May 2011 }}</ref>

[[Image:MD5CRK-Pollard.svg|right|thumbnail|350px|Pollard's Rho collision search for a single path]]
A technique called [[Floyd's cycle-finding algorithm]] was used to try to find a collision for MD5. The algorithm can be described by analogy with a [[random walk]]. Using the principle that any function with a finite number of possible outputs placed in a feedback loop will cycle, one can use a relatively small amount of memory to store outputs with particular structures and use them as "markers" to better detect when a marker has been "passed" before.  These markers are called ''distinguished points'', the point where two inputs produce the same output is called a ''collision point''.  MD5CRK considered any point whose first 32 [[bit]]s were zeroes to be a distinguished point.

==Complexity==
The expected time to find a collision is not equal to <math>2^{N}</math> where <math>N</math> is the number of bits in the digest output.  It is in fact <math>2^N! \over {(2^N - K)! \times {2^N}^K}</math>, where <math>K</math> is the number of function outputs collected.

For this project, the probability of success after <math>K</math> MD5 computations can be approximated by: <math>1 \over { 1 - e^{K \times (1-K) \over 2^{N+1} } }</math>.

The expected number of computations required to produce a collision in the 128-bit MD5 message digest function is thus: <math>{1.17741 \times 2^{N/2}} = {1.17741 \times 2^{64}}</math>

To give some perspective to this, using Virginia Tech's [[System X (supercomputer)|System X]] with a maximum performance of 12.25 Teraflops, it would take approximately <math>{2.17 \times 10^{19} / 12.25 \times 10^{12} \approx 1,770,000} </math> seconds or about 3 weeks.  Or for commodity processors at 2 gigaflops it would take 6,000 machines approximately the same amount of time.

==See also==
* [[List of volunteer computing projects]]
* [[Brute force attack]]

==References==
{{Reflist}}

===Further reading===
* {{cite conference |author=Paul C. van Oorschot |author-link=Paul C. van Oorschot  |author2=Michael J. Wiener|title=Parallel Collision Search with Application to Hash Functions and Discrete Logarithms |conference=ACM Conference on Computer and Communications Security 1994 |pages=210&ndash;218 |url=http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf }}

[[Category:Cryptographic attacks]]
[[Category:Volunteer computing projects]]