cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, MD5CRK was a

volunteer computing Volunteer computing is a type of distributed computing in which people donate their computers' unused resources to a research-oriented project, and sometimes in exchange for credit points. The fundamental idea behind it is that a modern desktop co ...

effort (similar to distributed.net) launched by Jean-Luc Cooke and his company, CertainKey Cryptosystems, to demonstrate that the MD5

message digest A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output re ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

is insecure by finding a

collision In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word ''collision'' refers to incidents in which two or more objects collide with great fo ...

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 Wang Xiaoyun (; born 1966) is a Chinese cryptographer, mathematician, and computer scientist. She is a professor in the Department of Mathematics and System Science of Shandong University and an academician of the Chinese Academy of Sciences. Ear ...

, Feng,

Xuejia Lai Xuejia Lai () is a cryptographer, currently a professor at Shanghai Jiao Tong University. His notable work includes the design of the block cipher IDEA based on the Lai-Massey scheme, the theory of Markov ciphers, and the cryptanalysis of a num ...

, and Yu. CertainKey awarded a 10,000

Canadian Dollar The Canadian dollar ( symbol: $; code: CAD; french: dollar canadien) is the currency of Canada. It is abbreviated with the dollar sign $, there is no standard disambiguating form, but the abbreviation Can$ is often suggested by notable style ...

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 In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

. 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 The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...

s were zeroes to be a distinguished point.

Complexity

The expected time to find a collision is not equal to

2^

where

N

is the number of bits in the digest output. It is in fact

2^N! \over

, 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

. 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 maximum 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.

Complexity

See also

References

Further reading