md5碰撞介绍及工具，并对百度 盘进行碰撞

• 前言
• • 什么是MD5
  • 什么是MD5碰撞
• md5碰撞
• • 常见的碰撞法
  • 差分攻击
  • 构造前缀碰撞法
  • • 快速 MD5 碰撞生成器使用方法
• 百度 盘md5碰撞攻击
• 总结
• 参考

前言

什么是MD5

MD5信息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，对于任意的输入，可以产生出一个128位（16字节）的散列值（hash value），通过对比这个散列值确保信息完整一致。

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。MD5就是一种散列函数，它不能称作加密算法，也不是压缩算法，因为不能够通过MD5值得到原来的输入。

MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。打个比方： 每个人的的指纹独一无二，这是公安机关鉴别罪犯身份的方法之一；与之类似，MD5就可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。

我们常常在某些下载站点的信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用某些软件计算出其MD5值，与给定的MD5值比较是否相等，以确保我们获得的文件与该站点提供的文件为同一文件。

另外，在百度 盘里，也用到了md5，它的“秒传”就是通过md5来实现的。在上传大文件前计算md5值，通过判断数据库中是否已经存在一个文件和要上传的文件有相同的md5值，来判断数据库中是否已经保存了这个大文件。如果已经保存则直接添加一个链接即可，不用再上传文件。Onedrive则是直接上传，不判断（应该是这样）。

MD5算法的特点：

1. 输入任意长度的信息，经过摘要处理，输出为128位的信息。（数字指纹）
2. 不同输入产生不同的结果，（绝大部分情况下，如果不同的输入能产生相同的结果就是“碰撞”）
3. 根据128位的输出结果不可能反推出输入的信息（不可逆）

MD5算法作用：

1. 防止数据被篡改（比如传输一个文件，并传输它的md5值，接收方可以对收到的文件进行md5计算后比较和发送过来的md5值是否一样，不一样说明不是同一个文件）
2. 防止直接显示明文。（比如用在数据库存储密码，只需比较输入密码的md5值和数据库里的md5值是否相同，而不用传输明文；但数据库即使采用md5存储密码也是有可能出现安全漏洞的，比如计算常用密码的md5值，然后比较数据库中是否有同样的项）
3. 数字签名（因为难以由md5值得到原来的值，所以可以通过给出原来的值证明我确实是我）

MD5算法的原理可简要的叙述为：MD5码以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

MD5 上有很多在线计算 站，也有很多软件附带，这里只列出一个：http://www.metools.info/other/o21.html

什么是MD5碰撞

前面提到：散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以对于一个散列值可以找到多个输入使得它们的散列值相同。
一个安全的摘要算法在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的；其二是找一个输出，能得到给定的输入在计算上是不可行的，即不可从结果推导出它的初始状态。

“md5碰撞”，即对一个确定的md5值，找到一个输入，使得计算出的MD5值和之前确定的md5值一样。

md5碰撞

简而言之就是：先得出一个字符串的MD5值，再根据这个值，逆算出另外一个不同的字符串——但是它们的MD5值是一致的。

常见的碰撞法

¹
暴力碰撞：穷举法、字典法
利用计算机的资源尝试碰撞已知的MD5码。

穷举法就是不停地尝试各种字符的排列组合，看哪一个组合的MD5码能对上。缺点是太耗费时间。举个例子，假设我们要破解一个6位大小写字母和数字混合的密码，那么一共有 (26 + 26 + 10) ^ 6 种组合。这个数的大小超过500亿。

字典法就是把计算结果以映射表的形式存放起来，一个原文对应着一个MD5值。将已知的MD5码查表，就可直接反查出原文。字典法体现了算法设计的“以空间换时间”的思想。缺点是比较耗费空间，而且实际上还是要穷举一遍所有的输入，只不过把穷举的结果存了起来。

一个用字典法破解MD5、SHA1的 站：https://www.cmd5.com/password.aspx

时间和空间的折中：哈希链表 / 彩虹表法
如果说穷举法太耗费时间，字典法太耗费存储空间的话，我们能不能考虑在时间消耗和空间消耗之间折中呢可以考虑用链表将一系列有意义的原文和MD5码串起来。

要构造这样的链表，我们需要两个函数：哈希函数H(x)和衰减函数（reduction function）R(x)。哈希函数可以是MD5，也可以是其他的消息摘要算法。H(x)的值域是R(x)的定义域，R(x)的值域是H(x)的定义域。R(x)不是H(x)的反函数。

将一个原文不停地使用H(x)和R(x)交替进行运算k次，再将原文本身和运算结果以链表的形式串接起来，就可以得到结点个数为2k+1的链表。实际存放的时候只存放首端和末端两个原文即可。这种链表叫做“哈希链表”，体现了算法设计的“时空权衡”（Space and Time Tradeoffs）。

