MD5 Collisions

It seems that bad days came for MD5 and those who based hashes on it. It is possible to create two executable programs with different functionalities with identical MD5 hash. Therefore, it is possible to create malicious executable which has same MD5 hash as regular program. This can be done just by using public Internet information and tools.

Here is short story and list of resources that you can be interested in to try.

In March 2005, Xiaoyun Wang and Hongbo Yu of Shandong University in China published paper “How to Break MD5 and Other Hash Functions” in which they described an algorithm that can find two different sequences of 128 bytes with the same MD5 hash. That article originally was here, but it seems as it is not anymore. You can buy it from SpringerLink (here) for price of $25, or download based on subscription to it. There is free Power Point presentation here.

Abstract of paper “How to Break MD5 and Other Hash Functions” says:

MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.

In meantime, Peter Selinger from Department of Mathematics and Statistics, Dalhousie University, published the tool that you can download for free and which he used to create MD5-colliding executable files. He calls it the “evilize” library. This software is based on Patrick Stach’s implementation of Wang and Yu’s algorithm. You can find his original implementation here.

Eduardo Diaz has described a scheme by which two programs could be packed into two archives with identical MD5 hash. A special “extractor” program turns one archive into a “good” program and the other into an “evil” one.

Almost three years ago I had published blog post on MD5 Online Cracking. Also, I have written about NIST new hash competition here and here.

[Thanks to Zeljko for pointing me to this implementation of tool.]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.