Login
Login

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 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.{{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 }} CertainKey awarded a 10,000 Canadian Dollar prize to Wang, Feng, Lai and Yu for their discovery.{{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 }}

Image:MD5CRK-Pollard.svg

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 bits were zeroes to be a distinguished point.

Complexity

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

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

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

To give some perspective to this, using Virginia Tech's System X with a maximum performance of 12.25 Teraflops, it would take approximately {2.17 \times 10^{19} / 12.25 \times 10^{12} \approx 1,770,000} 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

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–218 |url=http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf }}

Category:Cryptographic attacks

Category:Volunteer computing projects