举个例子，假设原文s=abcabc，经过2次交替运算，得到以下的链表：

abcabc->H(x)->3C8B0D7A->R(x)->eopmca->H(x)->7E9F216C->R(x)->rapper

以上数据均为举例编造的，仅为说明原理使用。那我们存放这个链表的时候，只需要记录abcabc和rapper两个原文即可。

假设我们要破解的摘要值（哈希链表的H(x)不一定是MD5算法，这里用更准确的说法代替MD5码）是7E9F216C，经过R(x)运算得到rapper，说明我们要寻找的原文就在以rapper为末端的哈希链表中。从首端开始经过多次运算，我们发现eopmca的摘要值就是7E9F216C。于是就反查出7E9F216C对应的原文是eopmca。

如果在生成哈希链表的时候依次使用多个不一样的R(x)，此时的哈希链表就是“彩虹表”。

已经计算好的彩虹表：http://project-rainbowcrack.com/table.htm

差分攻击

上面介绍的穷举法、字典法和彩虹表法都是暴力破解，适用于任何的消息摘要算法。真正意义上MD5算法的破解，是2004年山东大学王小云教授提出的MD5碰撞方法，她能够在短短几分钟内找出两个不同的字符串且它们的md5值相同。所用到的方法正是差分攻击。

这种方法概括起来说是这样的：给定一个1024位的原文M1，加上一个特定的常数得到的新的明文M2。M1和M2的MD5码是一样的。真正要解释原理请参见王小云的论文²，在论文里提出了许多个充分条件，一步步找出满足这些条件的字符串就有很大概率产生碰撞。论文我已经下载下来放在资源区里共享，无需积分。

构造前缀碰撞法

如果仅仅是能快速找到两个不同的字符串使得它们的md5值相同，这对安全性的损害其实还不怎么大，因为构造的字符串有意义的概率很低。真正使得md5彻底退出舞台的是对王小云碰撞方法的改进版本：构造前缀碰撞法，由密码学家：Marc Stevens等人提出（他们的论文³我也放在了资源区）。在他们的论文里还对X.509格式证书进行了碰撞

在他们的 站上给出了两个程序，它们的MD5一致，却又都能正常运行，并且可以做完全不同的事情。而使用的计算机不过是一台 Sony PS3，且仅用了不到两天。
http://www.win.tue.nl/hashclash/SoftIntCodeSign/HelloWorld-colliding.exe
http://www.win.tue.nl/hashclash/SoftIntCodeSign/GoodbyeWorld-colliding.exe
这两个程序会在屏幕上打印出不同的字符，但是它们的MD5都是一致的。

这几位密码学家编写的“快速 MD5 碰撞生成器”： http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
源代码：http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
已将生成器程序和源代码放在资源区里，有需要自取。
这个生成器需要一个输入来生成两个md5相同的文件，输入可以是可执行文件，还可是pdf文档等，生成的两个文件都可以打开或执行，使用方法见下：

快速 MD5 碰撞生成器使用方法

打开cmd控制台，到fastcoll程序所在的目录，运行fastcoll程序，运行时添加 -p 参数，参数后跟要构造的原文件的文件名，会生成两个功能和原文件一样且md5也一样的文件。与输入的文件的区别是：生成的两个文件后方跟了一堆乱码后缀，但执行或读取程序时，文件格式一般都在最前面，这也是为什么生成的文件还能正常执行或读取的原因。
具体过程可参考⁴：https://www.cnblogs.com/foyler/archive/2008/09/30/1302530.html
另外，扩展内容参考⁵：https://blog.csdn.net/jiang314/article/details/97367187

百度 盘md5碰撞攻击

用生成器生成两个md5相同而内容不同的较大文件（可用别的哈希函数验证内容不同，如SHA1），先上传一个，再上传另一个，会发现后一个上传时是使用的“秒传”。假如构造了一个恶意程序，并与某些软件碰撞成相同的md5值，在其他人上传前上传到百度 盘，那么别人下载下来的都将是构造的恶意程序。操作很简单，这里就不放图了。

总结

简单了解md5碰撞，并利用现成工具实现一次简单的碰撞攻击。

参考

1. https://zhuanlan.zhihu.com/p/121492822 ??

2. 【Collisions for Hash FunctionsMD4, MD5, HAVAL-128 and RIPEMD】Xiaoyun Wang, Dengguo Feng, Xuejia Lai3, Hongbo Yu
   【How to Break MD5 and Other Hash Functions】Xiaoyun Wang and Hongbo Yu ??

3. 【Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities】Marc Stevens, Arjen Lenstra, and Benne de Weger
   【Fast Collision Attack on MD5】Marc Stevens ??

4. https://www.cnblogs.com/foyler/archive/2008/09/30/1302530.html ??

5. https://blog.csdn.net/jiang314/article/details/97367187 ??