Hash函数MD5攻击技术研究

1、西安电子科技大学硕士学位论文 Hash函数MD5攻击技术研究 姓名：陈少晖 申请学位级别：硕士 专业：密码学 指导教师：毛明20100101摘要Hash函数是信息安全领域中一个非常重要的基本工具，它在数字签名、身份 认证等领域中有着广泛的应用。MD5算法作为Hash函数大家庭中的一员，是MD 结构的典型代表，广泛应用于信息安全领域。因此，通过对MD5算法的解析可以 掌握Hash函数的基本分析方法，对其他Hash函数的分析有着重要的参考意义。本论文对MD5算法的攻击技术进行了深入的分析和研究。首先系统总结了对 该算法进行碰撞攻击的整体思想，运用了比特跟踪技术对差分路径进行分析和控 制，利用消息修

2、改技术提高搜索到产生碰撞的明文对的概率；其次通过介绍初始 结构和过渡结构的构建，详细解析了对MD5进行原像攻击的技术和方法；最后对 Hash函数进行了归纳总结和进一步的研究与探索。关键词：杂凑函数MD5碰撞攻击原像攻击AbstractHash function is a very important and basic tool in the field of information security, widely applied in the areas of the digital signature and identity authenticationMD5 algorithm，as

3、 a member of Hash function family,is a typical representative of MD structure and wide used in information securityTherefore，it is helpful to get the basic analysis method of Hash functions to attack other Hash functions through the research of MD5 algorithmAttack technology of MD5 algorithm is anal

4、yzed and researched deeply in thispaperFirst of all，the main idea of collision attack of MD5 is summarizedThe bit-tracking technology is used to analyze and control the differential pathsMeanwhile， the message modification technology is taken advantage of to improve the possibility of searching the

5、messages for collisionSecondly,the construction of the initial structureand the skipping steps is proposed and the technology and method of preimage attack ofMD5 is analyzed in detailFinally,the performances of the Hash functions are summed up and the further research direction iS introducedKeywords

6、：Hash function MD5 Collision attack Preimage attack创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：2缠丝垡日期兰型!：兰：<关于论文使用授权的

7、说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在 解密后遵守此规定)本人签名：日期丝么生：兰：笪导师签名：日期丝么!1 2 1董第一章绪论第一章绪论弟一早珀T匕11论文的研究背景Hash函数在数字签名系统中扮演着重要的角色。“Hash函数"一词最初来源于 计算机科学，表示可以将

8、任意长度的字符串压缩成固定长度的字符串的函数， Hash函数的输出结果，称为Hash值，又称为消息摘要、指纹等。通俗地讲，Hash函数用于压缩消息，是将任意长的消息映射为固定长度的Hash 值。消息的Hash值可以看作是数字指纹：像实际生活中指纹可以验证一个人身份 的唯一性一样，Hash函数可用于验证一个消息的唯一性。也就是说，给定某一消 息和Hash值，我们可以判断此消息与Hash值是否匹配。此外，类似于我们在嫌 疑犯数据库里比较一系列犯罪现场出现的指纹一样，我们可以从有限的消息中检 测某些Hash值与哪些原始消息相匹配。然而，对于给定的Hash值不可能恢复出 其原始消息。Hash函数有三个

9、安全特性，包括抗碰撞攻击、抗原象攻击和抗第二 原象攻击。由于这些特性，Hash函数在公钥密码、数字签名、完整性检验、身份 认证等领域中有着广泛的应用。目前，Hash函数主要有MDx系列和SHA系列，MDx系列包括MD41。、 MD5121、HAVALl31、RIPENDl4】等；SHA系列包括SHA0t51、SHA1【6l、SHA-256、 SHA-384frl等，这些Hash算法体现了目前主要的Hash函数设计技术。本论文是对MD5算法攻击技术的研究和探索。MD5算法是由MD4算法发展而来的，其中MD表示消息摘要(Message Digest)。MD4算法是较早出现的Hash函数算 法，它使

10、用了基本的算术和布尔运算，其设计原则采用了迭代结构的思想。在MD4 算法公布后，许多Hash函数算法相继提出，包括MD5、HAVAL、RIPEMD、 RIPEMD128、RIPEMD160、SHA-0和SHA1等，它们的大多数算法也是基于MD4算法的设计原则。RIPEMD算法是欧洲计划RIPE的组成部分。RIPEMD128算法是1996年由Hans Dobbertin，Antoon Bosselaers和Bart Preneel提出来，用于替代实际应 用中的RIPEMD算法。在近十几年里，对于Hash函数的分析取得了一些进展。1996年，HDobbertin给 出了一个对MD4算法完整算法的攻

