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

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

Please log in for posting a message. Only registered users may post in this forum.