彩虹表

彩虹表

彩虹表（Rainbow Table）是一种破解哈希算法的技术，是一款跨平台密码破解器，主要可以破解MD5、HASH等多种密码。它的性能非常让人震惊，在一台普通PC上辅以NVidia CUDA技术，对于NTLM算法可以达到最高每秒103,820,000,000次明文尝试（超过一千亿次），对于广泛使用的MD5也接近一千亿次。更神奇的是，彩虹表技术并非针对某种哈希算法的漏洞进行攻击，而是类似暴力破解，对于任何哈希算法都有效。

彩虹表原理

这几乎是令人难以置信的，Roger迫不及待的去看了 http://www.project-rainbowcrack.com 所介绍的原理。这其实已经不是新的技术了，但是很遗憾的是，搜索“彩虹表原理”出来的文章对彩虹表原理的介绍都有不太正确，Roger就在这里简单的介绍一下，主要参考的是Wiki上的这篇 http://en.wikipedia.org/wiki/Rainbow_tables，英文好的可以去看这篇论文http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf。

我们先来做点科普，哈希（Hash）算法就是单向散列算法，它把某个较大的集合P映射到另一个较小的集合Q中，假如这个算法叫H，那么就有Q = H（P）。对于P中任何一个值p都有唯一确定的q与之对应，但是一个q可以对应多个p。作为一个有用的Hash算法，H还应该满足：H(p)速度比较快； 给出一个q，很难算出一个p满足q = H(p)；给出一个p1，很难算出一个不等于p1的p2使得 H(p1)=H(p2)。正因为有这样的特性，Hash算法经常被用来保存密码————这样不会泄露密码明文，又可以校验输入的密码是否正确。常用的 Hash算法有MD5、SHA1等。

破解Hash的任务就是，对于给出的一个q，反算出一个p来满足q = H(p)。通常我们能想到的两种办法，一种就是暴力破解法，把P中的每一个p都算一下H(p)，直到结果等于q；另一种办法是查表法，搞一个很大的数据 库，把每个p和对应的q都记录下来，按q做一下索引，到时候查一下就知道了。这两种办法理论上都是可以的，但是前一种可能需要海量的时间，后一种需要海量 的存储空间，以至于以目前的人类资源无法实现。

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

也正因为如此，我们一直都认为Hash是足够安全的，十几位的密码也是强度足够的，直到彩虹表的出现。现在我们来看看彩虹表是怎么干的。

彩虹表的根本原理就是组合了暴力法和查表法，并在这两者之中取得一个折中，用我们可以承受的时间和存储空间进行破解。它的做法是，对于一个Q = H（P），建立另一个算法R使得 P = R(Q)，然后对于一个p，这样进行计算：

p0 -H-> q1 -R->p1 -H-> q2 -R->p2 -H-> q3 -R->p3  … -H-> q(n-1) -R->p(n-1) -H-> qn -R->pn

简单的说，就是把q用H、R依次迭代运算，最后得到pn，n可能比较大。最后我们把p0和pn都存储下来，把其他的结果都丢弃。然后用不同的p0代入计算，得到多个这样的p的对子。

我们在做破解的时候，给出了一个q，我们来寻找p。我们先把q做一次R运算得到一个值例如叫c1，然后把c1和每一个p对的最后一个做比较，假如和某一个 pn相等，那么有可能这个pn所对应的p(n-1)就是我们在追寻的q，为了验证我们把pn对应的p0再做一次链式计算，比对qn是否就是给出的q，如果 是，很明显p(n-1)就是我们在追寻的p，因为 p(n-1) -H-> qn。如果不是就继续寻找直到遍历所有的q0qn对。

事情还刚刚开始，我们再算q -R-> c1 -H-> -R-> c2，再比对c2是否是qn，如果是，那么p(n-2)就可能是p；再算c3、c4直到c（n-1），不知道这样说你明白了吗？

总的来说，就是用一个p0pn对来存储了一个链子的数据，如果n很大，就可以大大减小了存储的空间。这样带来的问题是必须做n次比对，时间更长，但是我们不需要瞬间破解，等待几秒乃至几天破解一个密码都是可以接受的。

当然这里只是讲述了最粗浅的原理，仔细想一下还有很多的问题，例如R的选择，Hash冲突的处理，如何选择p0来实现足够的覆盖，如何在有限资源下生成彩虹表等等。对这些感兴趣的可以去看看RainbowCrack的源码 http://www.project-rainbowcrack.com

