Paper 2008/391

Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5 ?

Tao Xie, FanBao Liu, and DengGuo Feng

Abstract

So far, two different 2-block collision differentials, both with 3-bit input differences for MD5, have been found by Wang etc in 2005 and Xie etc in 2008 respectively, and those differentials have been improved later on to generate a collision respectively within around one minute and half an hour on a desktop PC. Are there more collision differentials for MD5? Can a more efficient algorithm be developed to find MD5 collisions? In this paper, we list the whole set of 1-bit to 3-bit input difference patterns that are possibly qualified to construct a feasible collision differential, and from which a new collision differential with only 1-MSB input difference is then analyzed in detail, finally the performances are compared with the prior two 3-bit collision attacks according to seven criteria proposed in this paper. In our approach, a two-block message is still needed to produce a collision, the first block being only one MSB different while the second block remains the same. Although the differential path appears to be computationally infeasible, most of the conditions that a collision differential path must satisfy can be fulfilled by multi-step modifications, and the collision searching efficiency can be much improved further by a specific divide-and-conquer technique, which transforms a multiplicative accumulation of the computational complexities into an addition by properly grouping of the conditional bits. In particular, a tunneling-like technique is applied to enhance the attack algorithm by introducing some additional conditions. As a result, the fastest attack algorithm is obtained with an averaged computational complexity of 2^20.96 MD5 compressions, which implies that it is able to search a collision within a second on a common PC for arbitrary random initial values. With a reasonable probability a collision can be found within milliseconds, allowing for instancing an attack during the execution of a practical protocol. The collision searching algorithm, however, is very complex, but the algorithm has been implemented which is available from the website http://www.is.iscas.ac.cn/gnomon, and we suggest you download the implementation program from the website for a personal experience if you are interested in it.

Note: Much thanks for the comments given by Jiri Vabek and Daniel Joscak, reminding me of the computational cost estimiation error. The computational cost estimation error has been corrected and a strict estimation method of computational cost is given as Appendix B in the revised version of this paper. Very recently, a much more efficient MD5 collision searching algorithm using the 1-MSB input difference has been released as version V3.1 on the website http://www.is.iscas.ac.cn/gnomon. Welcomes and much thanks for any comments from the cryptology community, which will contribute much to the consummation of the MD5 collision attacks. In this paper, firstly, a whole list of 1-bit to 3-bit eligible input differences is presented, and the supernatural appearance of collision differential selection is thus revealed. Secondly, a new 1-MSB input difference pattern is developed to be the currently fastest collision attack algorithm for MD5, with an averaged computational complexity of 2^20.96 MD5 compressions, implying that a common desktop PC can easily produce MD5 collisions. Thirdly, a divide-and-conquer technique specific for hash collision attacks is proposed with a concrete application of it. Finally, some technical details related to the derivation of the basic conditions and the extra conditions are presented. This paper will help the cryptology community to further grasp the recent techniques on hash cryptanalysis.