11、击【8l，该攻击以2抛的概率找到一个碰撞，他同 时给出了如何找到有意义消息碰撞的方法；1998年，HDobbertin证明了MD4算法 的前两圈不是单向函数【91，这一结论意味着对于寻找第一原像和第二原像存在有效 的攻击。对于RIPEMD算法，HDobbertin能够以231的复杂性找到两圈RIPEMD的碰2 Hash函数MD5攻击技术研究撞【lo】。随着MDx系歹lJHash函数的发展，对于这些函数的安全性分析也不断深入。 BdenBoer和AB0sselaers找到了针对MD5算法的一种伪碰撞【1l】11，即同一明文在不· 同初始值下得到相同Hash值。在1996年欧洲密码大会上

12、，HDobbertin公开了另一 种形式的伪碰撞【12】，即在两个不同的初始值下的不同消息的一个碰撞。在1998年 国际密码大会上，EChabatld和AJoux证明了用差分攻击方法可以以2姐的概率找到 SHA0的一个碰撞【l引。一些针对Hash函数的更为有效的攻击方法出现在2004年。Eli Biham和Raft提出了对SHA0算法的几乎完全碰捌14】。AAoux给出了一个由4个明文块构成的SHA0 的碰撞【15l。在这些成果中，最为显著的是在2004年国际密码学大会上，王小云等 人宣布的对于一系YlJHash函数的碰撞结果，包括MD4161、MD5171、HAVAL-12818l和RIPE

13、MD算法，其中可以找至IJMD4和RIPEMD算法碰撞的复杂性分别低于28和218。王小云提出了一套新的针对MDx系列的Hash函数的分析技术，同时给出了得 到满足差分路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击 的成功概率。2005年，王小云等应用此技术对MD5171、SHA-0191、SHA-120l算法 进行碰撞攻击，取得了很好的效果，在普通的个人电脑上就可以找到相关碰撞的 实例。这一攻击技术对现有的Hash函数提出了严峻的挑战，促进了新的Hash算法 的开发研究：美国NIST于2007年开始在全球征集新的Hash算法。截至2008年11月， 一共提交了64个入选算法；2

14、008年12月有51个算法被NIST接收作为第一轮的候选 算法；2009年7月，NIST公布了进入第二轮的14个算法；2010年将公布进入最终一 轮的5个算法；最终将于2012年选出获胜算法并命名为SHA-3。12 Hash函数设计原则Hash函数的算法是公开的，对于每一个给定的消息串，计算输出的Hash值是容 易的；但是从Hash值反推算出输入的明文是困难的。实际应用中，安全的Hash函 数必须符合以下三个设计原则：1抗碰撞性攻击：由于Hash函数具有压缩的性质，所以必然存在多个消息串对 应同一Hash值的可能，这就是所说的碰撞的出现。实际应用中由于Hash函数的抗 碰撞性，导致现实中很难找

15、到两个不同的消息串对应同一个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是一个集合，且

16、M中互不相同元素的个数为t(t>lO)，从M中随机选取样本容量为k>118柝)的样本，则样本中含有两个相同元素的概率大于1 一o，一生日攻击乜¨：设H：X_y是一个随机函数，并且Y是一个具有t个值的集合，则随机选取k(k>118也)个x，其中xEX，至少找到一对碰撞的概率大于妄。生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘 要的长度，且PHash值的长度。这种攻击对Hash函数提出了一个必要的安全条件， 即消息摘要必须足够的长。如同密钥的搜索方法作为分组密码的衡量标准一样， 抵抗生日攻击的能力被用于衡量单向Hash函数安全性的重要标准之一

17、。应用中的Hash函数，对以上三种抗攻击特性都有严格的规定：对11比特摘要 的Hash算法，碰撞攻击的复杂度至少为2以；第一原象攻击的复杂度至少为24；针 对长度小于2。比特的消息，第二原象攻击的复杂度至少为2诎。13 MD5的研究历程和意义MD5算法是MD4算法的改进算法。Ron Rivest于1990年提出MD4单向散列 函数，对于输入的消息，算法产生128位散列值。该算法首次公布之后，Ben den Boer 和Antoon Bosselaers对算法三轮中的后两轮进行了成功的密码分析。在一个不相 关的分析结果中，Ralph MerKle成功地攻击了前两轮。尽管这些攻击都没有扩展 到整个