原理参考：

• 论文：https://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf
• 维基：http://en.wikipedia.org/wiki/Rainbow_table

获得彩虹表

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

RainbowCrack下载地址： http://project-rainbowcrack.com/table.htm

Ophcrack彩虹表 官方下载地址：

http://ophcrack.sourceforge.net/tables.php

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

http://www.ha97.com/code/tables.rar

彩虹表的使用

彩虹表工具很多，常用到的彩虹表工具有Ophcrack、rcracki_mt、Cain等，主流的彩虹表有以下三种。

Free Rainbow Tables

官方网址：https://freerainbowtables.com/

镜像下载：http://tbhost.eu/rt.php

提供了多种类型的彩虹表下载，LM、NTLM、MD5、SHA1等。千万别把人家法语字符的表也下了，对国人来说，几乎没什么用，不过如果你有特殊需要，那就下吧……这里提供的都是.rti格式的，有别于传统的.ri格式，.rti比.rt的多了一个目录.index文件，据说遍列速度比.rt的更快（未曾对比过，无法确定是否属实）。

比较新的，用的索引和压缩，所以速度更快，体积更小，而且支持分布式破解。

支持HASH类型：LM，MD5，NTLM，SHA1，HALFLMCHALL

网上有已经生成好的表可供下载，真是造福于民。

扩展名：rti

Ophcrack

官网网址：http://ophcrack.sourceforge.net/

最常用的，界面友好，与众不同，压缩储存，有自己独特的彩虹表结构，还有Live CD。

支持的HASH类型：LM，NTLM

扩展名：乱七八糟的。

高级的表要花钱买，免费的表有（推荐只下2和5，要求高的可以下载3和5）：

1、XP free（LM表：包含大小写+数字）380MB（官网免费下载）

2、XP free fast（和前一个一样，但是速度更快）703MB（官网免费下载）

3、XP special（LM表：大小写+数字+所有符号包括空格）7.5G

4、Vista free （NTLM表：包含常用密码）461MB（官网免费下载）

5、Vista special（NTLM表：包含6位的全部可打印字符，7位的大小写字母数字，8位的小写和数字）8G

RainbowCrack

官网网址：http://project-rainbowcrack.com/table.htm

通用的，一般的破解软件如saminside都支持，命令行界面，黑客的最爱，支持CUDA。

可以自己生成表，不要钱，传说中的120G就来自于此。

支持HASH类型：LM, NTLM, MD5, SHA1, MYSQLSHA1, HALFLMCHALL, NTLMCHALL.

扩展名：rt

最小彩虹表是最基本的字母数字表，就这样它的大小就有388MB，这是Ophcrack启动盘默认的表，该表可以在11分钟内破解所有可能14位数字字母密码组合中的99.9%。国内有比较流行的传说中的120G的彩虹表，国外还有几T的海量彩虹表。win2003及以前的windows操作系统的密码采用的LM算法加密，而Vista、Win7、Win2008/R2采用的是NTLM，NTLM比LM安全得多。

LM和NTLM详解：

1、话说在远古时期，DES当道。微软在考虑9X系统口令加密的时候就自然地采用了国家标准DES一次加密8字节，留一位校检，还剩7字节（下文有解释）， 也就是LM（Lan Manage）的核心。

2、那有人要问了，万一我的口令是8位怎么办呢？不用怕，微软的程序员很“聪明”：先把前7位加密，后一位补6个0，再当7位一起加密不就可以了吗，结果就真的这么做了。

3、这就导致破解LM密码只需7位一分割，然后再逐块破解，这大大减低了破解的难度。因为最后一块往往不够7位，一般瞬间即可得出结果。也就是7位和13位的密码，在破解者眼里几乎是一样的，因为13位的后6位很快就能破解出来，而且可以根据后6位猜测出前7位的密码，这就是为什么我们破解XP和2003密码很快的原因，因为他们都使用了LM加密方式。

4、由于LM的种种不安全性，微软在设计NT系列操作系统时采用了新的口令存储手段，即NTLM技术（New Technology Lan Manage），采用MD4+RSA存储，立马安全性要高很多。但是为了保证兼容性，直到2003微软仍然保持着LM的加密方式，也就是在2000、2003和XP中，我们的口令同时保存了两份，一份LM一份NTLM，我们仍然可以通过LM破解2003的口令。

