一、MD5 是什么

MD5 英文全称 Message-Digest Algorithm 5，翻译成中文是 消息摘要算法第五版，为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。

MD5 算法具有以下特点：

• 压缩性：任意长度的数据，算出的 MD5 值长度都是固定的（128 bit）。
• 易计算：从原数据计算出 MD5 值很容易。
• 抗修改：对原数据进行任何改动，哪怕只修改 1 个字节，所得到的 MD5 值都有很大区别。
• 抗碰撞：已知原数据和其 MD5 值，想找到一个具有相同 MD5 值的数据（即伪造数据）是非常困难的（极小碰撞概率）。

二、使用 MD5 存储密码

MD5 的用处太多了，数据完整性校验、数字签名、文件完整性检查、密码保存等等，这里以一个密码保存来简单描述一下。

2.1 无盐的 MD5

大型网站需要保存千千万万用户的密码，如果密码使用明文保存，万一哪天数据库被黑客攻破了，用户的密码就全泄露了。

如果数据库只保存用户密码的 MD5 消息摘要，那么即使黑客拿到了用户们的 MD5 消息摘要，也无法复原出用户的密码。

有同学会抗议，这个说法不对！黑客可以使用彩虹表将用户密码复原出，网站常用的密码一般也就 6~10 位，这个取值空间还是很好破解的。没错，但是我们可以通过加盐提高破解的难度。

2.2 加盐的 MD5

我们知道，如果直接对密码进行散列，那么黑客可以对通过获得这个密码散列值，然后通过查散列值字典（例如 MD5 密码破解网站），得到某用户的密码。

加盐可以一定程度上解决这一问题。当用户首次提供密码时（通常是注册时），由系统自动对这个密码追加盐，然后再散列。而当用户登录时，系统为用户提供的密码追加同样的盐，然后散列，再比较散列值，已确定密码是否正确。

这个盐值是由系统随机生成的，并且只有系统知道。这样，即便两个用户使用了同一个密码，由于系统为它们生成的盐值不同，他们的散列值也是不同的。即便黑客可以通过自己的密码和自己生成的散列值来找具有特定密码的用户，但这个几率太小了（密码和盐值都得和黑客使用的一样才行）。

那是不是加了盐值之后就绝对安全了呢？当然没有！黑客还是可以根据他们数据字典中的密码，加上我们泄露数据库中的盐值，然后散列，然后再匹配。但是由于我们的盐值是随机产生的，假如我们的用户数据表中有 30w 条数据，数据字典中有 600w 条数据，黑客如果想要完全覆盖的话，他们加上盐值后再散列的数据字典数据量就应该是 30w * 600w = 180000000w，一万八千亿啊，干坏事的成本太高了吧。但是如果只是想破解某个用户的密码的话，只需为这 600w 条数据加上盐值，然后散列匹配。可见加盐虽然大大提高了安全系数，但也并非绝对安全。

实际项目中，盐值不一定要加在最前面或最后面，也可以插在中间，也可以分开插入，也可以倒序，程序设计时可以灵活调整，都可以使破解的难度指数级增长。

三、彩虹表是什么

聊完 MD5，咱们再聊聊彩虹表。

彩虹表不是 “密码 ⇨ 明文” 的简单存储。要从 c = hash(m) 逆向得到原始明文 m，有三种办法：

• 暴力破解法：时间成本太高。
• 字典法：提前构建一个 “明文 ⇨ 密文” 对应关系的一个大型数据库，破解时通过密文直接反查明文。但存储一个这样的数据库，空间成本是惊人的。
• 构建彩虹表：在字典法的基础上改进，以时间换空间。是现在破解哈希函数常用的办法。

3.1 彩虹表的前身

既然存储所有的明文密码对需要的空间太大，密码学家们想出了一种以计算时间降低存储空间的办法，被称为 “预计算的哈希链集”。

假设这是一条 k = 2 的哈希链：

其中 H 函数 就是要破解的哈希函数。

约简函数（reduction function）R 函数 是构建这条链的时候定义的一个函数：它的值域和定义域与 H 函数相反。通过该函数可以将哈希值约简为一个与原文相同格式的值。

这条链是这样生成的：

