Welcome to the resource topic for 2005/400
Title:
Improved Collision Attack on MD5
Authors: Yu Sasaki, Yusuke Naito, Noboru Kunihiro, Kazuo Ohta
Abstract:In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al.
In this attack, conditions which are sufficient to generate collisions (called
``sufficient condition") are introduced.
This attack raises the success probability by modifing messages to satisfy these conditions.
In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is 2^{37}.
After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the
complexity is 2^{33}.
In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far.
In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that
this method work correctly is roughly 1/2. Therefore, the complexity of this attack is 2^{30}. Furthermore, we propose a more efficient
collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8.
ePrint: https://eprint.iacr.org/2005/400
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 .