5、在Vista和2008、Win7中，微软终于下定决心对LM斩草除根，只留下NTLM，破解难度增大。

6、回到彩虹表，由于LM最多只有7位，所以它的彩虹表很小。而NTLM用了散列函数，所以理论上口令是可以无限长的，所以NTLM的彩虹表往往很大，120G肯定是不够完成所有可打印字符的，最大的彩虹表已经是T量级了。

LM和NTLM验证机制：http://www.nsfocus.net/index.php?act=magazine&do=view&mid=1665

某人用彩虹表测试破解MD5的小结：

ophcrack的表不支持破解md5，具体讲.rt .rtc .rti格式的，只需对比一组数据就可以。同样是破解12位的纯数字密码：

.rt的需要20GB .rtc的需要8.75GB .rti的需要1.67+1.67+1.68+1.71=6.72GB

明显是.rti的小，但是我试过，我下了上面.rti格式破解12位的6.72GB的表中的1.67GB，其破解效果很让我惊讶，我本以为纯数字的破解出来的可能性是四分之一，因为我只下了4个表中的一个，我只下了那1.67GB，但我试着破解了几个12位数字加密的32位md5，结果大多数都能跑出来，很少有跑不出的，汗。但当我惊喜时发现他并不支持破解16位的md5，然后去那国外的官方论坛去逛了逛，才发现这并不支持破解16位的md5。原来老外不来16位这一套，但我们国内的网站用16位的md5占绝大多数，所以入侵时大部分得到的是16位的MD5密码，而老外的就不来16位的，郁闷。

Ophcrack文档描述了它所能使用的彩虹表之间的差异：

字母数字表 10k 388MB 包含所有字母数字混合密码中99.9%的LanManager表。这些都是用大小写字母和数字组成的密码（大约800亿组合）。

由于LanManager哈希表将密码截成每份7个字符的两份，我们就可以用该表破解长度在1到14之间的密码。由于LanManager哈希表也是不区分大小写的，该表中的800亿的组合就相当于12*10的11次方（或者2的83次方）个密码。

字母数字表 5k 720MB 包含所有字母数字组合的密码中99.9%的LanManager表。但是，由于表变成2倍大，如果你的计算机有1GB以上的RAM空间的话，它的破解速度是前一个的4倍。

扩展表 7.5GB 包含最长14个大小写字母、数字以及下列33个特殊字符（!”#$%&’()*+,-./:;?@[]^_`{|} ~）组成的密码中96%的LanManager表。该表中大约有7兆的组合，5*10的12次方（或者2的92次方）密码。

NT 8.5 GB 我们可以使用该表来破解计算机上的NT哈希表，这是LanManager 哈希表所做不到的。该表包含了用如下字符组成的可能密码组合的90%：

• 最高6位字符由大小写字母、数字以及33个特殊字符（同上面列举的一样）
• 7位的大小写字母及数字
• 8位的小写字母及数字

该表包含7兆种组合，对应7兆的密码（NT哈希表不存在LanManager哈希表的弱点）。

注意：所有这些彩虹表都有其特定适用的密码长度和字母组合。太长的密码（如数十位），或者包含表中没有的字符，那么用彩虹表就无法破解。

---

手动生成彩虹表破解密码

大家都在说MD5用于加密不安全！不安全！！不安全！！！那到底是有多不安全，怎么个不安全法呢？

在线MD5破解

目前网上有许多在线的md5以及其他hash破解网站，部分免费,百度一下即可。

彩虹表目的就是破解Hash：

“破解Hash的任务就是，对于给出的一个q，反算出一个p来满足q = H§。通常我们能想到的两种办法，一种就是暴力破解法，把P中的每一个p都算一下H§，直到结果等于q；另一种办法是查表法，搞一个很大的数据 库，把每个p和对应的q都记录下来，按q做一下索引，到时候查一下就知道了。这两种办法理论上都是可以的，但是前一种可能需要海量的时间，后一种需要海量 的存储空间，以至于以目前的人类资源无法实现。”

所以为了平衡了时间和空间，彩虹表产生了，一组包含明文与密文的hash链表。使得解密的时间和空间可以承受。

使用的版本RainbowCrack版本为1.7

工具下载地址为：http://project-rainbowcrack.com/

下载完成之后，解压，文件解压结果如下。

解压文件目录作用

