密码破解

用户密码破解需要针对具体的加密方式来实施,如果使用对称加密,并且算法足够安全(比如AES),必须获取到密钥才能解密,没有其它可行的破解方式。

如果采用HASH算法(包括特殊HASH),一般使用彩虹表的方式来破解,彩虹表的原理是什么呢?我们先来了解下如何进行HASH碰撞。单向HASH算法由于不能进行解密运算,只能通过建表、查表的方式进行碰撞,即将常用的密码及其对应的HASH值全计算出来并存储,当获取到HASH值是,直接查表获取原始密码,假设用MD5算法来保护6位数字密码,可以建如下表:


全表共100W条记录,因为数据量不大,这种情况建表、查表都非常容易。但是当密码并不是6位纯数字密码,而是数字、大小写字母结合的10位密码时,建立一个这样的表需要(26+26+10)^ 10 ≈ 83亿亿(条记录),存储在硬盘上至少要占用2000W TB的空间,这么大的存储空间,成本太大,几乎不可行。有什么办法可以减少存储空间?一种方法是“预计算哈希链”,“预计算哈希链”可以大幅减少HASH表的存储空间,但相应的增加了查表时的计算量,其原理大致如下:

建表过程

先对原始数据“000000”进行一次HASH运算得到“670B1E”,再对HASH值进行一次R运算,R是一个定制的算法可以将HASH值映射到明文空间上(这里我们的明文空间是000000~999999),R运算后得到“283651”,再对“283651”进行hash运算得到“1A99CD”,然后在进行R运算得到“819287”,如此重复多次,得到一条哈希链。然后再选用其它原始数据建立多条哈希链。最终仅将链头和链尾保存下来,中间节点全都去掉。

查表过程:假设拿到了一条HASH值“670B1E”,首先进行一次R运算,得到了“283651”,查询所有链尾是否有命中,如果没有,则再进行一次HASH、一次R,得到了“819287”,再次所有链尾,可以得到看出已经命中。这样我们就可以基本确认“670B1E”对应的明文就在这条链上,然后我们把这条链的生成过程进行重新计算,计算过程中可以发现“000000”的HASH值就是“670B1E”,这样就完成了整个查表过程。这种表就是“预计算哈希链”。这种方式存在一个问题,多条链之间可能存在大量的重复数据,如下图所示:

为了解决这个问题,我们将R算法进行扩展,一条链上的多次R运算采用不同的算法,如下图:

一条链上的每个R算法都不一样,就像彩虹的每层颜色一样,因此取名的为彩虹表。

当然彩虹表除了可以用户破解HASH算法外,理论上还可以用于破解对称加密算法,比如DES算法,由于DES算法密钥比较短,建立彩虹表破解是完全可行的;但对于AES算法,由于密钥比较长,建表几乎不可行(需要耗时N亿年)。

三、小结

采用PBKDF2、bcrypt、scrypt等算法可以有效抵御彩虹表攻击,即使数据泄露,最关键的“用户密码”仍然可以得到有效的保护,黑客无法大批量破解用户密码,从而切断撞库扫号的根源。当然,对于已经泄露的密码,还是需要用户尽快修改密码,不要再使用已泄露的密码。


以上转载

http://techshow.ctrip.com/archives/1432.html

评论
热度(1)

© dzxlovelar | Powered by LOFTER