MD5破解的几种方法

前言

最近发现自己一个多礼拜没写东西了，想写点什么保持手感，也顺便完成自己之前立的要写MD5破解的flag。今天就来谈一下MD5怎么样破解。

逆向是不可能逆向的

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

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

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

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

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

既然计算如此费时，能不能考虑把计算结果以映射表的形式存放起来，一个萝卜一个坑，一个原文对应着一个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)，此时的哈希链表就是彩虹表。

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

差分攻击

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

这种方法概括起来说是这样的：给定一个1024位的原文M1，加上一个特定的常数得到的新的明文M2。M1和M2的MD5码是一样的。（出处及具体操作见参考文献[1]）这个特定的常数到底是怎么找出来的？笔者当时在查阅原始文献的时候也不清楚。因此后来的研究者开始对怎么样差分进行了各种各样的研究。这里就不再赘述。

后记

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

呼~终于写完啦。希望这篇一千多字的小短文能给自己带来奇怪的知识增加了！的感觉。

参考文献

[1] Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Xiaoyun Wang,Dengguo Feng,Xuejia Lai,et al. Rump Session of Crypto’04 E-print . 2004