Rainbow Table破解算法

这是早些时候一个朋友要求帮他优化rainbow table代码的时候写的。今天，另外一个朋友提到了rainbow table，就把文档拿出来跟大家分享一下吧。
rainbow table算法是当前比较流行的密码破解算法，很多商业软件都是基于它的改进。

加密的原理就在于，通过将明文通过一定的hash算法，将明文空间映射到一个密文空间。

破解密码的最简单的两种思路：
1. 顺序的计算所有明文空间中明文的hash，与密文进行比较，如果相等，说明找到了对应的明文。
2. 预先将所有的明文空间中的明文进行hash，并将结果存放到一个表中；破解的时候，直接查表，找到对应的明文。

这两种方法要么费时，要么费力。要是不相信，你可以试一下，可以将明文空间指定的大一些;-)

理解rainbow table的核心思想就在于理解reduce函数。
hash函数将明文空间映射到hash空间；reduce函数将hash空间映射到明文空间。
注意：reduce函数并不是hash函数的反函数，只是映射方向与hash函数相反而已，要是的话，我们就发财了;-)
当然，列位如果认为是反函数，可以验证一下，如果验证是的话，不要忘了告诉我。

举例来说，针对6位数字的md5， MD5("493823") -> "222f00dc4b7f9131c89cff641d1a8c50"。
这里我们定义reduce函数R()为hash值中的前6个数字，因此R("222f00dc4b7f9131c89cff641d1a8c50") -> "222004".
现在，我们通过reduce函数得到了另外一个明文，这就是reduce函数的目的。
通过不断的重复这个过程，每次生成不同的明文，形成一条链。
明文 -hash->  密文 -reduce-> 明文 -hash-> 密文 -reduce->明文 -hash->密文......

经过固定的轮数N之后，通过最初的明文A，hash函数H，reduce函数R，得到了最后的密文B。
只要知道上面的A、H和R，就可以计算，第i步得到的明文和密文了。实际上，链表中除开头和结尾的元素都是可以去掉的，因为我们可以通过计算得到;-)
链的表示，可以用Start和End元素来表示，也就是A和B。当然其他的例如H、R和N，都是系统之前设定好的。

这样我们可能生成如下的几条链：

iaisudhiu -> 4259cc34599c530b1e4a8f225d665802
oxcvioix -> c744b1716cbf8d4dd0ff4ce31a177151
9da8dasf -> 3cd696a8571a843cda453a229d741843
[...]
sodifo8sf -> 7ad7d6fa6bb4fd28ab98b3dd33261e8f

有了这些链，我们就可以用它们来进行密码破解了。现在，我们有一个未知明文的密文X，需要进行破解得到明文M。

算法如下：
start = 0
step = 0
while(step < N)
{
    if( T in Set_END )
        start = T.start
        break
    else
        T = hash(reduce(T))
        step++
}

if( start )
{
    for(;i    {
        start=reduce(hash(start))
    }
    M = start
}
else
{
    NOT Found ;-(
}

1. 在所有的链尾元素中查找，如果找到了就跳出循环。
2. 如果没有找到，就调用reduce函数，得到一个新的明文，并对其进行hash，得到新的密文，跳到1继续执行。
3. 如果找到了，说明了原始的密文X在对应的那条链中。
注：查找元素是否在链尾元素集合中，通常采用二分法，需要原先将所有的链按照链尾元素大小排序。字典一般非常的大，需要拆成多个文件。

我们用一个实例图来描述一下，M表示明文，X表示密文。

假设原始密文为X2，最后通过S步的Reduce和Hash，得到一个密文X6是某一条链的结尾元素。
那么X2肯定在X6所在的链中，而且是从开头M0经过(N-S-1)步Hash和Reduce操作得到的那个明文，就是原始密文对应的明文。

注意：当然存在一种情况，我们构造的链表不能覆盖所有的明文密文空间，那么就会可能出现，一个密文出现在所有链表中都不存在的情况，那么就无法破解这个密文。
实际上，rainbow table的算法很简单，最大的问题在于生成一堆比较好的chain。这需要大量的机器和大量的硬盘资源。很多破解产品，它们卖的不是软件，而是它们的字典。
BTW:因为计算不同的chain是不相互影响的，可以通过CUDA等并行平台来进行并行化处理。

参考：