18、算法，但Rivest还是改进了其算法，MD5算法就此产生。目前，对MD5算法的研究主要集中在碰撞攻击和第一原像攻击方面。在碰撞攻击方面，王小云在2004年利用明文修改技术，用两个明文块产生了 完全碰撞，将计算复杂度分别降低到239和232；2005年，来学嘉对文献x71所列 的产生碰撞的充分条件进行了修正【捌；2008年，冯登国等探索出一条新的差分路 径【231，利用类似隧道技术大大提高了产生碰撞的效率，可以在1秒钟内产生一组 碰撞的明文对陋J。在第一原像攻击方面， DeD等人在2007年对MD5的前26步进行了原像攻 击【251，这是研究人员第一次对MD5进行成功的原像攻击；在2008年的A

19、CISP上， 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结构的典型代表。在相当长4 Hash函数MD5攻击技术研究的时间内，MD5算法都广泛应用于信息安全领域，具有其他算法所不可比拟的应 用优势。因此，通过对MD5算法的解析可以掌握Hash函数的基本分析方

20、法，对 其他Hash函数的分析有着重要的参考意义。14研究的主要内容本论文研究的主要内容是针对MD5算法的结构特点，对其进行碰撞攻击和第 一原像攻击的研究，分析总结其攻击的思路和方法，在此基础上对其攻击的核心 环节进行深入的探索，逐步形成了一套完整的MD5分析研究体系，对今后新的 Hash算法的学习研究有着重要的借鉴意义。研究的主要内容如下：1MD5的碰撞攻击 总结了碰撞攻击的整体思想和关键步骤，从差分的引入，差分路径的控制和充分条件的推导等方面，展示了MD5算法产生碰撞的全过程，用比特跟踪技术详细 记录了在算法迭代过程中差分的继承、产生和消除，研究了消息修改技术的实际 应用，并从程序上得以验

21、证。2MD5的第一原像攻击 根据MD5消息字的排列特点，引入“中立字”的概念，构建“初始结构"和“过渡结构”，将整个MD5算法分为两个部分，再将两个部分分别对应两个“中 立字"，有效降低了攻击的计算复杂度；对原像攻击进行了整体规划和布局，在攻 击过程中设计了程序的限制性搜索功能。15论文的章节安排本论文共分为五章，结构如下：第一章介绍了论文的研究背景， Hash函数的发展历程，MD5的研究意义和本 文的研究内容。第二章介绍了相关的基础知识： MD5算法，三种差分的异同，循环左移的不同结果。 第三章对MD5的碰撞攻击进行了详细的解析：介绍了碰撞攻击的总体思路，利用比特跟踪技术

22、对差分路径进行分析和控制，利用明文修改技术对产生碰撞的明文对进行搜索，最后对MD5的碰撞攻击进行了总结。 第四章对MD5的原像攻击进行了详细的解析：先介绍了预备知识，然后对原像攻击最主要的两个结构：初始结构和过渡结构的构建进行了分析，最后对MD5的原像攻击进行了总结。第一章绪论5第五章对全文进行了总结并对将来的研究提出了展望。第二章相关的基础知识7第二章相关的基础知识目前，应用中的大多数Hash函数的设计都采用了迭代结构，每次处理一个固 定长度的消息分组。迭代结构的典型代表是MD结构，该结构是基于压缩函数的 迭代：厂：o，1)”×o，畸“-o，1)”其中咒>m1式(2-1)一个

23、Hash函数的任意有限长度的输入X在被压缩之前，首先被划分长度为b 比特的消息分组五，这个过程包含了消息的填充，也就是在最后的一个消息分组 的后面附加若干个额外的比特，使得填充后的消息的长度恰好为b比特的整数倍。 为了安全和便于应用，通常填充信息包含了填充前消息的长度。每一个消息块鼍作 为压缩函数f的输入，f的输出为一个n比特的中间结果。f可以看成是一个具有 两个输入变量的函数：前一个迭代输出的中间结果以及输入的消息分组t，让皿代 表第i个迭代的输出结果。一个输入为X'-IlX2··x的Hash函数迭代过程如下：H。=，式(22)4,=，(Hil；毛)，1sf sf

