<?xml version="1.0" encoding="iso-8859-1" ?>
<rss version="2.0">
  <channel>
    <title>2008 Reports</title>
    <link>http://eprint.iacr.org/forum/list.php?8</link>
    <description><![CDATA[Discussion forum for Cryptology ePrint Archive reports posted in 2008.
Please put the report number in the subject.

]]></description>
    <language>EN</language>
    <pubDate>Mon, 29 Sep 2008 10:42:07 -0600</pubDate>
    <lastBuildDate>Mon, 29 Sep 2008 10:42:07 -0600</lastBuildDate>
    <category>2008 Reports</category>
    <generator>Phorum 5.1.22</generator>
    <ttl>600</ttl>
    <item>
      <title>2008/391:  Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5 ?</title>
      <link>http://eprint.iacr.org/forum/read.php?8,60,60#msg-60</link>
      <author>jiri.vabek</author>
      <description><![CDATA[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 &quot;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.&quot;

- 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 &quot;early stop&quot; 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]]></description>
      <category>2008 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?8,60,60#msg-60</guid>
      <pubDate>Mon, 29 Sep 2008 10:42:07 -0600</pubDate>
    </item>
  </channel>
</rss>
