RainbowCrack

RainbowCrack是一个使用内存时间交换技术（Time-Memory Trade-Off Technique）加速口令破解过程的口令破解器。RainbowCrack使用了彩虹表，也就是一张预先计算好的明文和散列值的对照表。通过预先花费时间创建这样的彩虹表，能够在以后破解口令时节约大量的时间。

RainbowCrack文件说明：

RainbowCrack包含了下述实用程序：

— rtgen.exe——彩虹表生成器，生成口令、散列值对照表。

— rtsort.exe——排序彩虹表，为rcrack.exe提供输入。

— rcrack.exe——使用排好序的彩虹表进行口令破解。

首先使用彩虹表生成器（rtgen.exe）生成自己的彩虹表。其命令行格式为：

rtgen hash_algorithm
plain_charset plain_len_min plain_len_max
rainbow_table_index
rainbow_chain_length rainbow_chain_count
file_title_suffix
rtgen hash_algorithm
plain_charset plain_len_min plain_len_max
rainbow_table_index
-bench

Rainbow-Table-Attack 这是对"Brute-Force"和"Directory-Base"的一种折中的破解技术，在2003年瑞典的Philippe Oechslin 在Making a Faster Cryptanalytic Time-Memory Trade-Off一文 (文章开头有给出链接)中首次被提出，它有效的利用了PreComputation的优点，同时又克服了Diecretory-Based消耗太空磁盘空间的缺点，在这两者中找到了一个平衡点。 

不过，它也有缺点，即: 　
1) password+salt: 加盐 　
2) key stretching: 密码扩展，包括轮数扩展和长度扩展 接下来，我们的文章会重点分析这个彩虹表破解的技术原理 

3. 这几种密码破解方式的应用场景

在开始研究Rainbow Table-Attack的技术之前，我们有必要先明白一个问题，虽然说彩虹表破解技术比"Brute-Force-Attack"、"Directory-Based-Attack"都要好，但并不是所有场景下都能使用彩虹表进行破解的。

rainbowcrack使用教程：

其它的加密方式破解也可以很容易地添加到该软件中。
软件同时支持windows和linux系统
而且在一个系统上生成的表单可以直接转换到另一种系统上使用
用它来破解md5密码，数分钟即可让十位数内与字符密码还原，
它的功能虽然强大，但是在使用时却是比较复杂的，因此我要详细的介绍一番
第一步：
生成表单文件
下载来的软件压缩包中有几个执行程序，。
我们在破解md5密码时，要用到的是前两个可执行文件，是rcrack.exe rtgen.exe
其中的"rtgen.exe"程序就是用来生成包含预设密码表单文件的
表单文件中有许多大量的md5加密密文，rainbowcrack的原理不是暴力破解
而是通过查询预先做好的密码与密文一一对应的文件来快速破解密。优点是速度快，
缺点是生成的文件非常大，
在命令提示符窗口中，运行"rtgen.exe"命令
也可以输入cmd在那里面，找到，你解压缩文件的路径，然后运行
由于rainbowcrack是一个多功能的密码破解器，因此提示信息比较复杂，
我们只需破解md5密码，在这里可以按下面的格式生成md5密码表单：
"rtgen md5 byte 1 7 5 2400 40000 all";
命令执行后，提示"generateing...."正在生成密码文件
其中"md5"参数指定生成md5表单。
如果是破解windows密码之类的，还可以使用相应的"lm/sha1"参数
详细的，可以看帮助文件。
"byte"参数用来指定生成密码表单中所包含的明密类型为所有字符和数字
如果想破解的是纯数字密码或是纯字符密码。
可以将其改为相应的"numeric"或"alpha"参数
具体的参数可见目录下"charset.txt"文件
其中1和7分别代表密码最小和最大长度
2400代表每个表单文件中密码串的长度
数字5用来表示生成表单文件的数目
而40000则代表每个表单文件中的密码数目
后面这两个数目越大，生成表单文件的速度越慢
但是表单文件中的密码就越多。
相应的破解速度也会越快
命令执行后，提示"generateing...."正在生成密码文件
执行完毕后。就会在当前目录下生成5个文件名类似为"md5_byte#1-7_5_2004X40000_all.rt"的文件
其中"all"是我们刚才在生成命令中指定用来添加标识文件的参数
有点慢.我们先继续(这是刚才生成的表单文件)
第二步：
瞬间破解密码
生成密码表单文件后，就可以利用"rcrack.exe"文件来查询表单文件，
快速破解出指定的密码了。
直接执行命令后，即可看到程序使用帮助
从帮助信息中，我们可以看到能对单个md5密文件进行破解
也可以一次破解多个密文。
当我们要破解单个md5密码时，可以使用"-h"参数来指定要破解的密文，
假设这里要破解密文为"49ba59abbe56e057"可以输入如下命令
"rcrack *.rt -h 49ba59abbe56e057";
其中"*.rt"参数表示查询当前目录下所有密码表单文件。
如果密码表单文件制作 得好
命令执行后很快就可以从这些表单文件中找到要还原后的密码明文了
如果要一次破解多个密码。首先打开记事本。
将所有待破解的密码按行输入
保存为一个没有后缀的文件中。
这里文件名为"mima"然后执行命令：
"rcrack *.rt -l mama";
程序将会查询所有的表单文件，并将其与待破解密码文件中的密文一一对比，很快就可以将大部分的密码破
解出来了
提示一下：rainbowcrack软件可以说是md5密码的克星。我们完全可以在平时计算机不工作时，利用相当长的时间来生成个比较大的密码表单文件库

