Paper 2009/223

How To Find Weak Input Differences For MD5 Collision Attacks

Tao Xie and Dengguo Feng

Abstract

Since the first feasible collision differential was given for MD5 in 2004 by Wang et al, a lot of work has been concentrated on how to improve it, but the researches on how to select weak input differences for MD5 collision attack are only sporadically scattered in literature. This paper focuses on a reasonable selection of weak input differences for MD5 collision attack, tries to answer some questions such as, what techniques can be applied satisfying bit conditions? which step in the second round can be the latest to apply a search on free bits without violating previously satisfied conditions? what is the optimal characterization of feasible collision differential propagation for MD5, by which we can find more weak input differences? is there any collision differentials that exceed Wang et al's by some practical criteria? In this paper, a divide-and-conquer strategy is introduced with an optimal scheme of grouping the 64 steps of operation into five stages of independent condition fulfillment, and a feasible collision differential propagation is optimally characterized as a guide to select those 1~3-bit weak input differences, with their computational costs estimated. As a result, hundreds of thousands of weak input differences have been found, quite a number of which are superior to Wang et al's, for example, a 2-bit collision differential is able to find a collision within 2^10 MD5 compressions, a 1-MSB differential collision attack on MD5 is developed with a time complexity of 2^20.96 MD5 compressions, and a practical 1-block collision attack on MD5 is found to be possible. This paper also provides a rich resource of colliding messages with different weak input differences, therefore much greatly increase the probability of finding a second MD5 pre-image for an arbitrarily given message.

Note: This revision makes public our first 1-block collision on MD5, which is considered as a hopeful but unfinihsed work suggested in the final paragraph ot the last revision. The successful construction of a MD5 collision using just a single block message implys that a new attack technique has already been developed by us, and this is impossible to achieve by current attack techniques.