24、； 式(2-3)h(x)=g(只) 式(2-4)日H称为第i一1个迭代和第i个迭代之间的链接变量，风是一个预先定义的初 始值。在最后一步使用一个输出变换函数g，把n比特的链接变量映射成m比 特的输出结果g(H)。在很多Hash算法中，g经常被定义成恒等映射g(皿)=q。21MD5算法211整体结构描述 MD5算法采用迭代型Hash函数的一般结构，算法如图21所示。算法的输入为任意长的消息(图中为k比特)，分为512比特长的消息分组，输出为128比特的消息摘要。8 Hash函数MD5攻击技术研究 填充(1至tJ512bit)消息长度(K mod 264)匠卜512bit斗41-512bit

25、9;互128-IVcVq CVLl图21 Hash函数一般结构消息处理过程如下：1对消息的填充。对消息的填充，使得其比特长在模512下为448，即填充后 消息的长度为512的某一倍数减去64，留出64比特以备第2步使用。步骤1是必 须的，即使消息长度已经满足要求，仍需要填充。例如，消息长为448比特，则 需要填充512比特，使其长度变为960，因此填充的比特数大于等于1，小于等于512。填充的方法是确定的：第1位为1，后面的位都为O2附加消息的长度。用步骤1留出的64比特以littleendian方式来表示消息被 填充前的长度。如果消息的长度大于264，则以2“为模数取模。Littleendi

26、an方式是指数据的最低有效字节(byte)(或者最低有效位)的优先 顺序存储数据，即将最低有效字节(或者最低有效位)存于第地址字节(或者位)。 相反的存储方式称之为big-endian方式。前两步执行完后，消息长度为512的倍数(设为L倍)，因此可将消息表示为分组长为512比特的一系列分组KXl：，而每一分组有可表示为16个32比特长的字，这样消息中的总字数为N=Lxl6，因此消息又可按字表示为M0，1， N1】。3对MD缓冲区初始化。算法使用128比特长的缓冲区以存储中间结果和最 终Hash值，缓冲区可以表示为4个32比特长的寄存器似，B，C，D)，每个寄存器都 以littleendian方

27、式存储数据，其初值(以存储方式)为A=01234567，B=89ABCDEF, C=FEDcBA98，D=76543210，实际上为A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476。4以分组为单位对消息进行处理。每一分组K(q=0， ，L-1)都经一压缩函 数处理，压缩函数是整个MD5算法的核心，共有4个不同的布尔函数，分别为F 函数、G函数、H函数、l函数。每一轮的输入为当前处理的消息分组yq和缓冲区 当前值，输出仍放在缓冲区中以产生新的A、B、C、D。每一轮处理还需要加上第二章相关的基础知识9常数表中的常数。常数表中一共有64个元素，第i个常数值为23

28、2 xabs(sin(i) 的整数部分。第四轮的输出再与第一轮的输入值相加；相加的结果即为压缩函数 的输出值。5输出。消息L个分组都被处理完后，最后一个压缩函数输出值即为整个MD5 运算的最终Hash值，即消息摘要。212压缩函数压缩函数是MD5算法的核心部件，对压缩函数的分析是对算法进行成功攻击 的重要前提。该压缩函数中有4轮处理过程，每一轮有对缓冲区ABCD进行16步 迭代运算，每一步的运算形式(如图22所示)为：a=b+(g+func(b，c，d)+x【i】+T【i】)<<<k)式(2-5)其中a、b、c、d为缓冲区的4个字，func代表具体的布尔函数，为F、G、H、I

29、 之一；X【i】为该步使用的明文字；T【i】为该步使用的常数；K为该步循环左移的比 特数。YCVq+1图22迭代结构10 Hash函数MD5攻击技术研究在计算新的a的表达式中，“+”为模232的加法。明文字(消息字)在4轮处 理的过程中，每一轮以不同的次序使用16个明文字，第一轮按照原来顺序进行使 用。第二轮到第四轮分别对这16个字的次序进行变换(如表21所示)，然后以新 的次序使用这16个字。表21明文字转换次序轮数 明文字的次序1l2(1+5半i)mod 163(5+3半i)mod 164(7木i)mod 164轮处理过程分别使用不同的布尔函数F、G、H、I，每个布尔函数的输入为3 个32

30、比特的字，输出为一个32比特的字，其中的运算为逐比特的逻辑运算，即 输出的第n个比特是3个输入的第n个比特的函数。四个布尔函数，如表22所示：表22四个布尔函数轮数 布尔函数 func(b，C，d)1V(b，C，d)(6 A c)V(，6 A d)2G(b，C，d)p A d)V(c A-,d)3H(b，C，d)bCod4I(b，C，d)c op Vd) 四个布尔函数的真值如表23：表23布尔函数真值表FGH00010 10111O0O01010110111第二章相关的基础知识213移位和明文字顺序表在对MD5算法进行碰撞攻击的过程中，必须考虑移位对整个差分路径的影响。 在碰撞攻击过程中，明文