Rainbow Table彩虹表破解技术原理：

Rainbow Table相比Directory做的第一个改进就是将庞大的明文密文对"分成"了"明-密文对链chain"，链条的长度越长，空间的缩减效果就越大。为了使用彩虹表技术，需要事先确定两个 函数： H(HASH函数): 密码的加密方式，不同的彩虹表对应于不同的加密方式(这点和Directory-Based的道理是一样的) 常见的H函数有: MD4、MD5、SHA1、 R(Reverse Hash函数): 逆HASH函数，并不是真的对HASH函数求逆(我们都知道HASH函数是不可逆的)，这里所谓的R函数，只是一个映射Mapping函数，将H()得到的密文再次映射回一个对应 的明文，不一定是原来的明文，只要是明文就行

4.1 彩虹表生成

要注意，彩虹表的核心思想还是PreComputation的字典思想，所以生成彩虹表就是在生成一个字典，只是这个生成过程不再是单一的H计算，并保存明-密文对那么简单了。

我们分别看每一条链:

H(wikiedia)=ao4kd -> R1(ao4kd)=secret -> H(secret)=9kpmw -> R2(9kpmw)=jimbo -> H(jimbo)=v0d$x -> R3(v0d$x)=rootroot H(abcdefgh)=1vn6s-> R1(1vn6s)=bernie-> H(bernie)=kolscx-> R2(kolscx)=zurich-> H(zurich)=8ntpy -> R3(8ntpy)=myname .... H(passwd)=dlcm4-> R1(dlcm4)=culture-> H(culture)=re3xes-> R2(re3xes)=crypto-> H(crypto)=1tik0-> R3(1tik0)=linux23

有几个重点要关注:

1) 在这个例子中，彩虹表的chain length是3，也就是说一条链包含3个节点，也即这种情况可以以原本 1/3 的磁盘空间保存同等规模的字典

2) wikiedia称为"头结点"，rootroot称为"尾节点"。我们最后需要保存的也就是这个头-尾节点对，而中间的中间值全都不用保存，这也是彩虹表省空间的原因

3) R1、R2、R3....Rk(K代表每条链的长度，在这个例子中是3)，是K个不同的Reverse Hash函数，它存在的目的是为了避免出现不同的chain中出现重复的节点，我们可以思考一下，如果这个R在一条链中的每个节点都是一样的，那如果假如在两条链中的某两个节点在进行R()之后，得到了相同的结果，则在这之后，H计算也会得到相同的结果，紧接着R计算又是相同的结果，则造成了重复存储，浪费了存储空间，也减低了这套破解系统的明文空间覆盖度，从而间接影响了破解效果。

