MD5-Hash函数的碰撞攻击的改进
Improved Collision Attack on Hash Function MD5
-
摘要: Hash函数(也称杂凑函数或杂凑算法)就是能够把任意长度小于264比特的消息串M映射成某一固定长度的输出串h的一种函数。这个输出串h称为该消息串M的消息摘要(message digest)或指纹(fingerprint)。一个安全的杂凑函数应该至少满足以下几个条件;①对每一个给定的输入消息串,计算输出的Hash值(即消息摘要)是很容易的;②对任意给定的某一Hash值h, 找到一个输入消息串M,使得其计算输出的Hash值刚好等于h是计算上不可行的;③找到任意两个不同的输入消息串映射到同一个Hash值是计算上不可行的。Hash函数主要用于数据完整性校验和提高数字签名的有效性等。Hash函数的碰撞攻击就是指找到攻击方法可以给出两个不同的输入消息串映射到同一个Hash值的碰撞实例。关于Hash函数的碰撞攻击最近几年取得了举世注目的成果,王小云等提出的基于模减的差分分析方法有效地攻破了MD4, MD5, RIPMD,HAVAL和SHA-0等一系列Hash函数,其攻击算法复杂度都低于 次压缩函数运算,在一般的个人电脑上运算都可以找到碰撞实例。本文正是针对MD5-Hash函数的碰撞攻击做进一步分析的最新研究成果。基于王小云等在2005年欧密会上发表的关于MD5-Hash函数的碰撞差分链,本文给出了一种快速攻击MD5-Hash函数的算法。我们研究发现,在王小云等发表的关于MD5-Hash函数碰撞攻击的文章里6给出的保持MD5碰撞差分链的导出条件不是充分的即这些条件不足以保持碰撞差分链,并且一些导出条件可以放宽从而扩大碰撞集合;为了给出一个充分的条件集合,本文引进了循环移位和二进制加法进位的差分特性,通过反馈计算导出了一些附加条件,从而第一次给出了关于MD5-Hash函数的碰撞差分链的充分条件集合。在这基础上,我们总结了推导MD5-Hash函数的碰撞差分链的充分条件集合的一般方法。这一方法也适用于推导其它Hash函数的碰撞差分链的充分条件集合。基于充分条件集合并且引进小范围搜索的修正技巧,在算法中去除校验差分特征所带来的计算开销,我们有效地提高了对MD5-Hash函数的碰撞攻击的效率。我们的快速攻击算法搜索MD5-Hash函数的碰撞,其计算复杂度比文章6里给出的算法降低了至少16倍; 在Pentium4 1.70GHZ CPU 的个人电脑上实验,我们的攻击算法可以在5个小时内找到碰撞实例。Abstract: In this paper, we present a fast attack algorithm tofind two-block collision of hash function MD5. The algorithm is basedon the two-block collision differential path of MD5 that was presented byWang \it et al. in the Conference EUROCRYPT 2005. We found that the derivedconditions for the desired collision differential path were notsufficient to guarantee the path to hold and that some conditions could be modified toenlarge the collision set. By using technique of small range searchingand omitting the computing steps to check the characteristics in theattack algorithm, we can speed up the attack of MD5 efficiently. Compared withthe Advanced Message Modification technique presented by Wang \it etal., the small range searching technique can correct 4 more conditionsfor the first iteration differential and 3 more conditions for thesecond iteration differential, thus improving the probability and thecomplexity to find collisions. The whole attack on the MD5 can beaccomplished within 5 hours using a PC with Pentium4 1.70GHz CPU.