彩虹表(Rainbow Tables)原理及参考使用手册（附：1000G彩虹表下载）

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

一、彩虹表原理

先讲述一些基本概念：

Tables

可以说长期进行密码学研究的人很少有不知道这个的。在很多年前，国外的黑客们就发现单纯地通过导入字典，采用和目标同等算法破解，其速度其实是非常缓慢的，就效率而言根本不能满足实战需要。之后通过大量的尝试和总结，黑客们发现如果能够实现直接建立出一个数据文件，里面事先记录了采用和目标采用同样算法计算后生成的Hash散列数值，在需要破解的时候直接调用这样的文件进行比对，破解效率就可以大幅度地，甚至成百近千近万倍地提高，这样事先构造的Hash散列数据文件在安全界被称之为Table表(文件)。

Rainbow Tables

最出名的Tables是Rainbow Tables，即安全界中常提及的彩虹表，它是以Windows的用户帐户LM/NTLM散列为破解对象的。简单说明一下，在 Windows2000/XP/2003系统下，账户密码并不是明文保存的，而是通过微软所定义的算法，保存为一种无法直接识别的文件，即通常所说的SAM文件，这个文件在系统工作时因为被调用所以不能够被直接破解。但我们可以将其以Hash即散列的方式提取，以方便导入到专业工具破解，提取出来的密码散列类似于下面：


Administrator:500:96e95ed6bad37454aad3b435b51404ee:64e2d1e9b06cb8c8b05e42f0e6605c74:::
Guest:501:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
user1:1001:732b2c9a2934e481cd0a8808b19097ef:778620d5d5de064154e689fa4790129f:::
user2:1002:a042f67a99758fd727b99b2375d829f9:6127ee12a83da34fc19953e538e4d580:::


若是以传统破解方式而言，无论是本地，还是内网在线破解，效率都不是很高。据实际测试，单机环境下，破解一个14位长包含大小写字母以及数字的无规律密码，一般是需要3~~9小时的，这个时间值会随着密码的复杂度及计算机性能差异提升到几天甚至数月不等。虽然说大部分人都不会使用这样复杂的密码，但对于目前很多密码足够复杂并且长度超过10位的密码比如“Y1a9n7g9z0h7e”，还是会令黑客们头痛不已。

2003年7月瑞士洛桑联邦技术学院Philippe Oechslin公布了一些实验结果，他及其所属的安全及密码学实验室(LASEC)采用了时间内存替换的方法，使得密码破解的效率大大提高。作为一个例子，他们将一个常用操作系统的密码破解速度由1分41秒，提升到13.6秒。这一方法使用了大型查找表对加密的密码和由人输入的文本进行匹配，从而加速了解密所需要的计算。这种被称作“内存-时间平衡”的方法意味着使用大量内存的黑客能够减少破解密码所需要的时间。

于是，一些受到启发的黑客们事先制作出包含几乎所有可能密码的字典，然后再将其全部转换成NTLM Hash文件，这样，在实际破解的时候，就不需要再进行密码与Hash之间的转换，直接就可以通过文件中的Hash散列比对来破解Windows帐户密码，节省了大量的系统资源，使得效率能够大幅度提升。当然，这只是简单的表述，采用的这个方法在国际上就被称为Time-Memory Trade-Off ，即刚才所说的“内存-时间平衡”法，有的地方也会翻译成“时间—内存交替运算法”。其原理可以理解为以内存换取时间，可由下图3表示：

图 著名的“内存-时间平衡”法运算原理图

　　具体算法方面的内容本文就不再涉及，对于想进行更高深层次探究的读者，可以仔细参考2003年的这篇详细文档《Making a Faster Crytanalytical Time-Memory Trade-Off》以及2005年的文档《Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints》。

正是由于Rainbow Tables的存在，使得普通电脑在5分钟内破解14位长足够复杂的Windows帐户密码成为可能。

图 对Windows账户进行Rainbow Tables破解

　　如上图4可以看到，类似于c78j33c6hnws、yemawangluo178、38911770这样的Windows帐户密码几乎全部在180秒即3分钟内破出，最短只用了5秒，个别稍长的密码破解开也没有超过3分钟。

这几乎是令人难以置信的，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.co

二、彩虹表完全参考手册

彩虹表就是一个庞大的、针对各种可能的字母组合预先计算好的哈希值的集合，不一定是针对MD5算法的，各种算法的都有，有了它可以快速的破解各类密码。越是复杂的密码，需要的彩虹表就越大，现在主流的彩虹表都是100G以上，目前主要的算法有LM, NTLM, MD5, SHA1, MYSQLSHA1, HALFLMCHALL, NTLMCHALL, ORACLE-SYSTEM, MD5-HALF。

