This archive contains implementations of collision attacks published on the MD5 and SHA-0 hash functions. This code is provided for educational purposes only, without any explicit or implied guarantee of merchantability or fitness for any purpose.
The code was written by Thomas Pornin <firstname.lastname@example.org>
, on behalf of Projet RNRT SAPHIR. Part of the code was imported from sphlib, another library from the same source. The code for attacks took inspiration from the demonstration implementations by, respectively, Vlastimil Klima for MD5, and Soren Steffen Thomsen for SHA-0. See the comments in the C source files for details.
The code was optimized so that meaningful conclusions on the intrinsic cost of such attacks could be drawn. Both of these attacks have a similar structure: in order to fulfill a given differential path, they try many input blocks which have a (relatively) high probability of success. Successive blocks are derived from each other by message modification techniques. The bottom-line is that each trial consists in the computation of a number of elementary steps in the hash function processing. The average number of computed steps can be estimated a priori (e.g. 21 steps for the MD5 attack), as well as the average number of trials needed to reach a collision. One may estimate the attack performance (number of trials per second) by measuring how many elementary steps are computed per second when using the hash function itself.
It turns out that for both attacks, about 75 to 80% of that theoretical speed is achieved. The basis for this comparison is sphlib, a library of optimized C implementations of hash functions. Measures were performed on an Intel Core2 Q6600 processor, in "amd64" mode, with GCC 4.3.2 as C compiler. Since sphlib was written with the same optimization rules and efforts, with the same compilers for the same architectures, by the same programmer, it is expected that comparative benchmarks between the attacks and sphlib are meaningful and express intrinsic properties of the algorithms.
The MD5 collision attack code is in the "md5" directory. The source files md5.c and md5coll.c must be compiled and linked together (NOT md_helper.c). For instance, on a Linux or equivalent system with gcc installed, use this:
gcc -W -Wall -O2 -fomit-frame-pointer -o mcoll md5.c md5coll.c
to produce the "mcoll" binary. The program accepts a single, optional argument which is used as seed for the internal PRNG. It will then repeatedly compute collisions, measuring the average time to produce a collision, and the corresponding number of blocks tried before reaching the collision. The attack implementation itself is in md5coll.c; it includes (in comments at the end of the file) an alternate main() function which can be used to compute multi-collisions (using Joux's method).
On my 2.4 GHz Q6600 machine, I get an average of 14.66 seconds per collision, and about 219 millions of trials (which is lower than the theoretically expected 268 millions). Attack cost is then evaluated at about 2^26.5 evaluations of the MD5 function itself.
Simlarly, the SHA-0 collision attack code is in the "sha0" directory. Use this to compile the code:
gcc -W -Wall -O2 -fomit-frame-pointer -o scoll sha0.c sha0coll.c
This program also uses a single and optional argument as PRNG seed. Contrary to the MD5 code, this program computes and prints out a single collision. It first chooses the first block of the colliding messages (this is very fast), then it proceeds with the second block, which may take some time. It regularly prints out some internal statistics. When the second block is found, it is also printed out. The two blocks constitute together the first message of the colliding pair. The second message uses the same first block, and a slightly different second block (a 26-bit difference is applied by bitwise XOR; see the main() function in sha0coll.c). The program finally computes and prints out the two SHA-0 hashes for the colliding pairs (hopefully, these hashes are identical).
On my machine, the cost is evaluated to 2^39.6 evaluations of SHA-0, which is rather huge (that is, when running it in practical conditions). This translates to an average of almost two days worth of computation per collision. It turns out that using "1" as seed (the ASCII string consisting of a unique character of value 49, which is the ASCII code for a "1") falls on a lucky case, producing a collision in about 21 minutes.
Note that both programs are single-threaded and easily fit in L1 caches. Thus, on a quad-core system, four instances can be run in parallel (e.g. with distinct seeds).
The development system was a 64-bit x86 Linux system. However, the code should be highly portable to just about any system with a conformant C compiler (unless you find an exotic system where "char" is not an 8-bit type, but this should be detected at compilation time). In particular, there should be no endianness or type width issue.