• 隐藏侧边栏
  • 展开分类目录
  • 关注微信公众号
  • 我的 GitHub
  • QQ: 1753970025
Chen Jiehua

使用“彩虹表”轻松解密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 正比于 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位纯数字为例来生成自己的彩虹表,并可以权衡破解速度和存储空间。

大小说明:链数 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个,进行破解:

可以大概算出:

  • 单表成功率:47.8%;
  • 每个破解耗时(整体):0.9067ms
  • 每个破解耗时(成功):1.8972ms

提高破解概率

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


再进行一次破解,结果如下:


可以大概算出:

  • 整体成功率:96.04%;
  • 每个破解耗时(整体):2.3692ms
  • 每个破解耗时(成功):2.4669ms

最后

  • 使用彩虹表可以用比较小的存储来实现MD5的破解;
  • 破解速度与存储空间可以相互权衡;
  • 取得比较高的破解成功率,并可以根据实际场景更进一步提高成功率(比如小批量数据的99.99%成功率,但速度与存储会增加);
码字很辛苦,转载请注明来自ChenJiehua《使用“彩虹表”轻松解密MD5》

评论