31、字的编排顺序是差分引入的重要考虑因素之一；在原像 攻击过程中，明文字的编排顺序很大程度上确定了初始结构和过渡结构的位置。表24移位比特表步骤 移位比特数1，2，157 12 17 22 7 12 17 22 7 12 17 22 7 12 17 2216，17，315 9 14 205 9 14 205 9 14205 9 14 2032，33，474 11 16 23 4 11 16 23 4 11 16 23 4 11 16 2348，49，636 10 15 2l 6 10 15 21 6 10 15 21 6 10 15 21表25明文字顺序步骤 明文字的顺序1，2，15O 1 2 3

32、 4 5 6 7 8 9 10 11 12 13 14 1516，17，311 6 11 O 5 10 15 4 9 14 3 8 13 2 7 1232，33，475 8 11 14 1 4 7 10 13 O 3 6 9 12 15 248，49，63O 7 14 5 12 3 10 1 8 15 6 13 4 11 2 922MD5的差分分析221三种差分的概念引入差分分析是破译Hash函数最有效的工具之一，其中涉及到异或差分、符号差 分和模差分等几个重要的概念。异或差分：设X和X是两个32位的数，其异或差分为两个数的比特位的异 或运算，表示为XoX。异或差分能反映两个数的对应位的相同与

33、否。符号差分：同样，设X和X 7是两个32位的数，为了更好的体现这两个数的某一位的差别，在异或差分的基础上进一步引入符号差分“+"、“I"号。例如，XX=【5,6，7，8,"-,-27，这说明X和X从第5到第27位都不同，而且从符号可以看 出X的第5到第26位是0，第27位是1；而X 7的第5到第26位是1，第27位 是0。符号差分可以很容易看出两个数的各位的差别。模差分：同样，设X和X是两个32位的数，模差分是将两个数的差别用整 数减法体现出来。例如，X 7X用符号差分表示为【5，6，7，8,-",-27，此时用模差分 表示为X 7X=-24。符号差分

