Welcome to the resource topic for 2009/223
Title:
How To Find Weak Input Differences For MD5 Collision Attacks
Authors: Tao Xie, 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.
ePrint: https://eprint.iacr.org/2009/223
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .