彩虹表是什么

彩虹表是一种预计算技术，通过存储密码和哈希值的对应关系，可以快速破解哈希密码。

使用彩虹表的原因

考虑一种情形：若攻击者获取到了网站中用户名-密码哈希值对应关系的文件，可有两种思路来获取明文密码：一是暴力破解，逐个尝试所有可能的密码，此法需要大量时间；二是预先生成 (pre-computation) 所有可能的密码-哈希值对照表并存储，破解时直接根据文件中的哈希值从表中查询对应的密码，此法需要大量空间——而彩虹表对两种方式进行了折衷，通过消耗一定时间进行预计算，换取空间节省，将二者都控制在可接受范围内。

彩虹表的构成与哈希链

给定哈希函数 $ H $、有限密码集 $ P $，需找到一种数据结构来存储预计算信息，使得已知一个哈希值 $ h $ 时，要么能在其中定位到使 $ H(p)=h $ 的 $ p $ 也即密码、要么确定 $ p $ 不在这些数据中——彩虹表就是满足这样条件的数据结构。

彩虹表由许多哈希链 (Hash chains) 组成，为此需要定义一个归约函数 $ R $，将哈希值 $ h $ 输入 $ R $ 后，能输出一个 $ p $（这个值不一定是某个用户的密码，但可以在预计算数据库内——约等于随机生成了一个 $ p $）。$ R $ 不是 $ H $ 的反函数，而可以是任意的。

哈希链的生成：首先拿一个随机的 $ p_i $，将其输入 $ H $，然后计算出 $ H(p_i) = h_i $，再将 $ h_i $ 输入 $ R $，然后计算出 $ R(hi) = p{i+1} $，以此类推。下面是一个长度为 $ k $ 的哈希链：

$$ p_1 \stackrel{H}{\longrightarrow} h_1 \stackrel{R}{\longrightarrow} p_2 \stackrel{H}{\longrightarrow} h_2 \stackrel{R}{\longrightarrow} … \stackrel{R}{\longrightarrow} p_k \stackrel{H}{\longrightarrow} h_k $$

存储时，只需存储起点 $ p_1 $ 和结尾 $ h_k $ （当然结尾也可以存 $ p $），就可通过计算知道其中都存了哪些 $ p $ 和 $ h $，而储存空间只需原来的 $ \dfrac{1}{k} $。花费一定时间，计算出一堆哈希链，就相当于得到了一个庞大的预计算字典。不过，也没必要或说不可能像前文的第二种思路那样计算出所有值，只需在可接受范围内尽可能多地计算即可。

实际中，哈希链的长度一般在数量级。一般不会自己去计算彩虹表（会花费很多时间），而大多去下载现成的（一般都在 100G 以上）。

$ k $ 越大，破解时间越长、彩虹表占用空间越小；$ k $ 越小，彩虹表越大，破解时间越短。

注意：通常没有足够时间计算出所有可能的密码，因此密码也可能不在彩虹表的任何一条哈希链中——彩虹表攻击不是 100% 有效！但 Elcomsoft 宣称能找到表中缺失的密码，并存储在一种叫 Thunder Tables 的结构中：Thunder Tables™ Explained | ElcomSoft blog

怎样使用彩虹表破解密码

假设我们拿到了一个哈希值 $ h_1 $，需找到它对应的明文密码 $ p $：

  1. 将这个 $ h_1 $ 作为一个哈希链的开头，依次计算下去；
  2. 直到发现算出的某个值和彩虹表中某条哈希链的结尾相同，则根据该哈希链的开头依次计算，重构出这条链；
  3. 若发现 $ h_1 $ 在该 match 到的哈希链中，则它前面的 $ p $ 就是要找的明文密码；若没有找到这样的组（误报），就继续计算 $ h_1 $ 开头的这条哈希链，直到 match 另一条链的末尾。

彩虹表攻击的优点：同一张彩虹表可以用于破解多个密码；比字典攻击快很多；节省大量时间。

问题：为什么 match 的链中可能不包含 $ h_1 $？——不同的 $ h $ 通过 $ R $ 函数可能会得到相同的 $ p $（$ R $ 不是一一映射），因此 match 到后面某个值反过来向前推，可能会推到不同的 $ h $ 上，整条链也就不同了。

哈希链的碰撞 (Flaws of simple chains)

多个密码可能具有相同的哈希值，因此两条不同的链也可能都在某个地方算到这个相同的值上去，且接下来的所有节点都会相同了（发生碰撞）——这将导致在付出了同样的计算代价之后并不能使表尽可能多的覆盖到密码；而且由于链的前部并没有整个保存，碰撞不可能被有效检测：

$$ p_1 \stackrel{H}{\longrightarrow} h_1 \stackrel{R}{\longrightarrow} p_2 \stackrel{H}{\longrightarrow} h_2 \stackrel{R}{\longrightarrow} p_3 \stackrel{H}{\longrightarrow} h_3 \stackrel{R}{\longrightarrow} p_4 \stackrel{H}{\longrightarrow}… $$

$$ p^{\prime}_1 \stackrel{H}{\longrightarrow} h^{\prime}_1 \stackrel{R}{\longrightarrow} p^{\prime}_2 \stackrel{H}{\longrightarrow} h^{\prime}_3 \stackrel{R}{\longrightarrow} p^{\prime}_4 \stackrel{H}{\longrightarrow} h_2 \stackrel{R}{\longrightarrow} p_3 \stackrel{H}{\longrightarrow} … $$

解决方法：由于重复链一般在每个表中所处位置不同，可在每个固定位置依次使用多个不同的 $ R $，来确保即使出现了一对相同输出，接下来通过的 $ R $ 也不同，因此下一个节点也不会相同了，从而避免了碰撞：

$$ p_1 \stackrel{H}{\longrightarrow} h_1 \stackrel{R_1}{\longrightarrow} p_2 \stackrel{H}{\longrightarrow} h_2 \stackrel{R_2}{\longrightarrow} p_3 \stackrel{H}{\longrightarrow} h_3 \stackrel{R_3}{\longrightarrow} … $$

彩虹表的关键是构造 $ R $ 函数，优秀的 $ R $ 函数要保证计算结果均匀分布，即避免出现相同的明文密码。若将不同的 $ R $ 函数用不同的颜色表示，众多哈希链就会像彩虹一样，从里到外呈现出颜色变化，即彩虹表名称的由来。

防守

最简单的方法是“加盐”：即向密码哈希函数中添加额外的随机数据，以增加密码哈希的安全性。盐是一个随机生成的字符串，与用户的密码组合在一起，然后进行哈希计算。

密码哈希函数将用户的密码和盐作为输入，生成一个固定长度的哈希值。通过添加盐，相同的密码在不同用户之间生成的哈希值也会不同，即使两个用户使用相同的密码，其哈希值也会有所区别。

除此之外还有许多进阶方法，本文暂不介绍。