Riemann–Hurwitz formula: Difference between revisions
en>Giftlite m →Statement: +. |
|||
Line 1: | Line 1: | ||
In [[cryptography]], '''MD5CRK''' was a [[distributed computing|distributed]] effort (similar to [[distributed.net]]) launched by Jean-Luc Cooke and his company, [http://www.certainkey.com/ CertainKey Cryptosystems], to demonstrate that the [[MD5]] [[message digest]] [[algorithm]] is insecure by finding a [[Hash collision|collision]] — 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[http://eprint.iacr.org/2004/199.pdf]. [http://www.certainkey.com/ CertainKey] awarded a 10,000 [[Canadian Dollar]] [http://www.certainkey.com/news/?13 prize to Wang, Feng, Lai and Yu] for their discovery. | |||
[[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 [http://www.tcf.vt.edu/ Virginia Tech's System X] with a max 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 distributed computing projects]] | |||
* [[Brute force attack]] | |||
==References== | |||
* [[Paul C. van Oorschot]], Michael J. Wiener: Parallel Collision Search with Application to Hash Functions and Discrete Logarithms. ACM Conference on Computer and Communications Security 1994: pp210–218 [http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf Online version]. | |||
[[Category:Cryptographic attacks]] | |||
[[Category:Distributed computing projects]] |
Revision as of 16:39, 16 January 2014
In cryptography, MD5CRK was a distributed 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 — 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[1]. CertainKey awarded a 10,000 Canadian Dollar prize to Wang, Feng, Lai and Yu for their discovery.
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 where is the number of bits in the digest output. It is in fact , where is the number of function outputs collected.
For this project, the probability of success after MD5 computations can be approximated by: .
The expected number of computations required to produce a collision in the 128-bit MD5 message digest function is thus:
To give some perspective to this, using Virginia Tech's System X with a max performance of 12.25 Teraflops, it would take approximately 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
- Paul C. van Oorschot, Michael J. Wiener: Parallel Collision Search with Application to Hash Functions and Discrete Logarithms. ACM Conference on Computer and Communications Security 1994: pp210–218 Online version.