彻底搞懂彩虹表的实现原理

悠悠 2023-02-26 02:06 5阅读 0赞

# 为什么要写这篇文章 #

鉴于今天摸索了一上午，终于搞清楚了彩虹表的实现原理，特此记录，以备后查。

# 什么是彩虹表 #

7788的术语我就不多说了，简而言之，就是一种破解md5或者sha1这种哈希散列算法的一种办法。

# 彩虹表的实现原理 #

在说彩虹表之前，先说说已经存在的几种破解类似md5这种哈希散列算法方法

## 方法一：暴力破解 ##

我们假设有一个明文123456通过md5加密后得到密文 `E10ADC3949BA59ABBE56E057F20F883E`，那么我们有了这段密文如何反推他的明文呢？我们假设我们知道他的明文是一个6位数的明文，暴力破解就是不停的算，先用111111进行md5看看得到多少，然后和密文比，发现不一样，然后用111112进行md5再和密文比，还是不一样，就这样一直循环，直到找到一个数n的密文也是 `E10ADC3949BA59ABBE56E057F20F883E`，那么就说明他的明文**可能**就是n.为什么说是可能呢？因为对于不同的数进行md5运算后可能会得到同样的密文。很明显这种方式的效率是十分低下的，每一个数我们都要进行一次md5运算然后再把结果和密文进行对比，众所周知，运算是需要时间的，尽管md5运算很快，但任然需要消耗计算机一定的性能。那么我们能不能先把所有可能的密文都算出来，然后放在一张表里，然后直接用我们需要找的密文去这张表里找呢？其实是可得，这种方式其实就是下面要说的查表法。

## 方法二：查表法 ##

把所有可能的密文都算出来，然后放在一张表里，表的数据结构类似如下

<table> 
 <thead> 
  <tr> 
   <th>明文</th> 
   <th>密文</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>C4CA4238A0B923820DCC509A6F75849B</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>C81E728D9D4C2F636F067F89CC14862C</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>ECCBC87E4B5CE2FE28308FD9F2A7BAF3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>A87FF679A2F3E71D9181A67B7542122C</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
 </tbody> 
</table>

然后我们要找某个密文对应的明文的时候，直接用这个明文去表里查询就完了。这个方式省略了每次都进行md5运算这个耗时的操作，确实会比较快，但相比你也已经想到了，我这个表的数据得多大才能涵盖所有的字母+数字+特殊符号的组合？的确如此，这种方式所得到的表数据量是非常惊人的，我们来看一组数据

> 对于14位的大小写加数字（先不算特殊字符了）组成的密码的集合有多大？自然就是（26\*2+10）^14 = 62^14 = 1.24 \* 1025，这个就约等于12亿亿亿，即使我们每纳秒可以校验一个p(一秒钟10亿次，目前PC做不到)，暴力破解法也大概需要4亿年；如果我们采用查表法，假定Hash的结果是128Bit即16字节的，光存放Hash（不存放明文P）就需要1026字节的存储空间。什么？现在硬盘很便宜？没错现在 1GB硬盘大概是五毛钱，那么按这个来算光存储这个Hash大概需要5亿亿人民币来买硬盘。

实际生活中大多数人的密码并不会有14位这么长，所以采用暴力破解法或者查表法具有一定的可行性，但对于强密码的破解，显而易见这两种方式都有点捉颈见肘，局限性很大。那么有没有更好的办法呢？彩虹表的出现就是为了解决这一问题。

## 方法三：彩虹表 ##

### 先构建一张表 ###

我们对于一个明文P，进行HASH算法H后得到了一个密文Q，可以进行如下表示

Q=H(P)

然后我们额外构建一个函数R（Reduce）。这个函数是Hash的伪逆运算，也就是：R函数的参数是Hash码，得到的是一个位数不定的密码，之所以说伪是因为得到的密码并不是最初的密码。那么表示为如下

P=R(Q)

这之后，就要开始一堆骚操作了  
我们先给定任意数P1，先进性一次H运算，得到Q1，即Q1=H(P1)。然后对Q1进行R运算得到P2，即P2=R(Q1)，再对P2进行H运算得到Q2，即Q2=H(P2)。…如此循环下去。假设循环得到n步长，我们就得到一条链，如下：

P1-H-Q1-R-P2-H-Q2-R-P3-H-Q3-R-P4-H-Q4-......-P(n-2)-H-Q(n-2)-R-P(n-1)-H-Q(n-1)-R-Pn

然后我们存储P1和Pn，其他的p都不存储，那么这就得到了一个类似于查表法的一张表，只不过他的数据量很明显要少了很多，少了n-2这么多。  
那么有了这个P1和Pn之后，我们如何进行破解呢？

### 破解过程 ###

比如我们拿到一个Hash码，我们先对hash做一次R运算得到一个P，

P=R(hash码)

将这个P跟存储Pn比较，如果P与Pn不相等，那么我们就对P做一次H-R运算，表示为如下

hash码2 = H(P)
    P2 = R(hash码2)

然后用P2继续和Pn比较，如果相等的话，因为我们这里只做了一次H-R的运算，说明这个明文就是倒数第二个P，也就是P(n-1),因为

P(n-1)-H-Q(n-1)-R-Pn

