Exploiting md5 and other hashing functions collisions for fun and profit

The crytographic hash function MD5 has been broken. In March 2005, Xiaoyun Wang and Hongbo Yu of Shandong University in China published an article in which they describe an algorithm that can find two different sequences of 128 bytes with the same MD5 hash.

More links can also be found on Wikipedia's MD5 page.

SHA-0 has also been broken and The security of SHA-1 has been somewhat compromised by cryptography researchers. Chinese cryptographers showed that SHA-1 is not collision-free. That is, they developed an algorithm for finding collisions faster than brute force. There was also an attack reported in RIPEMD.

Practical applications of md5 collisions:

• Magnus Daum and Stefan Lucks have created two PostScript files with identical MD5 hash, of which one is a letter of recommendation, and the other is a security clearance.
• Eduardo Diaz has described a scheme by which two programs could be packed into two archives with identical MD5 hash. A special "extractor" program turn one archive into a "good" program and the other into an "evil" one.
• Here's a pair of valid X.509 certificates that have identical signatures. The hash function used is MD5.
• Here's a paper demonstrating a technique for finding MD5 collisions quickly: eight hours on 1.6 GHz computer.
• Hashclash - Vulnerability of software integrity and code signing applications to chosen-prefix collisions for MD5
• The Status of MD5 after a recent attack (1996 whitepaper)
  

The following is an improvement of Diaz's example, which does not need a special extractor. Here are two pairs of executable programs (one pair runs on Windows, one pair on Linux).

• Windows version:
  • hello.exe. MD5 Sum: cdc47d670159eef60916ca03a9d4a007
  • erase.exe. MD5 Sum: cdc47d670159eef60916ca03a9d4a007
• Linux version (i386):
  • hello. MD5 Sum: da5c61e1edc0f18337e46418e48c1290
  • erase. MD5 Sum: da5c61e1edc0f18337e46418e48c1290

What does this mean? You should use at least 2 hashing algorithms (RIPEMD-160, Tiger, WHIRLPOOL, SHA-256, SHA-512), as the chances of finding the same collisions in more than 1 hashing algorithm are practically 0.