浅析加盐散列

  • A+
所属分类:lcx

某次某个东东的小主题。。。

主题:浅析加盐散列
作者:young

0x00 简介
本文介绍了存储用户密码的方式及其相关内容(破解、安全性分析、应用实践),介绍了加盐散列这种安全的存储用户密码的方式。
这是一个简单的选题,个人水平有限,经验较浅。
本文可总结为:使用8Byte随机salt+hash保存密码更为安全有效。若你对这方面已较了解,请飞过。如有好的建议,欢迎交流讨论。

0x01 前话背景
事情是这样,你搞到了某站的库。一般可以是扔CMD5之类网站直接拿密码了。让我把这个地方无聊的描述一次。

某站用md5将你的密码hash后并存储,验证密码时,将你输入的密码进行hash并和数据库中存储的hash值对比。像下面这样。
数据库中存储md5(pw)
验证时取出md5(pw),比对md5(pw) == md5(input_pw)

为什么使用hash存储呢,考虑使用明文存储的话,存储密码的数据库被他人得到后,那个人也就获得了所有用户密码。使用hash存储后,他人只能得到密码的hash值。若想得到密码原文,只能尝试对可能的值依次进行hash运算并比对。

后来有了彩虹表,简单的说彩虹表采用预计算(pre computed)、空间-时间折中,这样想找到hash值对应的密码时只需要查找彩虹表即可。在很短的时间内即可获得hash对应密码(几秒至几分钟),单纯的hash存储密码就变得不安全了。

单纯的hash会对相同的密码产生相同的hash值,也是个不安全点。

题外说说彩虹表。魔鬼隐藏在细节里,彩虹表并不是一个简单的玩意。它不是单纯的按pw 对应hash这样存储,这样太耗空间了。彩虹表大致是这样,算出pw对应hash,构成一条链,有一个reduce函数进行回射,丢弃中间值,查找时在多条链上按规则查找。难点是reduce函数、链的实现。这些影响彩虹表查找的准确率、大小、查找耗时,还有一些特例需要处理。推荐对彩虹表原理有兴趣的朋友参考文末参考资料(1、wiki彩虹表介绍,2、彩虹表原理论文) 。彩虹表类似原理第一次在1980M.E. Hellman,的论文《A Cryptanalytic Time - Memory Trade-Off》被提及,2003年被参考资料2中的论文详细论述。
举个实际的例子,准确率上,d033e22ae348aeb5660fc2140aec35850c4da997,这个sha1 hash在cmd5上解出来为admin,修改最后一位7改为1,查出来依旧是admin。Cmd5官方写着准确率为93%,国外一些免费的彩虹表准确率基本在99%以上。相同彩虹表实现下,准确率越高,彩虹表占用空间也就越大。

对于每种可能的hash算法,彩虹表均需要计算,也就有了不同密码空间、不同存储密码方式对应的彩虹表。

这时各种抗彩虹表的方法出现了,依次说明如下
截断,类似MD5,hex编码后得到十六进制字符串长32位,只存储其中一部分。
多次hash,md5得到的hash再md5一次。
多种算法联合,先md5,得到散列,在对散列进行sha1
使用一个固定盐,把盐附在密码后面得到散列并存储
其他变种,如md5后进行一次变换。

上述方法实质并未改变,短期内可能没有对应的彩虹表,对应彩虹表出现后,上述方法均可用彩虹表破解。这些方法降低了hash算法抗碰撞性,例如,方法1中hash位数缩短,碰撞可能性提高(即密码本身是123,但输入321也可能通过验证)。

有人会说我们使用一个谁也不知道的方法保护用户密码即可,这对开源、有大量用户的应用是不现实的,你也难以保证谁也不知道就一直是谁也不知道。本文讨论的一个前提是攻击者除不知道原始密码外知道其他所有。你如果能保证你的应用是绝对安全的,存储用户密码的数据库也绝对不会外泄,那你使用明文存储也是一样的安全。
0x02 加盐散列(salted hash)对应的解决方案中较好的是加盐+hash,盐是随机的。
OpenLDAP存储密码的方式就是这样。国内的话Discuz也是类似的方法。举OpenLDAP的例子说:
使用ssha,4Byte盐,sha1做hash,base64存储
加密时:
先生成一个4Byte的随机salt,将salt附在要加密的密码pw后面,对pw+salt进行sha1得到摘要digest,base64编码digest+salt得到secret并存储。用式子表示就是
digest = sha1(pw+salt)
base64_encode(sha1(pw+salt)+salt)
验证时:
base64解码secret,取出salt、digest,对输入的密码input_pw进行sha1(input_pw+salt),得到结果与digest比对。
用式子表示就是
digest,salt = base64_decode(secret)
sha1(input_pw+salt) ?= digest