文件	作用
rtgen.exe	生成彩虹表的执行文件
rtsort.exe	给彩虹表排序文件
rcrack.exe	执行解密的文件
rt2rtc.exe	将后缀是rt的文件转化为rtc文件
rtc2rt.exe	将后缀是rtc的文件转化为rt文件
charset.txt	这个文件是我们的字符集对照表文件(解密的类型)
group.txt	-这是组文件.将几个彩虹表组合起来

下面的这些都是文件是命令行和图形化界面的执行文件

执行根目录下大部分exe文件都会闪退。

基本步骤：

生成彩虹表（rtgen）——> 排序（rtsort）——> 破解（rcrack）

生成彩虹表可以用以下命令：

rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index

翻译如下：
rtgen 哈希类型 字符范围 最小位数 最大位数 表索引 链长度 链数量 索引块

哈希类型：LM,HTLM,MD5,SHA1,SHA256，几种常见HASH

其中有两个参数不太好理解：table_index和part_index。

表格生成参数隐式确定了许多彩虹表格特征：

生成彩虹表

彩虹桥能够解密的密码越复杂它所占磁盘空间就越多，如果只是想在自己电脑上测试一下，就生成一个小一点的.。

我们生成一个只能解密md5的密码位数为4位(必须是4位)的纯数字的彩虹表，下面这个是我生成的命令。

rtgen md5 numeric 4 4 0 3000 400000  0 

如下图:

生成的彩虹表很小只有6.1M，几十秒就完成了彩虹表生成，在输入完这条命令后也可以在命令行中看到我们设置的一些相关信息。

第二行的 md5_numeric#4-4_0_3000*400000_0.rt 就是我们生成的彩虹表文件，这个文件就存储在当前命令行执行的目录下。

彩虹表的排序

彩虹表是一串彩虹链。每条彩虹链都有一个起点和一个终点。rtsort程序通过终点对彩虹链进行排序，使二进制搜索成为可能。

运行以下命令对当前目录中的所有.rt彩虹表进行排序：

rtsort . 

切勿中断rtsort程序，否则被分类的彩虹表可能会被损坏。

如果可用内存大小小于正在排序的彩虹表的大小，则需要与彩虹表大小一样大的临时硬盘空间来存储中间结果。

我们生成的这表太小，所以瞬间就完成了排序。

解密

随便在网上搜一下在线md5加密，随表加密一个4位的数字，将加密完的结果拿过来，我们执行解密工作.。

rainbowCrack 解密的md5必须是32位的。(其实16位就是 32位去掉前8位和后8位字符)

下面这些是官方给出的集中解密格式.。

一般使用Helvetica Neue

假设彩虹表位于目录c：\ rt中。

破解单个哈希：

rcrack c:\rt -h fcea920f7412b5da7be0cf42b8c93759 
rcrack_cuda c:\rt -h fcea920f7412b5da7be0cf42b8c93759 
rcrack_cl c:\rt -h fcea920f7412b5da7be0cf42b8c93759

为了破解多个哈希：

rcrack c:\rt -l hash_list_file 
rcrack_cuda c:\rt -l hash_list_file 
rcrack_cl c:\rt -l hash_list_file

在上面的例子中，hash_list_file是一个文本文件，每个散列在一行中。

在多个目录中查找彩虹表格：

rcrack c:\rt1 c:\rt2 -l hash_list_file 
rcrack_cuda c:\rt1 c:\rt2 -l hash_list_file 
rcrack_cl c:\rt1 c:\rt2 -l hash_list_file 

在上面的例子中，rcrack / rcrack_cuda / rcrack_cl程序将按顺序在c：\ rt1和c：\ rt2目录中查找彩虹表。

我在使用window命令行的时候发现，这里面也有一种方式，我用的就是这种方式。(具体如下所示)在官网出现了三个命令行工具，这个应该是根据我们电脑的GPU区分的，如果我们GPU是NVIDIA(英伟达的)我们就可以用rcrack_cuda.exe。

我用的是rcrack.exe，在命令行中输入 rcrack.exe

我在解密是输入一个2342的md5加密值 2321994D85D661D792223F647000C65F

命令如下。

rcrack.exe . -h 2321994D85D661D792223F647000C65F

解密结果如下，成功的解密出了。

整个过程就完成了。

图形化界面的形式解密结果

图像化界面的简单实用，(以md5为例)

根据自己的GPU来使用相同的exe文件。当然rcrack_gui.exe 是可以什么GPU都能使用的。

直接在根目录点击rcrack_gui.exe，打开如下图所示

