[1045]彩虹表
文章目录
彩虹表
彩虹表（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
二、获得彩虹表
RainbowCrack： http://project-rainbowcrack.com/table.htm
120G彩虹表BT下载：http://www.ha97.com/code/tables.rar
彩虹表工具很多，常用到的彩虹表工具有Ophcrack、rcracki_mt、Cain等。
freerainbowtables: http://www.freerainbowtables.com/
Ophcrack: http://ophcrack.sourceforge.net/ http://ophcrack.sourceforge.net/tables.php
最小彩虹表是最基本的字母数字表，就这样它的大小就有388MB。这是Ophcrack启动盘默认的表，很多人的收集便有了传说中的120G的彩虹表。win2003及以前的windows操作系统的密码采用的LM算法加密，而Vista、Win7、Win2008/R2采用的是NTLM，NTLM比LM安全得多。
使用“彩虹表”轻松解密MD5
大家都在说MD5用于加密不安全！不安全！！不安全！！！那到底是有多不安全，怎么个不安全法呢？
在线MD5破解
目前网上有许多在线的md5以及其他hash破解网站，部分免费。
我们可以使用 http://cmd5.la/ 进行在线的md5破解。
彩虹表MD5破解
RainbowCrack官网：http://project-rainbowcrack.com/，工具主要为 rainbowcrack-1.6-linux64, 具体使用方法查阅官网文档。
彩虹表破解与传统的暴力破解并不相同：
A brute force hash cracker generate all possible plaintexts and compute the corresponding hashes on the fly, then compare the hashes with the hash to be cracked. Once a match is found, the plaintext is found. If all possible plaintexts are tested and no match is found, the plaintext is not found. With this type of hash cracking, all intermediate computation results are discarded. A time-memory tradeoff hash cracker need a pre-computation stage, at the time all plaintext/hash pairs within the selected hash algorithm, charset, plaintext length are computed and results are stored in files called rainbow table. It is time consuming to do this kind of computation. But once the one time pre-computation is finished, hashes stored in the table can be cracked with much better performance than a brute force cracker.
彩虹表原理
彩虹表的实现原理可以参考Philippe Oechslin’s faster time-memory trade-off technique 这篇论文。
原理参考：
简单要点：
- 彩虹表的个数：l，每个彩虹表采用不同的 reverse function，避免了碰撞和合并；单个表的破解概率有限，可以通过使用多个彩虹表来提高整体的破解概率，Pall = 1 – (1 – Pone)l
- 每个表的链数：m，每个表中预先哈希、反哈希……之后存储的起点和终点，中间过程不存储，每条链（起点和终点）占用16byte
- 每条链的长度：t，每条链哈希和反哈希的次数，链越长，需要的CPU资源越多，破解时间也更长，但成功率更高
时间-空间：
- 时间：T 正比于 t * l
- 空间：Ｍ 正比于 m * l
性能优化
内存：
4 GB memory is minimal and 8 GB or more memory is recommended. Larger memory always help to improve performance when searching large rainbow tables.
硬盘：
Because rainbow table must be loaded from hard disk to memory to look up and some rainbow table set can be as large as hundreds of GB, hard disk performance becomes a very important factor to achieve overall good hash cracking performance. We suggest put rainbow tables in RAID 0 volume with multiple hard disks. Windows operating system natively support software RAID 0 called “striped volume”. The rcrack program always read data from hard disk sequentially. There is no random access.
GPU：
RainbowCrack software supports GPU acceleration with CUDA enabled GPUs from NVIDIA and OpenCL enabled GPUs from AMD. GPU acceleration with multiple GPUs is supported. To get optimal performance, all GPUs need be of same model.
彩虹表生成
现在，我们以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)5 = 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%成功率，但速度与存储会增加）；
参考：https://www.cnblogs.com/bokun-wang/p/3887463.html https://chenjiehua.me/python/rainbow-table-crack-md5.html https://www.cnblogs.com/bokun-wang/p/3887463.html https://www.jianshu.com/p/732d9d960411
腾讯云开发者