存储的时候，不需要存储所有的节点，只需要存储每条链的头尾节点（这里是 aaa 和ccc）。

以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，可得到一张哈希链集。

预计算的哈希链集的使用

假设密文刚好是 4D5E6F ，首先对其进行一次 R 运算，得到 ccc，然后发现刚好命中了哈希链集中的（aaa, ccc）链条。可以确定其极大概率在这个链条中。于是从 aaa 开始重复哈希链的计算过程，发现 bbb 的哈希结果刚好是 4D5E6F，于是破解成功。

假设密文不是 4D5E6F 而是 1A2B3C ，第一次 R 运算后的结果并未在末节点中找到，则再重复一次 H 运算 + R 运算，这时又得到了末节点中的值 ccc。于是再从头开始运算，可知 aaa 的哈希结果刚好是 1A2B3C，破解成功。

如过密文重复了 k（=2）次之后，仍然没有在末节点中找到对应的值，则破解失败。

预计算的哈希链集的意义

对于一个长度为 k 的预计算的哈希链集，每次破解计算次数不超过 k，因此比暴力破解大大节约时间。同时每条链只保存起节点和末节点，储存空间只需约 1 / k，因而大大节约了空间。

R 函数存在的问题

要发挥预计算的哈希链集的作用，需要一个分布均匀的 R 函数。当出现碰撞时，就会出现下面这种情况

由于两条链出现了重复。这两条哈希链能解密的明文数量就远小于理论上的明文数（2 * k）。由于集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。

3.2 彩虹表

彩虹表的出现，针对性的解决了 R 函数导致的链重复问题：它在各步的运算中，并不使用统一的 R 函数，而是分别使用 R1…Rk 一共 k 个不同的 R 函数。

这样一来，即使发生碰撞，通常会是下面的情况：

即使在极端情况下，两个链条在同一序列位置上发生碰撞，导致后续链条完全一致，这样的链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。

彩虹表的使用

首先，假设要破解的密文位于某一链条的 k - 1 位置处，对其进行 Rk 运算，看是否能够在末节点中找到对应的值。如果找到，则可以如前所述，使用起节点验证其正确性。

否则，继续假设密文位于 k - 2 位置处，这时就需要进行 Rk - 1、H、Rk 两步运算，然后在末节点中查找结果。

如此反复，在最不利条件下需要将密文进行完整的 R1、H、…Rk 运算后，才能得知密文是否存在于彩虹表之中。

彩虹表中时间、空间的平衡

哈希链集的最大计算次数为 k，平均计算次数为 k / 2；彩虹表的最大计算次数为 1 + 2 + …k = k(k - 1) / 2，平均计算次数为 [(k + 2) * (k + 1)] / 6。

可见，要解相同个数的明文，彩虹表的代价会高于哈希链集。

无论哈希链集还是彩虹表，当 k 越大时，破解时间就越长，但彩虹表所占用的空间就越小；相反，当 k 越小时，彩虹表本身就越大，相应的破解时间就越短。

3.3 为什么加盐哈希可以抵御彩虹表

彩虹表在生成的过程中，针对的是特定的 H 函数，H 函数如果发生了改变，则已有的彩虹表数据就完全无法使用。

如果每个用户都用一个不同的盐值，那么每个用户的 H 函数都不同，则必须要为每个用户都生成一个不同的彩虹表。大大提高了破解难度。

总结：奇妙的比喻

最后以一个奇妙的比喻来总结该文章：

如果将 MD5 哈希后的密文比作一把锁，暴力破解的方法就是现场制作各种各样不同齿形的钥匙，再来尝试能否开锁，这样耗时无疑很长很长。。。

我以前错误理解的 “彩虹表”，是事先制作好所有齿形的钥匙，全部拿过来尝试开锁，这样虽然省去了制作钥匙的时间，但是后来发现这些钥匙实在是太多了，没法全部带在身上。

而真正的彩虹表，是将钥匙按照某种规律进行分组，每组钥匙中只需要带最有特点的一个，当发现某个 “特征钥匙” 差一点就能开锁了，则当场对该钥匙进行简单的打磨，直到能开锁为止。这种方法是既省力又省时的。