2008 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2008. Please put the report number in the subject.
2008/391: Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5 ?
Posted by: jiri.vabek (IP Logged)
Date: 29 September 2008 16:42

Hello,

we have some comments on the paper:

- the complexities are computed incorrectly - on the p. 14, the factor 47/64 should be placed in this way: (2^{29})x(47/64), the same mistake on p. 15. It changes the complexity values dramatically - you have 29 conditions with prob. 1/2, so you have to make about (2^{29})x(number of steps)

- the collision search with aproximatelly same speed (within few second) was already implemented for original Wang path - see Mark Stevens master thesis on his webpage.

- also the description of automated differential path construction algorithm was published in Mark Stevens master thesis or even in his paper from Eurocrypt 2007, which is in the references

- previous two point gives also insight to the problematics of the conditions on IV for the second block

- possibility of other 3-bit input differences were already published in "Jun Yajima, Takeshi Shimoyama, Yu Sasaki, Yusuke Naito, Noboru Kunihiro, Kazuo Ohta - How to construct a differential path of MD5 for collision search, SCIS 2006, 2006."

- we suggest to use the notation of BSDR, then it wouldn'n be necessary to prove the facts from section 2

- also the collision search algorithm with divide and conquer technique is basically the same algorithm using tunneling (e.g. steps 9 and 10 are exactly the tunnels T(Q_4,m_4) and T(Q_9,m_9) - in Stevens notation)

- you can further improve the step 11 in algorithm for the first block using "early stop" technique.

- we have constructed 2-block collision with one of the 3-bit input differences (m_2,m_9,m_12), the paper was recently accepted to Indocrypt 2008

Jiri Vabek and Daniel Joscak

Jiri Vabek
Department of Algebra
Charles University in Prague
Czech Republic