34、的扩展在MD5算法破译过程中具有广泛的应用，利用符号差分的扩 展，可以达到自己所需要的差分目标。例如，对2k、2k可以进行如下扩展：2k=2k¨2k=2k+22k+1-2k='''=2n-l_2n-22n-32k，其中0sk<ns322k=2k+1+2k=2k+2+2k+1+2k= =2n+2n'2+2n-3·+2k，其中0<k<n"：3212 Hash函数MD5攻击技术研究在MD5的运算中，第32位的位置既特殊又重要，其“+"和“”在某种程度 上是可以看成一致的。鉴于这一位的特殊性，可以将上面两个等式进

35、行进一步扩 展：2k=2k+I2k：2k+2_2k+12k= =231230229一·2k=一(231+230+229+2k)式(26)2k=2k+1+2k=2k+2+2“1+2k= =231+230+229-+2k=(231+230+229一·+2k)式(27)为了便于分析，符号差分可以简化为如下的表示方式：【k】=【k+1，-k】=【k+2，一(k+1)，-k】= =In一1，-(n一2) -k】=【32，-31-',-k】=【一32，-31"-,-k】式(2-8)【-k】=【-(k+1)，k】=【-(k+2)，(k+1)，k】= =【-(n一1)，(

36、n-2) k】=【-32，31 ，k】=【32，31 ，k】式(29)另外，上面的差分扩展还可以将两个元素联合起来考虑：【-+2)，k】=【-(k+2)，(k+1)，一k】=【-(k+1)，-k】=【·(k+3)，(k+2)，(k+1)，-k】=【-(k+3)，(k+2)，k】=式(2-10)符号差分扩展在MD5差分路径的控制上有着至关重要的作用，一般情况下，在模差分确定后，可以根据具体需要确定符号差分。222循环左移的结果分析MD5算法在运算过程中有大量的左循环移位，所以在引入差分之后，符号差分的左循环移位会出现几种不同的情况，需要分别进行分析处理。 例如，文献【24】，设2。=【

37、k+x，·(1【+x-1),-,-k，其中1 s x32-k，设循环左移的位数为s(用<<<s表示)，分三种情况讨论移位后的结果： 当k+x+s<32，移位的结果为(2。<<<s)=2“。； 当k+x+s>32且k+x<32，移位的结果为(2。<<<s)=2m+1；当k+x>32，移位的结果为(2。<<<s)=2。砝。证明过程如下：1当k+x+ss32时，(2。<<<s)=【k+x，一(k+x一1)，-(k+x一2， )，-k，】<<<s=【k+x+s，

38、(k+x+s1)， ，-(k+s)】=2k+5 mod(232)式(211)2当k+x+s>32且k+s<32时，(2。<<<s)=【k+x，-(k+x一1)，一(k+x·2， )，-k，】<<<s=【-32,"-,-(k+x)，k+x+s-32，一(k+x+s一32-1)， ，一1=【32,"-,-(k+x)，k+x+s一32，一(k+x+s-32-1)， ，一1第二章相关的基础知识13=(2h+1)mod(232)式(212)3当k+s>32时，(2。<<<s)=【k+x，-(k+x

39、83;1)，-(k+x-2， )，-k，】<<<s=fk+x+s一32，一(k+x+s一321)，一(k+s一32)=(2“。32)mod(232)式(213) 同理，设一2。-(k+x)，(k+x1)， ，k】，其中1 s X s 32一k，同样分三种情况讨论：当k+x+s s 32，移位的结果为(2。<<<s)=2；当k+x+s>32，k+s s 32，移位的结果为(2。<<<s)=(2k+5+1)； 当k+s>32，移位的结果为(2。<<<s)=2k-“-32。第三章MD5的碰撞攻击第三章MD5的碰撞攻击

40、31碰撞攻击的整体思想破译MD5算法是个系统工程例。在破译过程中，首先，要从整体上确立一个 框架，确定一个产生碰撞的总体思路；其次，根据整体思路应用明文修改等相关 技术和非线性函数的特性等来实现差分路径；最后，尽可能简化实现差分路径的 充分条件，降低计算复杂度，提高计算机“搜索”到碰撞的概率。311引入明文差分破译MD5算法的关键之一是在明文中引入差分。好的明文差分有以下几个特 点：首先，要有尽可能多的“自由字"，这样可以放宽产生碰撞的充分条件，提高 碰撞概率；其次，明文中第一次出现差分的位置应该尽量远离第一个字，这对于 消息修改技术至关重要，可以使明文存在更大的修改空间，同时也有利

41、于计算机 的成功搜索；再次，实现碰撞所需要的充分条件越少越好，这样可以有效的降低计算复杂度；最后，明文的“块数”越少，说明实现碰撞的技术水平越高。目前，发表的三种MD5算法的碰撞实例17，23，24，都是采用“两个明文块"，即1024位 的明文，其中文献17，23】的两个明文块的差分的位置都是位置对称、符号相反， 这种差分的引入是针对Hash函数MD结构的特点而设计的，它能使得第一明文块和第二明文块分别产生的差分值能够位置对称，符号相反(第32位除外)，最终 的Hash值是将两个值相加。这样，两个明文块产生的差分最终将抵消(第32位 以溢出的形式抵消)，从而产生了碰撞。文献f24】差

42、分的引入摆脱了对称的模式，但其差分的消除仍遵循上述原则。最后要说明的是，以上三种MD5算法的碰撞实例，在寻找碰撞的过程中，都需要利用明文修改技术来确保得到碰撞所需的明文。312选择差分路径破译MD5算法的关键之二是要选择好差分路径。差分路径的控制很大程序上 是利用符号差分的扩展来实现的，使得整个差分按照整体的需要进行。选择差分 路径时，要尽量减少差分中的汉明重量。一般情况下，尽量把差分引到第32位， 由于该位置的特殊性，容易消除差分。在选择差分路径的过程中，必须关注每一步运算中差分的继承和非线性函数的 位运算。以MD5第12步为例，b3=c3+(b2+F(c3，d3，a3)+m11+t11)&

43、lt;<<22)，令16 Hash函数MD5攻击技术研究11=b2+F(c3，d3，a3)+m1，+ll，其中tn是常数。b3的差分有以下两个来源：1直接继承c。的差分。2间接继承。，的差分：第一是b：的差分，第二是F(c，d，a。)的差分，第三是m，的差分(如果m，有差分的前提下)。在计算b，运算中，只有F函数是位运算，其他都是在模232下的加法运算。在 这个过程中，首先充分关注F函数，利用F函数的性质，产生下面步骤所需要的 差分，同时消除不需要的差分；其次，符号差分的扩展很大程度上是依靠”来实现的。在模差分确定的前提下，符号差分有多种可能，必须根据需要来选择；最后，结合第32位

44、的特殊性和符号差分的扩展，跟踪循环左移对这个差分继承的影响。313确定充分条件破译MD5算法的关键之三是控制差分路径的充分条件。充分条件越少，对明 文的限制程度越小，越容易找到碰撞。在MD5中利用F函数、G函数、H函数和 I函数的性质，循环左移的性质和差分路径的整体需要，来确定差分的充分条件。在确定充分条件的过程中，必须利用非线性函数的性质。MD5算法中有F函 数、G函数、H函数和I函数这四个非线性函数，现在以F函数和H函数为例， 总结非线性函数的特性【31】。从F(X，Y z)-(x八V(-i XAY)的表达式，可以看出F函数是一个选择函 数。选择函数的意思是：F函数的值的选取是根据X的值来

45、决定选取Y或者Z的 值：即如果X=I，F函数的值等于Y的值；如果X=0，F函数的值等于Z的值。X 的值对F函数的值起到一个选取的作用。根据上述所说的F函数的选取的性质， 我们可以总结出F函数的三个性质：1F(X，Y z)=F(1 X，Y z)，当且仅当Y=z；2F(X，Y z)=F(X，-I Y z)，当且仅当x=O；3F(X，Y z)=F(X，Y 1 z)，当且仅当x=1；从H(X，Y Z)=XoYOZ的表达式，可以看出H函数是个对称函数，该函数具有以下两个性质：1X，Y z这三个参数中相同的位有奇数个1， H函数的值对应的位为1；2x，Y Z这三个参数中相同的位有偶数个1，H函数的值对应的

46、位为O。 总之，在寻找MD5碰撞的过程中，上述三个方面都很关键，他们相辅相成，相互协调，必须统一起来整体考虑。第三章MD5的碰撞攻击1732比特跟踪技术在MD5碰撞攻击的过程中，在差分引入之后，必须应用比特跟踪技术对差分进行比特级别的跟踪，以确保有效地控制差分路径，最终实现碰撞。就MD5的第一轮而言，以四个连续步骤为例：a=b+(a+F(b，C，d)+mi+ti)<<<si)；式(31) d=a+(d+F(a，b，c)+m“1+t“1)<<<s“1)；式(32) c=d+(c+F(d，a，b)+mi+2+ti+2)<<<si+2)；式(3-

47、3) b=c+(b+F(c，d，a)+mi+3+t“3)<<<si+3)；式(34) 在这每一步中，只有F函数的运算是位运算，除此以外的运算都是模232的加法运算。因此，在F函数中，其三个参数某一比特的变化，最终只会影响F函数 的相应的比特位；F函数以外的运算，由于可能存在进位的问题，所以影响的可能 不只是变化的那一比特，而且可能是影响其周围的一连串的比特位，影响的范围可能很大，这就需要依靠比特跟踪技术来监控。在整个运算过程中，第32比特位置特殊，其进位将会产生溢出，这个性质在比特跟踪过程中至关重要。下面将以 文献f171为例，介绍比特跟踪技术在碰撞攻击中的应用。321符号说

48、明1M=(mo，m。， ，m。5)和M=(mo，m。， ，m。，I)代表相对应的两个512比特的明文 块，AM=(Am。，Aml，一，Am。，)代表两个相对应的明文块的差分，其中每个m；为32比特的字。2ai,di，ci，bi分别代表第(4i3)步，第(4i2)步，第(4i1)步，第4i步的输出，其中1i16；同样的方法定义a；，b；，ci',d；。3ai,j,bi,j,ciJ,du分别代表ai，di，ci，bi的第j比特，其中，最高位为第32比特，最低位为第1比特。4西舻IIij,分别表示mi和E的第j比特，其中中；表示第i步的逻辑函数，V； 表示循环左移的整体的表达式。 例如，第8

49、步中，西7=F(c2，d2，a2)=(c2 A d2)V(-1c2a2)，1l，7=bl+F(c2，d2，a2)+m7+t7。5Xi,j=x硒tx硝=-1，这是表示第j比特的差分。如果值为1，说明xi的第j Lt 特是1而X；的第j比特是0；如果值是0，说明xi 7的第j比特是0而x；的第j比 特是1，其中X可以是a,b，c，d，西，V。6Ax；jl,j2， ，jl】=Xijl,j2， 'jl】-X；，表示x；的第jLj2， ,jl比特的变化。 x；【j1，j2， ，jl】表示具体第j1，j2""jl的比特的变化，其中“+"表示该比特从O 变成了1；“”表

50、示该比特从1变成了0。18 Hash函数MD5攻击技术研究322比特跟踪技术的应用文献1171是用两个明文块(M。，M，)，明文长度共为1024比特，对应的差分明文 块为(M。，M1)，经过两次MD5运算，(Mo，M1)和(Mo，M。)产生相同的Hash值，这就成功找到了碰撞。本文通过对第一次MD5迭代运算的前8步进行研究，所以只关注Mo和M o，其中：AMo=Mo'-Mo=(0，0，0，0，231,0，0，0，0，0，0，215,0，0，231,0)。从这 里可以看出，m。开始引入差分，本文结合文献【17】，以前8步为例，介绍比特跟 踪技术对差分路径的控制。第5步分析： 第5步的表达

51、式：a2=b。+(a1+F(b1，Ca，d1)+m4+t4)<<<7)，开始引入了差分，&rn。=231，在前4步的过程中，明文没有引入差分，所以ax,b，C1，d，都没有出现差 分，即81=a1，dl=d1，ca=C1，bl=b1。Aa2=(lI，4【31】<<<7)=(一231)<<<7)=-26。 根据基础知识，第32比特的“+”和“”是相同的，所以，此时明文引入的差分231， 看成231来处理，经过循环左移，a，的模差分为26，为了下面步骤的需要，需要将这个模差分进行扩展，满足a2【+7，+8，+9，+22，23】。此时要求

52、a2,7=a 2，8=a2，9= =a2刀=O， a2，23=1。第6步分析：第6步的表达式：d2-a2+(d1+F(a2，b1，c1)+m5+t5)<<<12)，这步明文Am5=O， Ad2=Aa2+(V 5<<<12)，Ad：的差分由两部分组成：首先，d：继承了Aa2=26这 部分的值；其次，(胛。<<<12)产生了后面所需要的差分223+231。根据前面的基础知识，为了达到这个目标，需要充分利用F函数的性质：1利用F(X，Y z)=Fn x，Y Z)，当且仅当Y=Z。第6步中b。j=clj，这个条件确保a：的第 i比特的变化不会影响d

53、：， 其中i=7，8，9，10，11，13，14，15，16，17，18，19，21，22，23。2223+231是由胖，12】和Aqs，20】经过循环左移12比特形成的。此时由于没 有差分的扩展，满足Aqs，12】=中，【12】=1，胛；201=A，201=1。此时要求 bz121-121=1，bl201-q201=1，即bl【12】=1，121=0，bx201=1，ca20=O(见文献【17】表4)。第7步分析：第7步表达式：c2=d2+(Cl+F(d2，a2，b1)+m6+t6)<<<17)，这步明文am6=O，Ac：=Ad，+OF。<<<12)，同第

54、6步的分析一样，c，的差分由两部分组成：1Ac2继承了Ad2=-26+223这部分的值，而且都进行了扩展，c2【7，8，9，10，11，-12】 这些变化都是由26引起的：设C：。的第7到12比特为?，由于C2嘲=0， 其中i=7，8，9，10，11，C2【12】-1，差分计算?7100000=26，这样就实现了 C2【7，8，9，10，11，一12】的变化。同理，223导致了c2【-24，-25，-26，27】的变化。第三章MD5的碰撞攻击192研究r(d2，a2，b1)部分，根据F函数的性质、d2、a2，可以得出：6=【-23，22，21，20，19，18，17，16，14，13，12，1

55、1】，在经过V6=c1+m6+m6+t6，异或差分 进行了变化，1l，6=216+214+213+212+211，即AW6=【16，14，13，12，11】。3经过循环左移17比特，AtlJ6<<<17=【一1，31，30，29，28】。Ac2继承了V6<<<17 的比特变化，其中，第1比特的差分进行了扩展了6个比特，使得c：【-6，5，4，3，2，1】， 其他比特没有进行扩展。4Ac2还继承了Ad2=231这部分的值，联合AtlJ6<<<17=【31，30，29，28】，这些部分共同构建了C232，31，30，29，28】。 详细解析第8步中各比特的由来：第8步在文献171中是个关键的步骤，控制好该步的差分对最终产生碰撞有着 重要的作用。该步的差分是由前7步差分共同作用产生的，即 (ac：，Ad：，Aa：，Ab。)一b：。为了控制好差分路径，使得经过第8步的运算以后，达 到b2t-b2【1，16，-17，18，19，20，一21，一24】的差分特性，必须控制好前面的c2，d2， a2，b。的值。前7步的运算为第8步提供了以下前提条件：