夜火博客 个人的碎碎念收集箱

彩虹表的原理简介

夜火以前发过120G彩虹表HTTP下载,但是一直不清楚那么庞大的数据,怎么会那么快的原理,特转来一篇彩虹表的原理简介

彩虹表的原理简介

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

    这几乎是令人难以置信的,Roger迫不及待的去看了 http://www.project-rainbowcrack.com 所介绍的原理。这其实已经不是新的技术了,但是很遗憾的是,搜索“彩虹表原理”出来的文章对彩虹表原理的介绍都有不太正确,Roger就在这里简单的介绍一下,主要参考的是Wiki上的这篇 http://en.wikipedia.org/wiki/Rainbow_tables,英文好的可以去看这篇论文 http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf

  我们先来做点科普,哈希(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)就是我们在追寻的q,为了验证我们把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的源码 http://www.project-rainbowcrack.com

    说到彩虹表不得不说ophcrack和LM Hash了。本来即使是彩虹表的千亿次速度,破解14位数字字母的密码也需要百万年的时间,无奈微软为自己的Windows密码设计了一个极其傻逼的算法LM Hash:它把超过7位的密码拆成两个7位的密码分别做hash。。。然后还大小写不分,这使得它的取值范围只有 36^7 约 784亿,这么小的集合加上彩虹表的威力,很快就可以破解出来。于是有了ophcrack,它可以dump SAM,然后Load指定的彩虹表进行破解。SAM是Windows存放密码散列的地方(system32configsam),一般情况下是受到操作系统保护的,即使是管理员也没办法读取,但是还是有很多工具能把它读出来,例如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反算出明文来,也无助于对密码的破解。
————————————————————————
作者: roger
Blog: http://rogerfd.cn
Email:roger99707@163.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

留言列表
破军
破军 哦,又增长了认识了。我转走咯!嘻嘻  回复
chinese
chinese 学习了,谢谢!  回复
xiexie
xiexie 如何算得看不懂.但是顶了.  回复
lyf2002
lyf2002 不错,看懂了。  回复
发表评论
来宾的头像