先科普个概念，就是彩虹表的成功率，在下面网站中大家会看到，在下载时，都会分成四个目录，从index的0到3，那么为什么一个表会分成四部分呢。其实这四个部分都是独立的彩虹表，他们的绝大多数覆盖的内容是一样的，只有少部分区别。也就是说，单个表的成功率并不是100%的，根据算法看，以4个表的一个set来看，整个set的成功率达到99.9%,分为4个表，那么有：

也就是说，为了追求空间和成功率间的平衡，我们不需要下载所有的表，下2-3个表的成功率已经足以应付普通的追求了，如果你空间很多那就另当别论了，嘿嘿。

目前来说主要是老外在做着方面的工作，国内基本没什么网站在弄了，贴几个经典的彩虹表网站：

http://project-rainbowcrack.com
主要是下载生成程序和买现成的彩虹表的地方，主要的格式是rc和rtc，自带有GUI查询程序，支持GPU加速查询，速度肯定刷刷的。最郁闷的是没有现成的表下载，如果自己生成，基本上等死人，不推荐，除非你有分布式大型运算系统。但是这里提供购买，我发询问邮件回复的是中文你信不信，嘿嘿：

project-rainbowcrack_buy

 

Smaller Tables:
Table md5_ascii-32-95#1-7 (64 GB)
Table md5_mixalpha-numeric#1-8 (160 GB)
Table md5_loweralpha-numeric#1-9 (80 GB)

这三个表加一个500G的移动硬盘，包邮卖300美元，一个字，贵！但是有了这四个表基本cmd5.com上收费的数据都能够查出来，听说北京中关村也有卖，好像是500多块钱，我没有证实，有兴趣的可以去证实一下。还有一个1000美金

http://freerainbowtables.com/
福音啊，要是没有这个网站，真不知道去哪下载了，目前提供下载的表已经十分多和大了，采用的是志愿者分布式运算，可以下载网站上的软件加入这个计算系统，利用电脑的剩余资源计算彩虹表，运算的速度还是蛮快的：

统计
活跃主机	4339
在线主机	2590
当前计算能力	21015 GIOPS
最近24小时	8178 百万彩虹链
当前速率	56.9 十亿链/秒
数据增长	121.86 GB

主要提供的下载格式是rti和rti2，新算出来的表都是rti2的了，这种类型的表需要使用 rcracki_mt来查找，大小好像也会比rt小一点。当然，这个网站也是提供购买数据服务的了。下载地址：
http://freerainbowtables.mirror.garr.it/mirrors/freerainbowtables/RTI2/
http://freerainbowtables.mirror.garr.it/mirrors/freerainbowtables/
顺便说一下软件rcracki_mt，它是支持CPU和GPU的，也就是支持使用CUDA，现在的大表，一般都需要使用GPU来跑，要不然会等死你。下载地址：
https://sourceforge.net/projects/rcracki/files/rcracki_mt/rcracki_mt_0.7.0/
For cpu only runs on windows use the default win32_mingw built. 
For gpu only runs on windows use the win32_vc build.
For linux pre-built binaries for gpu/cpu use the linux_x86_64.

http://ophcrack.sourceforge.net/
针对windows系统的彩虹表，优化过，体积大大减少，xp的表全免费，vista的大表是收费的，但是网上有网友放出下载，但是平时使用根本不需要用到那么大的了，基本上普通人的电脑密码强度都是很简单的，主要不要下german的表了，那是包含德语符号的，贴下官方的覆盖图。

下面的是收费表的

下载地址：
http://ophcrack.sourceforge.net/tables.php

http://www.pwcrack.com/rainbowtables.shtml
是个下载彩虹表的种子的分流站，可以去下载种子，不过如果迅雷离线里面有的话，就很快了，单表，成功率在80%多吧。

http://www.ha97.com/code/tables.rar
国内流出的120G彩虹表，好像包括了md5和lm什么的，我没下，感觉还是自己找的靠谱点。国内真正流传出的好东西太少了。

找了找看了下还是觉得那套300美元的小表比较适合国内使用，为什么呢，我觉得它的覆盖面和自身大小比例非常棒，我们来看看charset.txt：

freerainbowtables上的很多表都是包含了空格的，而国内由于母语不是英文基本上是不会用到空格的的，因此造成了很多的数据冗余，不过硬盘大的话，没关系啦，嘿嘿嘿。如果有好的下载源，欢迎各位留言补上，嘿嘿。

 

http://pan.baidu.com/s/1eQj5mDk