本文目的

在我的上一篇文章《MD5算法，看这篇就够了》中，我描述了md5算法的基本步骤，今天跟大家分享一下破解md5的原理。参考文献在文末，有兴趣的读者可以读读。

符号

文本中出现诸如M0，M1，以粗体字母+非粗体数字组合的符号等同于公式中该字母和以该数字作为下标的符号。

MD5算法回顾

首先我们来大概回顾一下MD5算法。

1. 填充。将消息E的长度进行填充，使其满足对512取余为448。
2. 补充数据长度。将原消息以64位表示，并添加到填充的数据之后，我们得到M。
3. 初始化缓存器。A：01 23 45 67；B：89 ab dc ed；C：fe dc ba 98；D：76 54 32 10。A，B，C，D都是32位的缓存器，在下一步运算中使用。
4. 进行迭代处理。M的长度是512的整数倍（448+64），我们将数据M以512长度为单位进行划分，此时M=（M0,M1,M2....M(N-1)），在运算中我们将这512位用16个32位的数来表示。接下来，我们对M进行遍历，对其中的每一项进行四轮运算，每一轮都要进行16则计算，计算的结果缓存到A，B，C，D缓存器中，并对下一次迭代产生影响。
5. 输出。我们从A的低位字节开会，到D的高位字节结束，每一个都是32位，最终拼接的结果就是4*32 = 128位，这就是MD5计算的结果。

上述迭代的过程我们称之为杂凑运算。可以描述成这样：

公式中的Mi表示为M中下标为i的元素，H0是缓存器中的初始值（A，B，C，D），Hi表示第i-1轮中缓存器中的结果，四轮运算我们抽象成函数f。

差分攻击简介

哈希函数最重要的分析方法是差分攻击，同时也是分析分组密码最重要的方法之一。差分攻击大部分是使用异或运算的异或差分攻击，由Eli Biham和Adi Shamir在分析类似DES加密体系的安全性中提出的，他们描述差分密码分析是一种分析纯文本对（原文）中的特殊差异对产生的密码文本对的差异的影响的方法。

在本文中，我们使用整数模减（(A-B) mod C）来进行差分分析。

差分攻击原理

两个数之间的差我们表示为：

对于M=（M0,M1,M2,....,M(N-1)）和M'=（M0',M1',M2',....,M(N-1)'）。哈希函数的整个过程的差我们可以表示为：

在上式中，△H0表示初始值（A，B，C，D）之间的差，显然是0。△H表示最终两个消息之间的差，△Hi表示在第i次迭代之后结果的差，当然也是下次迭代的初始差值。我们的目标很简单，假如我们使得最终的结果△H=0的话，也就是M和M'的哈希结果是一样的，M和M'就产生了碰撞。

差分优化

要想使得碰撞发生，即△H为0，需要满足的充分条件多达290多条（N=2），分布在每一轮运算的计算上，附录中给出了表格。要想满足这些条件，提高碰撞的可能性，我们使用消息修改技术。有两种修改方式。

1、对于任意的消息块（Mi,Mi'）第一轮运算的非0“差”。

其中△R，第二个下标表示轮数。我们通过修改Mi的值，保证在第一轮运算中满足差分的条件。

2、使用多消息修改机制，我们不仅能保证第一轮运算满足充分条件，同时也能都大幅提高第二轮运算条件满足的几率。

MD5差分攻击

对于MD5的差分攻击，同其他哈希函数大同小异。这里我们攻击的目标是1024位M=（M0,M1）的消息体。我们的目的就是根据差分值计算M'=（M0',M1'）,使得MD5(M)=MD5(M')。

步骤描述如下：

1. 随机产生M0
2. 使用消息修改算法修改M0，使之尽量满足充分条件；
3. 如果所有的充分条件都满足，则计算MD5的输出并将其作为后半部分的链接变量，如果不满足，则回到第2步，重新随机选择；
4. 随机产生M1
5. 使用和前半部分相同的方法计算后半部分的输出。需要注意的是，后半部分计算使用的链接变量初始值为前半部分的输出

总结

该攻击方法只用于寻找产生碰撞的消息对，对于实际应用来说，满足差分的充分条件的几率很小。

参考文献

1. Xiaoyun Wang,Hongbo Yu,How to Break MD5 and Other Hash Functions
2. E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard
3. The MD5 Message-Digest Algorithm

附录

摘自王小云论文

摘自王小云论文

关注技术大白，带你阅读技术书籍，了解技术内幕！