md5crk

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 in August 2004 after a collision for MD5 was discovered using analytical methods. A technique called Pollard's rho algorithm (a cycle detection algorithm) was used to try and 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 max 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.

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 (PDF format).

<< Previous

Word Browser

Next >>

beta minus particle
calcaneus
krems
violawww
rafe mair
ornament
arena theater
grand theft auto: san andreas
nicholas parsons
pathfinder tendency
james ivory (mathematician)

mikhail fradkov
turbo code
curse of the ninth
reva
robert seppings
sterling lyon
wonderfalls
james rennell
alexander mcdonnell
songs in a minor
soviet submarine k 159

john 'babbacombe' lee
april 2004
pierre prvost
zooropa
euphuism
agumon
pierre st. amant
the legend of zelda: oracle of ages
the red headed league
symphony no. 9
bernhard horwitz

sts 41 d
university of new haven
carmen covito
sts 51 a
sts 51 c
george atwood
gene ziegler
sts 51 d
marmaduke wyvill
the nature conservancy
sts 51 b

Md5crk

Complexity

See also

References