How To Find Weak Input Differences For MD5 Collision Attacks.
Tao Xie, Dengguo Feng · 2009
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 use to satisfy 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 better than 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 new differential collision attack with only 1-MSB input difference is developed with a time complexity of 2 20.96 MD5 compressions, two weak input differences are able to find a collision within 2 10 MD5 compressions. In particular, a 2-bit weak input difference is found to be able to construct a practical 1-block collision attack on MD5. This paper will provide 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.