基于彩虹表碰撞法破解SHA/MD5等hash加密——半非暴力破解哈希逆运算

背景知识

哈希加密算法应用范围广泛，包括但不限于：Unix风格的用户密码（Linux、*BSD、Solaris、AIX、QNX等）、macOS、Windows、Web应用程序（如WordPress）、办公软件（如Notes、Domino）、数据库（如MySQL）、文件系统和磁盘（macOS.dmg、Windows BitLocker）、压缩软件（ZIP、RAR、7Z）、文档文件（PDF、Microsoft Office）等。

常见的哈希加密算法有MD5、SHA1、SHA256、SHA3等，他们都有一个特点，就是算法不可逆，要想通过密文倒推加密前的明文，最可靠的办法是暴力穷举，但其耗时往往是无法接受的。

以14位字母和数字的组合密码为例，共有 $(26*2+10)^{14}\approx 1.2*10^{25}$ 种可能，即使电脑每纳秒计算一个hash值，也需要4亿年才能穷举，其耗时是不可接受的。

另一种办法是查表法，提前将穷举的结果的原文/密文对保存下来，拿到密文后通过查表找到对应的原文，也就是用空间换时间，但是这种空间代价也是无法接受的，还是以14位字母和数字的组合密码为例，假设密文长度为32字节，那么需要存储

$(32+14)*2*10^{25}=9.2*10^{26}\approx 8.4*10^{14}TB$

假设1TB硬盘价格1RMB，硬盘费用在8百万亿元人民币，是无法承受的。

为此，有人提出了一种碰撞算法来实现暴力破解哈希加密，并命名为彩虹表密码攻击法，该方法是查表法和暴力穷举法的折中优化，在可接受的存储容量基础上，大大减少计算量。

彩虹攻击技术原理

彩虹攻击本质上是一种暴力破解方法，同时采用了空间换时间的思路，即预先针对某种哈希加密算法生成彩虹表，然后使用彩虹表里面相对少量的值表征了整个超大密码空间值。要弄懂彩虹攻击原理，我们先要弄懂Hash函数工作原理，然后设计一个将哈希值散列到明文空间的Reduce函数，然后再理解彩虹链和彩虹表，最后理解碰撞检测原理。不着急，一个一个来

Hash函数

以最常用的MD5函数为例，我们借助node.js里面的md5模块

var crypto = require('crypto');
var md5 = crypto.createHash('md5');var result = md5.update('MyPasswad').digest('hex');// 输出：5342972619fca82e494ff2fb688f5da2
console.log(result);
// 输出：32
console.log(result.length)

其功能是将输入的 MyPasswad 字符串通过哈希计算，散列对应到一个长度为128bit的大数空间中的某个数，最后通过16进制打印出来。其中有几个重点：

1.均匀性：尽量确保不同的字符串经过哈希计算后会对应到不同的大数，很难找到两个不同的字符串具有相同的哈希值，即实现哈希散列的均匀化，具备高抗碰撞性；

2.单向性：无法从哈希加密结果反向计算加密前的明文字符串，即该计算是单向的，不可逆；

3.唯一性：同一个字符串经过某种哈希计算后得到唯一的大数值。