假如R是不变的: H(startpoint1)=median1 -> R(median1)=median12 ...... -> R(median1x)=same -> H(same)=same1 -> .... same_end H(startpoint2)=median2 -> R(median1)=same -> H(same)=same1 -> .... same_end ... 注意这个重合一定是发生在不同链上的不同位置的节点，因为H的"非碰撞性"保证了这点(思考)，这个重合导致的是两条链中的某一段发生了"重合"

会出现这个现象的原因是因为我们选择的R函数很难保证"非碰撞性"，即无法保证不同的输入在进行R计算不会得到不同的输出，为了解决这个问题，将一条链上的不同节点的每次计算都使用不同的R函数，这样，即使在不同链上的不同位置因为Rk是不一样的，就不会发生重合了。

回到主题上来，这个链式的表生成好之后，我们之保存每条链的头和尾的两个明文节点，中间的点都是"可计算的"，故丢弃，把全部的链的头尾节点保存起来，就成了所谓的彩虹表

4.2 使用彩虹表进行HASH密码破解

再次回顾这张图

假如我们要破解的HASH密文为re3xes1) 对密文re3xes进行Rk(k代表最后一个R函数，这里是R3)运算，得到一个临时结果 I，将这个临时结果I和每条链的尾节点进行比较，检测是否是某一条链的尾节点

1.1) 如果匹配成功，则破解成功，我们知道了这个待破解的密文属于某一条链，就可以利用这条链的头尾节点重现(再次计算)出这条链上的每个明密文对，自然也包括了待破解密文的明文 　　

1.2) 如果匹配失败，在所有链的尾节点上都没有这个临时结果 I，则继续进行(2)2) 对密文re3xes进行Rk-1(k-1代表倒数第二个R函数，这里是R2)，这里又得到一个临时结果: crypto，再对临时结果crypto进行H计算，得到: 1tik0，再对1tik0进行Rk 　　(k代表最后一个R函数，这里是R3)得到一个临时结果: linux23。将这个临时结果和每条链的尾节点进行比较，检测是否是某一条链的尾节点 　　

1.1) 如果匹配成功，则破解成功，在这个例子中我们知道匹配成功，就可以利用这条链的头节点: passwd重现(再次计算)出这条链上的每个明密文对，自然也包括了待破解密文的明文: culture　　 　　

2.1) 如果匹配失败，则继续调用Rk-2进行搜索，步骤都是类似的 ... 直到完成了R1的搜索，如果还没有找到匹配的，则宣布本次破解失败，需要增大彩虹表文件大小、重组字典

彩虹表的缺点：

我们知道，彩虹表的核心思想是"PreComputation预计算"，而预计算的一个最大大问题就是"当加密的形式发生变化，这个预生成的字典从某种程度上就无用了"。这么说有些不太准确，我想表达的意思是预计算对算法的变化非常敏感，这也是对抗彩虹表技术的一个思考方式。

因为彩虹表需要针对算法变化的每一种形式都预生成一个对应的字典，如果这个变化空间很大，就会使彩虹表的生成成本变得很大，这样，彩虹表原本解决的空间成本问题又再次暴露出来。

而要达到"算法变化"的方式非常多，常见的有以下两种方法

1) 加盐 saltedhash(password) = hash(password+salt) Or saltedhash(password) = hash(hash(password)+salt) 需要对付这种加密方式，彩虹表就需要针对salt的每一种可能的取值都生成一套字典，当salt的长度很长时，彩虹表的生成成本和破解效率都会大幅下降

2) 密码增强 key stretching 是加密方式变化除了"加盐"，加密轮数也是一个可变化的点，MD5-Crypt and in bcryp中都使用了Crypt Loop技术，即使用同一个算法，或不同的算法组合对一个明文进行迭代的 多次(1000以上)加密，这样，加密的轮数和加密方式的组合本身也构成了一个"变化空间"需要对付这种加密方式，彩虹表就需要针对每一个加密轮数+加密方式的组合都生成一套字典，同样，彩虹表的生成成本和破解效率都会大幅下降