Finding MD5 Collisions - a Toy For a Notebook.
Vlastimil Klíma · IACR Cryptology ePrint Archive · 2005
In this short memo, we summarize the results achieved during a two and half months long research. Further details will be provided in a forthcoming paper. One of the major cryptographic “break-through” of the recent years was a discovery of collisions for a set of hash functions (MD4, MD5, HAVAL-128, RIPEMD) by the cryptographers in August 2004 [1]. Their authors (Wang et al.) kept the algorithm secret, however. During October 2004, the Australian team (Hawkes et al.) tried to reconstruct the methodology in their great work [3]. The most important Chinese trick was not discovered, although they succeeded in describing a differential scheme of conditions that hold for the published collisions. Nevertheless, fulfilling the conditions of this scheme has been still more computationally difficult in comparison to what the results of [1] showed. During our research, we also analyzed the available data using differential cryptanalysis. We have found a way to generate the first message block of the collision about 1000 2000 times faster than the team that corresponds to reaching the first colliding block in 2 minutes using a common notebook (PC platform). The same computation phase took the team about an hour using an IBM P690 supercomputer. On the other hand, the team was 2 80 times faster when computing the second message block of their collisions. Therefore, our and the methods probably differs in several details in both parts of the computation. Overall, our method is about 3 6 times faster. More specifically, finding the first (complete) collision took 8 hours using a notebook PC (Intel Pentium 1.6 GHz). Note that our method works for any initialization vector. It can be abused in forging signatures of software packages and digital certificates as some papers show ([4], [5], [6]). We have shown that it is possible to find MD5 collisions using an ordinary home PC. That should be a warning towards persisting usage of MD5. In the appendix, we show new examples of collisions for a standard and chosen initialization vectors. 1 This research has been done during Christmas vacation and during January and February 2005. At that time the author has been working for the company LEC, s.r.o., Prague, Czech Republic which supported the project by material and financial means.