MD5CRK

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

For this project, the probability of success after ${\displaystyle K}$ MD5 computations can be approximated by: ${\displaystyle 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: ${\displaystyle {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 ${\displaystyle {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.

• List of distributed computing projects
• Brute force attack