在File中Add Hashes中添加md5密文，每一行输入一组密文.。

也可点击Load Hashes from File 将一个有md5密文的文件引入进来和Add Hashes效果一样。(文件需要一行只能有一组md5密文)

点击 Rainbow Table中的 Search Rainbow tables选择需要用到的彩虹表，我们可以用我们刚刚生成的md5_numeric#4-4_0_3000x400000_0.rt选中之后将自动的解密。

菜单栏中的Edit中Delete all Hashes 可以删除所有刚才添加的md5密文

Edit 中的Clear Messages 可以删除主界面下方所有解密的具体信息

彩虹表生成例子

现在，我们以10位纯数字为例来生成自己的彩虹表，并可以权衡破解速度和存储空间。

# 生成一个包含1~10位数字，链长128，链数67108864 的彩虹表
./rtgen md5 numeric 1 10 1 128 67108864 0

# 对生成的彩虹表进行排序
./rtsort md5_numeric#1-10_1_128x67108864_0.rt

大小说明：链数 67108864 * 16byte = 1GB，因此生成的彩虹表（md5_numeric#1-10_1_128x67108864_0.rt）的大小为 1GB。

其他说明：

• 彩虹表的生成需要非常强的计算能力，可以使用多核CPU或GPU来提高速度；
• 生成上面的使用的彩虹表（一个），在24核60G服务器耗时约1.5min（CPU使用率 2300%）；4核8G渣渣开发机耗时10min（CPU使用率390%）；
• 本次测试中暂时未发现内存大小对速度性能造成的影响；

小试牛刀

我们以一批随机的10位数字ID进行测试，样本数据共59293个，进行破解：

# wax_uid.txt 为需要破解的数据，每行一个
./rcrack md5_numeric#1-10_1_128x67108864_0.rt -l wax_uid.txt
 
 
# 结果
statistics
-------------------------------------------------------
plaintext found:                              28336 of 59293
total time:                                   53.76 s
  time of chain traverse:                     12.67 s
  time of alarm check:                        2.85 s
  time of wait:                               20.64 s
  time of other operation:                    17.60 s
time of disk read:                            33.52 s
hash & reduce calculation of chain traverse:  478138752
hash & reduce calculation of alarm check:     91928521
number of alarm:                              2375649
speed of chain traverse:                      37.75 million/s
speed of alarm check:                         32.22 million/s

可以大概算出：

• 单表成功率：47.8%；
• 每个破解耗时（整体）：0.9067ms
• 每个破解耗时（成功）：1.8972ms

提高破解概率

单表的破解概率为 47.8%，如果我们需要将破解概率提高到**95%，**则需要5个彩虹表（计算：1 – (1 – 0.478)⁵ = 0.9612）

# 生成5个彩虹表，其中 table_index 指定不同的参数
./rtgen md5 numeric 1 10 1 128 67108864 0
./rtgen md5 numeric 1 10 2 128 67108864 0
./rtgen md5 numeric 1 10 3 128 67108864 0
./rtgen md5 numeric 1 10 4 128 67108864 0
./rtgen md5 numeric 1 10 5 128 67108864 0
 
# 对彩虹表进行排序
./rtgen *.rt

再进行一次破解，结果如下：

# *.rt 包含了上面生成的5个彩虹表
./rcrack *.rt -l wax_uid.txt
 
 
# 结果
statistics
-------------------------------------------------------
plaintext found:                              56947 of 59293
total time:                                   140.48 s
  time of chain traverse:                     32.23 s
  time of alarm check:                        5.56 s
  time of wait:                               49.94 s
  time of other operation:                    52.75 s
time of disk read:                            134.54 s
hash & reduce calculation of chain traverse:  1191802752
hash & reduce calculation of alarm check:     185569273
number of alarm:                              4795196
speed of chain traverse:                      36.97 million/s
speed of alarm check:                         33.38 million/s

可以大概算出：

• 整体成功率：96.04%；
• 每个破解耗时（整体）：2.3692ms
• 每个破解耗时（成功）：2.4669ms

最后

• 使用彩虹表可以用比较小的存储来实现MD5的破解；
• 破解速度与存储空间可以相互权衡；
• 取得比较高的破解成功率，并可以根据实际场景更进一步提高成功率（比如小批量数据的99.99%成功率，但速度与存储会增加）；

rainbowCrack的官网文档地址：http://project-rainbowcrack.com/documentation.htm