Hash函数MD5攻击技术研究(7)

Hash函数MD5攻击技术研究

第一章绪论３

对Ｈａｓｈ函数最重要的碰撞攻击是生日攻击。生日攻击的名字起源于生日悖论，严格来说，它并不是一个真正的悖论，只是一个概率问题。

生日悖论乜¨：

１

一ｏ

，设Ｍ是一个集合，且Ｍ中互不相同元素的个数为ｔ（ｔ＞ｌＯ），从Ｍ中随机选取样本容量为ｋ＠＞１．１８柝）的样本，则样本中含有两个相同元素的概率大于

一生日攻击乜¨：设Ｈ：Ｘ＿ｙ是一个随机函数，并且Ｙ是一个具有ｔ个值的集合，则随机选取ｋ（ｋ＞１．１８也）个ｘ，其中ｘＥＸ，至少找到一对碰撞的概率大于妄。

生日攻击方法没有利用Ｈａｓｈ函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，且ＰＨａｓｈ值的长度。这种攻击对Ｈａｓｈ函数提出了一个必要的安全条件，即消息摘要必须足够的长。如同密钥的搜索方法作为分组密码的衡量标准一样，抵抗生日攻击的能力被用于衡量单向Ｈａｓｈ函数安全性的重要标准之一。

应用中的Ｈａｓｈ函数，对以上三种抗攻击特性都有严格的规定：对１１比特摘要的Ｈａｓｈ算法，碰撞攻击的复杂度至少为２以；第一原象攻击的复杂度至少为２４；针对长度小于２。比特的消息，第二原象攻击的复杂度至少为２诎。

１．３ＭＤ５的研究历程和意义

ＭＤ５算法是ＭＤ４算法的改进算法。ＲｏｎＲｉｖｅｓｔ于１９９０年提出ＭＤ４单向散列函数，对于输入的消息，算法产生１２８位散列值。该算法首次公布之后，ＢｅｎｄｅｎＢｏｅｒ和ＡｎｔｏｏｎＢｏｓｓｅｌａｅｒｓ对算法三轮中的后两轮进行了成功的密码分析。在一个不相关的分析结果中，ＲａｌｐｈＭｅｒＫｌｅ成功地攻击了前两轮。尽管这些攻击都没有扩展到整个算法，但Ｒｉｖｅｓｔ还是改进了其算法，ＭＤ５算法就此产生。

目前，对ＭＤ５算法的研究主要集中在碰撞攻击和第一原像攻击方面。

在碰撞攻击方面，王小云在２００４年利用明文修改技术，用两个明文块产生了完全碰撞，将计算复杂度分别降低到２３９和２３２；２００５年，来学嘉对文献［ｘ７１所列的产生碰撞的充分条件进行了修正【捌；２００８年，冯登国等探索出一条新的差分路径【２３１，利用类似隧道技术大大提高了产生碰撞的效率，可以在１秒钟内产生一组碰撞的明文对陋Ｊ。

在第一原像攻击方面，Ｄｅ．Ｄ等人在２００７年对ＭＤ５的前２６步进行了原像攻击【２５１，这是研究人员第一次对ＭＤ５进行成功的原像攻击；在２００８年的ＡＣＩＳＰ上，Ｓａｓａｋｉ等对ＭＤ５中间的４４步进行了攻击［２６１，计算复杂度为２９６；在２００８年的ＳＡＣ上，Ａｕｍａｓｓｏｎ等对ＭＤ５前４７步进行了攻击【２７１，复杂度为２１０２，Ａｏｋｉ等以低于２１２８的复杂度找到了对ＭＤ５的完全原像攻击【２８１；２００９年，Ｓａｓａｋｉ和Ａｏｋｉ【２９】把对ＭＤ５的第一原像攻击的计算复杂度降低到２１强４。ＭＤ５算法作为Ｈａｓｈ函数大家庭中的一员，是ＭＤ结构的典型代表。在相当长