MD5摘要算法的几种破解方法！

MD5 算法暴力破解的几种方法

前言

昨天微信群里又热闹了起来，我一看消息，原来是有人在讨论：“如果突然有一天 MD5 算法被破解了，可逆了怎么办？”

其中有些网友表示，这题我会。

“如果它被破解了，我 35 岁之后就有事干了”

“如果可逆了，全宇宙最强的压缩算法就诞生了，任意字节数据都可以压缩到128bits”

“根据摘要就能把论文全文推导出来，碉堡了”

...

群消息刷了很多，都在带薪摸鱼，却没人讨论，具体怎么破解。所以，今天我就来献丑一下，浅谈一下 MD5 怎么样“破解”，大家轻喷！

逆向是不可能逆向的

在正式介绍 MD5 “破解”的方法前，先说明一点：目前我们没办法把 MD5 字符串还原回对应的原文。道理很简单，任意长度的数据经过 MD5 处理后，所包含的信息量已经大大减少。要是可以还原的话，那 MD5 岂不是成为最强的压缩算法了？？

所以，目前所谓的“破解”指的就是“碰撞”。即找到一个原文，算出来的 MD5 码和已知的 MD5 码一样。接下来介绍一些常见的破解方法。

暴力碰撞：穷举法&字典法

小标题上写了两种方法：穷举法和字典法。但是我认为它们的本质是一样的，都是利用计算机的资源尝试碰撞已知的 MD5 码。这里就放在一起了。

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

只考虑大小写字母和数字，每一位有 62 种可能，那么 8 位密码的排列组合就是 62 的 8 次方，218340105584800，约等于二百万亿！

既然计算如此费时，能不能考虑「把计算结果以映射表的形式存放起来，一个萝卜一个坑」，一个原文对应着一个 MD5 码呢？可以呀！这就是传说中的“字典法”。将已知的 MD5 码查表，直接反查出原文。

字典法体现了算法设计的“以空间换时间”的思想。「缺点是比较耗费空间。不过现在硬盘的价格变得白菜价了，空间开销不算什么。」

所以，简单且常见的密码，如果用了 MD5 加密，会被暴力的很快。况且现在量子计算机要来了，等量子计算机发展到和我们现在的普通笔记本大小，MD5 被暴力的就更快了，说不定就是分分钟的事。

给大家推荐一个用字典法破解 MD5 的网站：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)，此时的哈希链表就是“彩虹表”。」

文字描述起来太过复杂，还是用图列举一个 demo。

这里再给大家推荐一个已经计算好的彩虹表：http://project-rainbowcrack.com/table.htm

差分攻击

上面介绍的穷举法、字典法和彩虹表法都是暴力破解，适用于任何的消息摘要算法。真正意义上 MD5 算法的破解，是 2004 年山东大学王小云教授提出的 MD5 碰撞方法。她所用到的方法正是差分攻击。

这种方法概括起来说是这样的：给定一个 1024 位的原文 M1，加上一个特定的常数得到的新的明文 M2。M1 和 M2 的 MD5 码是一样的。（这里大家可以去找具体的论文）这个特定的常数到底是怎么找出来的？笔者当时在查阅原始文献的时候也不清楚。因此后来的研究者开始对怎么样差分进行了各种各样的研究。具体的方法比较复杂，我就这里就不再赘述，班门弄斧了。

后记

其实还有一种破解 MD5 的方法——长度扩展攻击。不过这种方法是在一定条件下（破解加盐之后产生的 MD5 码）才能用的。这种方法由 MD5 分块计算的特性而来。

如果，我是说如果。你能逆转破解成功，你一定会获得图灵等计算机大奖。大大的解放数据存储能力，任何数据都可以用一段字符串表示。