使用“彩虹表”轻松解密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%成功率，但速度与存储会增加）；
评论