题外,我没搞懂为啥要用hex编码后存储,base64编码后存储空间大约是hex编码的一半
比较可能是一般的散列库都自带hexdigest()这个方法,若用base64需要用到其他库。

考虑这种方式,若要采用彩虹表攻击,则需要生成的彩虹表大小为 不加盐彩虹表大小*2(盐的位数次方)。实际来说RainbowCrack Project网站上sha1 1-8 混合大小写数字的彩虹表是160GB,对于4byte盐。彩虹表攻击所需的彩虹表大小为:160 * 2的32次方。空间上就是不可接受的,计算生成这些彩虹表的时间同样不可接受。

这个方式还有个好处就是对于相同密码,将会得到不同的hash值

没有弱点么?弱点在于salt,首先是盐太短,早期有很多位数很短的salt,这时生成彩虹表的代价是可接受的。多长的salt是安全的,4Byte并不足够,当我看到OpenLDAP官网给出的示例是4Byte盐时,我在写一个工具来破解弱盐,后来我放弃了,因为发现OpenLDAP的实例上salt是8Byte的。
4Byte的弱盐?这是另一个弱点,盐是可打印字符。实际是这样的,ascii表中可打印字符一共是95个,一般彩虹表中会收录的字符为小写+大写+数字共62个,那么对于一个4Byte salt生成的sha1的hash值,若salt全为可打印字符,我们直接查表,查表后得出的值减去salt就可以得到原始密码,举例来说,4Byte salt sha1的一个hash值为d033e22ae348aeb5660fc2140aec35850c4da997,查表得到admin,取出salt,就可以得到密码为a。问题是这个概率有多大,若有足够优良的彩虹表针对1-10位所有可打印字符,假设这个密码长度不超过6,那么可查表概率为(95/256)的四次方,大概是百分之一多一点。实际中可查表概率远低于此,一是没有这样全的彩虹表,二是加盐后长度增加,很轻易就超过了彩虹表支持的最大密码长度。
弱盐的另一个实际例子是django
Django(版本1.3)的盐是随机生成的5Byte,这5Byte由0-f这几个字符构成。盐较短,全是可打印字符,没有标点之类。较容易查到表,考虑一个实际的破解:
在数据库中的密码是:
sha1$31649$ce15e069aeb0cbdc16ad413044c0ab1cc0987aae
Salt = 31649,digest=ce15e069aeb0cbdc16ad413044c0ab1cc0987aae
放MD5Decrypter网站上查,得到digest对应的字符串3164999,减去盐。得知密码是99。
虽然上面举得两个弱盐的例子中对应密码本身也是弱口令,但以足够展示弱盐的风险。
由于上述原因,推荐salt 采用 8Byte以上随机盐,即大于64位的随机bit串。

Salt hash是不抗暴力破解的。后面会提到。

0x03 其他补充
一些有设计缺陷的密码保存方法不在本文讨论之中,对于那些可针对他的弱点进行破解,例如windows之前干的。
可以使用hash后再加密的方法,并把加密用密钥保存到另一个地方,这样攻击者除了拿到库还必须拿到密钥才能进行破解。
对于所有hash也包括salt+hash,如果能写数据库,你可以用一个已知原始密码的hash替换掉数据库中的对应值。这样你就能通过验证了,但你无法得知真正的原始密码。

0x04 安全,看法与实践
迁移需要一定成本。对于现有用户,由于你不知道他的原始密码,不能直接修改成新的方式,而只能让他通过验证后重新设置密码,并按新的方式保存密码。这对已有大量用户的应用来说较麻烦。
你应当尽力保护数据库不被攻击者获取,也就不用担心攻击者通过数据库破解密码。采用一定密码策略(密码复杂度要求、密码有效期等)

我们的建议是对于已有应用,只要不是采用明文保存、有缺陷的保存方式、有大量现有彩虹表的。就可以继续使用,否则应提供一个程序,当用户下次登录时提示重设密码,并按新的安全方式保存密码。
对于新应用,使用安全的方式保存密码。
这里我说的安全的方式当然是指上文中所说的使用8Byte随机盐+hash。具体实现可参考文末参考资料[9]。

0x05 暴力的艺术
在采用salt hash后,密码破解的问题退回到了原始的逐个尝试。顺着这一话题我们继续。

退回到逐个尝试后,我们破解密码的策略变成了两个。
一是缩小密码空间,尝试可能的密码,不尝试不大可能的密码。
二是提高计算能力,单位时间内尝试更多密码。

