Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5 ?
Tao Xie FanBao Liu DengGuo Feng Abstract: So far, two different 2-block collision differentials, both with 3-bit input differences for MD5, have been found by Wang etc in 2005 and Xie etc in 2008 respectively, and those differentials have been improved later on to generate a collision respectively within around one minute and half an hour on a desktop PC. Are there more collision differentials for MD5? Can a more efficient algorithm be developed to find MD5 collisions? In this paper, we list the whole set of 1-bit to 3-bit input difference patterns that are possibly qualified to construct a feasible collision differential, and from which a new collision differential with only 1-MSB input difference is then analyzed in detail, finally the performances are compared with the prior two 3-bit collision attacks according to seven criteria proposed in this paper. In our approach, a two-block message is still needed to produce a collision, the first block being only one MSB different while the
