Improved Collision Attack on Hash Function MD5

In this paper, we present a fast attack algorithm tofind two-block collision of hash function MD5. The algorithm is basedon the two-block collision differential path of MD5 that was presented byWang \it et al. in the Conference EUROCRYPT 2005. We found that the derivedconditions for the desired collision differential path were notsufficient to guarantee the path to hold and that some conditions could be modified toenlarge the collision set. By using technique of small range searchingand omitting the computing steps to check the characteristics in theattack algorithm, we can speed up the attack of MD5 efficiently. Compared withthe Advanced Message Modification technique presented by Wang \it etal., the small range searching technique can correct 4 more conditionsfor the first iteration differential and 3 more conditions for thesecond iteration differential, thus improving the probability and thecomplexity to find collisions. The whole attack on the MD5 can beaccomplished within 5 hours using a PC with Pentium4 1.70GHz CPU.