知道了他是P(n-1)，而又因为我们存储了P1的值，那么很容易通过P1得到P(n-1).也就得到了明文了。  
当然还有可能就是，这个hash码做了所有的H-R运算，依然不等于Pn. 那就说明我们这条HASH链并不能破解这个密文，那么就要转而去找其他的HASH链。所以从这里也可以看出，彩虹表破解成功率其实也并不是100%。但只要库的hash链的数据样本足够多，那么破解成功的概率应该是无限接近100%的。

彩虹表的根本原理就是组合了暴力法和查表法，并在这两者之中取得一个折中，用我们可以承受的时间和存储空间进行破解。当然这里只是讲述了最粗浅的原理，仔细想一下还有很多的问题，例如R的选择，Hash冲突的处理，如何选择p0来实现足够的覆盖，如何在有限资源下生成彩虹表等等。  
所以：严格来说，以上的这种算法并不能叫彩虹表，他被称为`预计算的哈希链集`.  
哈哈，是不是很失望，我都看到这里了你告诉这个不是彩虹表？别急，其实这个离彩虹表已经很近了，彩虹表也是基于这个做出了改进

### 彩虹表的改进点 ###

一下内容摘抄自 [知乎 Smallay 的答复][Smallay]  
**R的问题**  
在构造哈希链的时候，一个优秀的函数R功不可没。首先R需要能将值域限定在固定的范围——例如给定的长度范围、给定的字符取值范围等等——之内，否则的话，哈希链中大量的计算结果并不在可接受的取值范围内，一条链条无法对应多个明文，链条就失去了意义；其次R必须同哈希函数一样，尽量保证输出值在值域中的均匀分布，减少碰撞的概率。  
然而实际上，很难找到能满足这些需求的完美的R函数。当计算中发生碰撞时，就会出现如下的情况：  
![在这里插入图片描述][20200713182306598.png]  
图中加粗的部分，所涉及到的明文是完全重复的，因此这两条哈希链能解密的明文数量就远小于理论上的明文数2×k。不幸的是，由于集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。随着碰撞的增加，这样的重复链条会逐渐造成严重的冗余和浪费。  
**改进**  
对于这个问题，2003年提出的彩虹表算法进行了针对性的改进。它在各步的运算中，并不使用统一的R函数，而是分别使用R1…Rk共k个不同的R函数（下划线表示下标）。这样生成的哈希链集即被称为彩虹表。（在不同的运算位置使用不同的R函数，就像彩虹由内而外的不同位置上显示出不同的颜色一样。）这样一来，如果发生碰撞，通常会是下图的情况：  
![在这里插入图片描述][20200713182524533.png]  
不难发现，当两个链条发生碰撞的位置并非相同的序列位置时，后续的R函数的不一致使得链条的后续部分也不相同，从而最大程度地减小了链条中的重复节点，保证了链条的有效性。  
同时，如果在极端情况下，两个链条有1/k的概率在同一序列位置上发生碰撞，导致后续链条完全一致，这样的链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。  
彩虹表的使用比哈希链集稍微麻烦一些。首先，假设要破解的密文位于任一链条的k-1位置处，对其进行Rk运算，看是否能够在末节点中找到对应的值。如果找到，则可以如前所述，使用起节点验证其正确性。否则，需要继续假设密文位于k-2位置处，这时就需要进行Rk-1、H、Rk两步运算，然后在末节点中查找结果。如是反复，最不利条件下需要将密文进行完整的R1、H、…Rk运算后，才能得知密文是否存在于彩虹表之中。

# 如何获取彩虹表 #

彩虹表可以使用RainbowCrack或Cain来生成。表分割得越细，成功率就越高，生成的表体积也越大，所需时间也越长。但下载比生成快得多，有人做过测试，4核4GB内存的机器，生成2GB彩虹表，需要花费7天时间，而7天按2MB的带宽（256K/S左右）几乎可以下载48GB左右，效率明显要超过生成。当然，你要是有超级计算机群生成的话，也不妨自己生成。对于广大网络安全爱好者来说，还是直接下载来得靠谱！

Ophcrack彩虹表 官方下载地址：  
http://ophcrack.sourceforge.net/

120G彩虹表BT下载（这是种子文件，迅雷上有资源，如果是会员使用迅雷下载还是很快的，我8M带宽，下了3天左右下完了。）：  
http://www.ha97.com/code/tables.rar

# 彩虹表的防御 #

了解了彩虹表的原理，那么知道怎么防御彩虹表破解就简单了，很明显的是，如果我们的密码足够的复杂，比如我20位的密码以至于40位的密码，即时使用彩虹表也很难破解，但大多数人并不会采用这么长的密码，那么我们可以在密码后面加盐（salt）以增加密码的长度。

saltedhash(password) = hash(password+salt)

如果将用户密码后添加一段随机字符串，然后将随机字符串和散列后的哈希值存储在密码数据库中。彩虹表讲不得不计算出盐化后的密码，而盐化后的密码会大大增加散列前的长度，从而使密码集合过大而变的不可能生成的彩虹表。

部分内容摘抄自：  
http://www.ha97.com/4009.html  
https://blog.csdn.net/hit\_fredrick/article/details/40988543  
https://www.zhihu.com/question/19790488  
https://blog.csdn.net/linkedin\_21614133/article/details/43835635

[Smallay]: https://www.zhihu.com/question/19790488
[20200713182306598.png]: /images/20230209/7d6e2705d3734694a3ccab2ea3aea696.png
[20200713182524533.png]: https://img-blog.csdnimg.cn/20200713182524533.png