Hash函数MD5攻击技术研究

西安电子科技大学硕士学位论文Hash函数MD5攻击技术研究姓名：陈少晖申请学位级别：硕士专业：密码学指导教师：毛明20100101摘要Hash函数是信息安全领域中一个非常重要的基本工具，它在数字签名、身份认证等领域中有着广泛的应用。MD5算法作为Hash函数大家庭中的一员，是MD结构的典型代表，广泛应用于信息安全领域。因此，通过对MD5算法的解析可以掌握Hash函数的基本分析方法，对其他Hash函数的分析有着重要的参考意义。本论文对MD5算法的攻击技术进行了深入的分析和研究。首先系统总结了对该算法进行碰撞攻击的整体思想，运用了比特跟踪技术对差分路径进行分析和控制，利用消息修改技术提高搜索到产生碰撞的明文对的概率；其次通过介绍初始结构和过渡结构的构建，详细解析了对MD5进行原像攻击的技术和方法；最后对Hash函数进行了归纳总结和进一步的研究与探索。关键词：杂凑函数MD5碰撞攻击原像攻击AbstractHashfunctionisaveryimportantandbasictoolinthefieldofinformationsecurity,widelyappliedintheareasofthedigitalsignatureandidentityauthentication．MD5algorithm，asamemberofHashfunctionfamily,isatypicalrepresentativeofMDstructureandwideusedininformationsecurity．Therefore，itishelpfultogetthebasicanalysismethodofHashfunctionstoattackotherHashfunctionsthroughtheresearchofMD5algorithm．AttacktechnologyofMD5algorithmisanalyzedandresearcheddeeplyinthispaper．Firstofall，themainideaofcollisionattackofMD5issummarized．Thebit-trackingtechnologyisusedtoanalyzeandcontrolthedifferentialpaths．Meanwhile，themessagemodificationtechnologyistakenadvantageoftoimprovethepossibilityofsearchingthemessagesforcollision．Secondly,theconstructionoftheinitialstructureandtheskippingstepsisproposedandthetechnologyandmethodofpreimageattackofMD5isanalyzedindetail．Finally,theperformancesoftheHashfunctionsaresummedupandthefurtherresearchdirectioniSintroduced．Keywords：HashfunctionMD5CollisionattackPreimageattack创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：2缠丝垡日期兰型!：兰：关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规定)本人签名：日期丝么生：兰：笪导师签名：日期丝么!121董第一章绪论第一章绪论弟一早珀T匕1．1论文的研究背景Hash函数在数字签名系统中扮演着重要的角色。“Hash函数一词最初来源于计算机科学，表示可以将任意长度的字符串压缩成固定长度的字符串的函数，Hash函数的输出结果，称为Hash值，又称为消息摘要、指纹等。通俗地讲，Hash函数用于压缩消息，是将任意长的消息映射为固定长度的Hash值。消息的Hash值可以看作是数字指纹：像实际生活中指纹可以验证一个人身份的唯一性一样，Hash函数可用于验证一个消息的唯一性。也就是说，给定某一消息和Hash值，我们可以判断此消息与Hash值是否匹配。此外，类似于我们在嫌疑犯数据库里比较一系列犯罪现场出现的指纹一样，我们可以从有限的消息中检测某些Hash值与哪些原始消息相匹配。然而，对于给定的Hash值不可能恢复出其原始消息。Hash函数有三个安全特性，包括抗碰撞攻击、抗原象攻击和抗第二原象攻击。由于这些特性，Hash函数在公钥密码、数字签名、完整性检验、身份认证等领域中有着广泛的应用。目前，Hash函数主要有MDx系列和SHA系列，MDx系列包括MD4[1。、MD5121、HAVALl31、RIPENDl4】等；SHA系列包括SHA．0t51、SHA．1【6l、SHA-256、SHA-384frl等，这些Hash算法体现了目前主要的Hash函数设计技术。本论文是对MD5算法攻击技术的研究和探索。MD5算法是由MD4算法发展而来的，其中MD表示消息摘要(MessageDigest)。MD4算法是较早出现的Hash函数算法，它使用了基本的算术和布尔运算，其设计原则采用了迭代结构的思想。在MD4算法公布后，许多Hash函数算法相继提出，包括MD5、HAVAL、RIPEMD、RIPEMD．128、RIPEMD．160、SHA-0和SHA．1等，它们的大多数算法也是基于MD4算法的设计原则。RIPEMD算法是欧洲计划RIPE的组成部分。RIPEMD．128算法是1996年由HansDobbertin，AntoonBosselaers和BartPreneel提出来，用于替代实际应用中的RIPEMD算法。在近十几年里，对于Hash函数的分析取得了一些进展。1996年，H．Dobbertin给出了一个对MD4算法完整算法的攻击【8l，该攻击以2抛的概率找到一个碰撞，他同时给出了如何找到有意义消息碰撞的方法；1998年，H．Dobbertin证明了MD4算法的前两圈不是单向函数【91，这一结论意味着对于寻找第一原像和第二原像存在有效的攻击。对于RIPEMD算法，H．Dobbertin能够以231的复杂性找到两圈RIPEMD的碰2Hash函数MD5攻击技术研究撞【lo】。随着MDx系歹lJHash函数的发展，对于这些函数的安全性分析也不断深入。B．denBoer和A．B0sselaers找到了针对MD5算法的一种伪碰撞【1l】11，即同一明文在不·同初始值下得到相同Hash值。在1996年欧洲密码大会上，H．Dobbertin公开了另一种形式的伪碰撞【12】，即在两个不同的初始值下的不同消息的一个碰撞。在1998年国际密码大会上，EChabatld和A．Joux证明了用差分攻击方法可以以2姐的概率找到SHA．0的一个碰撞【l引。一些针对Hash函数的更为有效的攻击方法出现在2004年。EliBiham和Raft提出了对SHA．0算法的几乎完全碰捌14】。AAoux给出了一个由4个明文块构成的SHA．0的碰撞【15l。在这些成果中，最为显著的是在2004年国际密码学大会上，王小云等人宣布的对于一系YlJHash函数的碰撞结果，包括MD4[161、MD5[171、HAVAL-128[18l和RIPEMD算法，其中可以找至IJMD4和RIPEMD算法碰撞的复杂性分别低于28和218。王小云提出了一套新的针对MDx系列的Hash函数的分析技术，同时给出了得到满足差分路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概率。2005年，王小云等应用此技术对MD5[171、SHA-0[191、SHA-1[20l算法进行碰撞攻击，取得了很好的效果，在普通的个人电脑上就可以找到相关碰撞的实例。这一攻击技术对现有的Hash函数提出了严峻的挑战，促进了新的Hash算法的开发研究：美国NIST于2007年开始在全球征集新的Hash算法。截至2008年11月，一共提交了64个入选算法；2008年12月有51个算法被NIST接收作为第一轮的候选算法；2009年7月，NIST公布了进入第二轮的14个算法；2010年将公布进入最终一轮的5个算法；最终将于2012年选出获胜算法并命名为SHA-3。1．2Hash函数设计原则Hash函数的算法是公开的，对于每一个给定的消息串，计算输出的Hash值是容易的；但是从Hash值反推算出输入的明文是困难的。实际应用中，安全的Hash函数必须符合以下三个设计原则：1．抗碰撞性攻击：由于Hash函数具有压缩的性质，所以必然存在多个消息串对应同一Hash值的可能，这就是所说的碰撞的出现。实际应用中由于Hash函数的抗碰撞性，导致现实中很难找到两个不同的消息串对应同一个Hash值的情况。2．抗第一原像攻击：对于任意一个消息串a，容易得到它的Hash值h(a)；但是从它I拘Hash值h(a)很难推出相应的消息串a，此时消息串a称之为h(a)的原像。抗第一原像攻击使得Hash函数具有单向性的特点。3．抗第二原像攻击：对于某一给定的消息串a，很难找到另一不同的消息串b，使得h(a)=h(b)。抗第二原像攻击使得Hash函数可以应用于数字签名和身份认证领域。第一章绪论3对Hash函数最重要的碰撞攻击是生日攻击。生日攻击的名字起源于生日悖论，严格来说，它并不是一个真正的悖论，只是一个概率问题。生日悖论乜¨：设M是一个集合，且M中互不相同元素的个数为t(tlO)，从M中随机选取样本容量为k@1．18柝)的样本，则样本中含有两个相同元素的概率大于1一o，一生日攻击乜¨：设H：X_y是一个随机函数，并且Y是一个具有t个值的集合，则随机选取k(k1．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所列的产生碰撞的充