Hash函数MD5攻击技术研究(7)
时间:2025-07-11
时间:2025-07-11
Hash函数MD5攻击技术研究
第一章绪论3
对Hash函数最重要的碰撞攻击是生日攻击。生日攻击的名字起源于生日悖论,严格来说,它并不是一个真正的悖论,只是一个概率问题。
生日悖论乜¨:
1
一o
,设M是一个集合,且M中互不相同元素的个数为t(t>lO),从M中随机选取样本容量为k@>1.18柝)的样本,则样本中含有两个相同元素的概率大于
一生日攻击乜¨:设H:X_y是一个随机函数,并且Y是一个具有t个值的集合,则随机选取k(k>1.18也)个x,其中xEX,至少找到一对碰撞的概率大于妄。
生日攻击方法没有利用Hash函数的结构和任何代数弱性质,它只依赖于消息摘要的长度,且PHash值的长度。这种攻击对Hash函数提出了一个必要的安全条件,即消息摘要必须足够的长。如同密钥的搜索方法作为分组密码的衡量标准一样,抵抗生日攻击的能力被用于衡量单向Hash函数安全性的重要标准之一。
应用中的Hash函数,对以上三种抗攻击特性都有严格的规定:对11比特摘要的Hash算法,碰撞攻击的复杂度至少为2以;第一原象攻击的复杂度至少为24;针对长度小于2。比特的消息,第二原象攻击的复杂度至少为2诎。
1.3MD5的研究历程和意义
MD5算法是MD4算法的改进算法。RonRivest于1990年提出MD4单向散列函数,对于输入的消息,算法产生128位散列值。该算法首次公布之后,BendenBoer和AntoonBosselaers对算法三轮中的后两轮进行了成功的密码分析。在一个不相关的分析结果中,RalphMerKle成功地攻击了前两轮。尽管这些攻击都没有扩展到整个算法,但Rivest还是改进了其算法,MD5算法就此产生。
目前,对MD5算法的研究主要集中在碰撞攻击和第一原像攻击方面。
在碰撞攻击方面,王小云在2004年利用明文修改技术,用两个明文块产生了完全碰撞,将计算复杂度分别降低到239和232;2005年,来学嘉对文献[x71所列的产生碰撞的充分条件进行了修正【捌;2008年,冯登国等探索出一条新的差分路径【231,利用类似隧道技术大大提高了产生碰撞的效率,可以在1秒钟内产生一组碰撞的明文对陋J。
在第一原像攻击方面,De.D等人在2007年对MD5的前26步进行了原像攻击【251,这是研究人员第一次对MD5进行成功的原像攻击;在2008年的ACISP上,Sasaki等对MD5中间的44步进行了攻击[261,计算复杂度为296;在2008年的SAC上,Aumasson等对MD5前47步进行了攻击【271,复杂度为2102,Aoki等以低于2128的复杂度找到了对MD5的完全原像攻击【281;2009年,Sasaki和Aoki【29】把对MD5的第一原像攻击的计算复杂度降低到21强4。MD5算法作为Hash函数大家庭中的一员,是MD结构的典型代表。在相当长
上一篇:第二章_多项式练习