彩虹表的原理简介

文章来源：http://www.15897.com/blog/post/caihongbiao-yuanli.html

夜火以前发过120G彩虹表HTTP下载。enWiki上面的情况更复杂，hash chain长度k可变，逆函数R1,2,3...n有多个，对于相同的end point 可能存在不同的过程（存在冲突）。加入salt的方法，使得rain table的计算变得更难实现，重要的是相同的密码不会产生一样的hash值。

彩虹表的原理简介

    彩虹表（Rainbow Table）是一种破解哈希算法的技术，它的性能非常让人震惊，在一台普通PC上辅以NVidia CUDA技术，对于NTLM算法可以达到最高每秒103,820,000,000次明文尝试（超过一千亿次），对于广泛使用的MD5也接近一千亿次。更神奇的是，彩虹表技术并非针对某种哈希算法的漏洞进行攻击，而是类似暴力破解，对于任何哈希算法都有效。

    这几乎是令人难以置信的，Roger迫不及待的去看了  所介绍的原理。这其实已经不是新的技术了，但是很遗憾的是，搜索“彩虹表原理”出来的文章对彩虹表原理的介绍都有不太正确，Roger就在这里简单的介绍一下，主要参考的是Wiki上的这篇 ，英文好的可以去看这篇论文 。

  我们先来做点科普，哈希（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)就是我们在追寻的p，为了验证我们把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的源码 

    说到彩虹表不得不说ophcrack和LM Hash了。本来即使是彩虹表的千亿次速度，破解14位数字字母的密码也需要百万年的时间，无奈微软为自己的Windows密码设计了一个极其**的算法LM Hash：它把超过7位的密码拆成两个7位的密码分别做hash。。。然后还大小写不分，这使得它的取值范围只有 36^7 约 784亿，这么小的集合加上彩虹表的威力，很快就可以破解出来。于是有了ophcrack，它可以dump SAM，然后Load指定的彩虹表进行破解。SAM是Windows存放密码散列的地方（system32\config\sam），一般情况下是受到操作系统保护的，即使是管理员也没办法读取，但是还是有很多工具能把它读出来，例如ophcrack自带的pwdump。下面是Roger在笔记本上用ophcrack破解一个11位大小写+数字密码的截图（无），仅仅4秒！如果table已经在内存中，速度还会更快，几乎是瞬间。当然这个程序要求内存比较大，否则Load Table会比较慢。

    ophcrack还有Live CD的ISO供下载，这意味着，只要可以物理接触一个XP的系统，就可以轻松的获取所有用户的密码明文！那我们将如何应对？像Windows这样的是无法有力的保护散列的存放的，唯一的办法是禁用很弱智的LM Hash算法，仅使用比较强的NT Hash，破解的难度会增大很多。Vista以后默认禁用了LM Hash。对于XP，可以修改本地安全策略的安全选项，“网络安全：不要再下次更改密码时存储Lan Manager的 Hash值” 设为启用，再修改一次密码就可以了。

    最后再提一下王小云的MD5的破解问题。这个准确来说不叫破解，而是她找到一种方法能快速找到碰撞。就是给出一个p1，可以很快算出一个不等于p1的p2使得 MD5(p1)=MD5(p2)，这一点足够把MD5枪毙掉了。但是这并不意味着能根据MD5的Hash反算出明文来，也无助于对密码的破解。