先说缩小密码空间。
举下词典生成策略。如不允许连续多位的符号、组合各种可能、变换各种可能(字母大小写转换,@a这类类似字符替换)。应当多尝试可能的密码,不去尝试不太可能的密码。多了解各类词典生成策略。
说个特别点的词典生成策略。
对于由字母组成的密码,考虑马尔科夫链,也就是只尝试可发音字符。这有一定效果的,管理员有时会用工具生成可发音字符串作为初始密码(随机生成的其他密码常被员工记在小纸条上到处放),用户有些也倾向于用可发音字符串作为密码。

其次,计算能力上。
我们现在的计算能力如何,一个简单的测试如下:

sha1在我的测试中100w次sha1计算耗时3秒。即每秒30W次sha1计算。
测试环境如下:
Cpu:xeon 5504  * 12%(我在虚拟机中,这个虚拟机有实体机xeon5504 最大百分之12的配额)
RAM:4G
程序使用python编写。
同样的测试环境我试了下Cain的sha1计算,每秒钟250W次。
这意味着一台普通的机器跑出一个1-8位的纯数字ssha只需要1分钟左右。跑出一个1-8位混合大小写数字的ssha需要两年多。

对于大的密码空间,增加计算能力主要有设计专用硬件破解(昂贵)、采用GPU辅助、使用分布式。这方面我木有实际经验,参考诸多内容后大概估计如下

使用同CPU等价显卡GPU辅助运算,运算能力可提高10倍左右
分布式取决于你客户端的数量。简单估算为 单台计算能力 * 客户端数量。

那么是否有一种抗爆破的密码存储方式?客观的说,攻击者知道验证方式、被各种hash后的密码,他知道的跟你知道的一样多,你可以使用一个强壮的密码,或者就是,增加一次尝试所需的时间。

使用sha512代替sha1,sha512需要的运算时间大概是sha1的1.5倍。
考虑设计一个耗时可控制的变换算法作为密码保存的hash。
Hash当初设计时是为了快的得出一段位串的摘要,不过对于密码存储,或许我们需要一种 慢hash。用以对抗暴力破解。

0x06 破解SSHA,破解工具与框架现在我需要破解ssha,google一下,有一个ssha_carck可以使用,那么如果不是ssha是smd或者其他加盐的hash呢。
你有一个好的字典生成器,不过他生成的字典实在太大了,但你使用那个破解器又只能载入字典或自己生成很简单的字典。
你想使用GPU、分布式等协助破解,但现有的支持GPU、分布式破解的工具并不支持爆破你那段密码,例如ssha。
是的,我寻找了一段时间。诸如Elcomsoft Password Recovery、Passware Kit这类商业的支持GPU、分布式的并不支持破解特定的被保护的密码,也不提供插件机制。
如果你自己写一个,那么你至少要写一个字典生成器、破解器,如果需要GPU、分布式,那你还得学会更多,理想情况是你只需要写出破解部分即可,应该有这样的框架。
开源的durandal,ncrack应该是个选择,我没有具体尝试。Durandal支持GPU与分布式、有一个字典生成器,ncrack跟nmap似乎有一定联系,他的目标就是成为一个破解工具框架。

0x07 资料参考[1]wiki的rainbowtable介绍                http://en.wikipedia.org/wiki/Rainbow_tables
[2]Making a Faster Cryptanalytic Time-Memory Trade-Off                 Oechslin, Philippe  彩虹表就是基于这篇论文的。这篇论文发表在Crypto 2003 ,作者本人的其他论文http://lasecwww.epfl.ch/philippe.shtml
[3]Cracking_Salted_Hashes.pdf         www.exploit-db.com/download_pdf/14710/ 是一个组织的一次集会的paper
[4]Durandal http://durandal-project.org/ 上面提及的一个开源的破解工具。支持GPU、分布式
[5]Ncarck http://nmap.org/ncrack/  一个开源的破解框架
[6]http://www.project-rainbowcrack.com/ 彩虹表的项目,可下载彩虹表
[7]cmd5  http://www.cmd5.com/  国内一个破解常见hash,salt hash之类的站
[8]基于用户身份鉴别的密码存储方式        张俨娜1.周珂2                 电脑知识与技术(学术交流) 2007,2(10)        国内的一篇介绍密码存储方式的文章
[9]http://www.openldap.org/faq/data/cache/347.html   OpenLDAP FAQ上关于ssha的介绍文章来源于lcx.cc:浅析加盐散列

相关推荐: 完美扫描PHP特殊一句话后门

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: