哈希值有点像指纹数据。

说明

一个特定的哈希值表示一个文件,或者任意数据集合。至少在理论上,上面你看到的是一个128位的MD5哈希值,它最多可以表示2^128个独立项,或者340,000,000,000,000,000,000,000,000,000,000,000,000个。在现实中可用的空间会缩减;一旦你填充了一半的空间,你将看到明显的碰撞,但是不可能一半这么巨大的数据仍然还有大量的冲撞。

早在2005年,我琢磨过一个校验和(Checksum)与一个哈希(Hash)的差别。你可以认为一个人的全名就是一个校验和:Eubediah Q. Horsefeathers。这是一个快速、简单的独特捷径,但是容易伪造,因为名字不是安全的重点。你不可能走近一个人然后采集指纹来证明他就是他本人。由于社会的种种因素,名字仅仅是方便消除歧义,一种快速的决定你在和谁谈论的方法,而不是绝对的身份证明。可以肯定全世界有多个人有相同的名字,依法更换成别人的名字也不会造成太多麻烦,但是把你的指纹改成Eubediah的完全是不可能的,只有在电影里才能看到!

哈希算法用来防篡改

一个设计得当的哈希函数会根据输入的数据产生一个很微小单个位数的本质性变化输出。即使这些变化是恶意的,想欺骗哈希算法的。不幸的是,并不是所有的哈希函数都设计的得当,一些像MD5,也被彻底的打破并且很可能被转换为校验和算法

就像我们下面将解释的,Wang和Yu的算法可被用来创建任意长度具有相同MD5值的文件,唯一不同在于文件中间128位某些的地方。一些人已经用这个技术创建了具有相同MD5值的文件组:

  • Magnus Daum和Stefan Lucks已经创建了两个具有相同MD5值的PostScript文件,一个是议案信,一个是安全检查。

  • Eduardo Diaz描述了可以将2个程序打包到相同的MD5值文档中方案。一个特殊的“提取”程序使一个文档好用,另一个不好用。

  • 2007年,Marc Stevens, Arjen K. Lenstra 和 Benne de Weger使用Wang和Yu的一个改善版本来挑战chosen prefix collision方法产生2个可执行的具有相同MD5值的文件,但表现不同的是,不像老方法,2个文件仅仅在几个精心挑选的位上有所区别,chosen prefix方法通过在每个文件的结尾加上几千个字节允许2个完全任意的文件有相同的MD5值.

  • Didier Stevens使用evilize程序(如下)创建了2个具有相同Authenticode数字签名的不同程序。Authenticode是微软的代码签名机制,虽然它默认使用SHA-1算法,但是它也支持MD5算法。

如果你可以随意仿制其他人的指纹或者DNA,那么你就能做做一些非常邪恶的事情。MD5明显妥协了,且SHA-1现在看上去也没那么强大

好消息是这些哈希算法由专业的数学家和密码学家设计,他们知道他们在做什么。随便挑一个比MD5(1991)和SHA-1(1995)更新的哈希算法,你将会没事——至少在被关注的碰撞和唯一性上。继续看下去。

哈希算法运行缓慢

校验和(checksum)的速度很重要,因为校验和一般用在传输的数据上,如果校验和计算用的时间太长,会影响到你的数据传输速度。如果校验和计算导致明显的CPU开销,这就意味着传输数据也将会减慢或者导致计算机过载。例如,想象下被用在像DisplayPort上的视频标准校验和算法,可以达到17.28Gbit/Sec。

但是哈希算法不是为了速度而设计的,事实上,恰恰相反:当哈希算法被用在安全上时,需要慢点。你计算哈希越快,暴力破解的可能性越高。不幸的是,慢到1990和2000还不足够。这些哈希算法设计者可能已经通过摩尔定律预测了CPU增长能力,但他们几乎肯定没有想到GPU计算能力增长的是如此的快。

到底有多快?好吧,让我们来比较下安装hashcat的CPU和安装oclHashcat的GPU的在计算MD5哈希算法情况:

>Radeon 7970        8213.6 M c/s

>6-core AMD CPU     52.9 M c/s 

单个现在的GPU视频卡每秒产生哈希计算量是现在CPU150倍还多,如果摩尔定律预测每18个月计算能力增加一倍,这就像我们看到了10年后的情形,相当惊人的东西,不是吗?

哈希算法与密码

让我们谈谈密码,因为哈希和密码是密切关联着的。除非你存储密码的方式不正确,否则你总是以Salt后的哈希码来存储,从来不是明文,是吗?对不对呢?这就意味着如果你的包含这些哈希码数据的数据库被攻击或泄露,用户仍然被保护——没有人能搞清楚自己的密码实际上是哈希后储在数据库中。是的,当然字典攻击可能出奇的奏效,但是我们不能阻止用户总是使用“monkey1”作为他们的密码。总之,用户选择蹩脚密码的真正解决方案不是让用户记住繁杂冗长的密码,而是干脆不要密码

这就导致了密码哈希的一个倒霉的衍生物:很少这些算法是专门使用大量、常用的高能力GPU设计的。这里有我在我现在使用的PC上测试的结果,我的电脑有2个ATI Radeon 7970卡,用MD5可产生大约16000Mc/s。我使用一个包含所有普通美式键盘的oclHashcat-lite——也就是说,包含大写、小写、数字和所有可能的字符:

all 6 character password MD5s 47 seconds
all 7 character password MD5s 1 hour, 14 minutes
all 8 character password MD5s ~465 days
all 9 character password MD5 sfuggedaboudit

当你增加GPU时,这个可以作为很好的参考标准,因此当你在一个机器上插入4个视频卡的时候你可以把这个时间缩短一半。这个也许听起来很疯狂,但是爱好者们已经在2008年做了实验。你可以再缩短一半时间,通过在另一台机器上构建4个或者更多的视频卡,分隔攻击区间(如果你是狂热疯子或者为NSA工作,那就再继续)。现在产生所有8位MD5码时间减少到差不多合理的117天,但也许这是个最坏的场景,多数的密码没有特殊字符,如果我们仅使用大写、小写和数字尝试相同的事情,又会是怎样的呢?

all 6 character password MD5s 3 seconds
all 7 character password MD5s 4 minutes
all 8 character password MD5s 4 hours
all 9 character password MD5s 10 days
all 10 character password MD5s ~625 days
all 11 character password MD5s fuggedaboudit

一个12位全小写字符密码在PC上大约需要75天就能破解,如果你对这些最坏的场景好奇,你可以自己试试;下面就是我使用的脚本:

set BIN=oclHashcat-lite64
set OPTS=--gpu-accel 200 --gpu-watchdog 0 --outfile-watch 0 --restore-timer 0 --pw-min 6 --pw-max 6 --custom-charset1 ?l?d?s?u
%BIN% %OPTS% --hash-type 0 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ?1?1?1?1?1?1?1?1?1?1?1?1?1

仅仅适当修改pw-min, pw-max和custom-charset。或者,如果你懒得自己试一试,通过浏览别人运行的的oclHashcat记录。这同样也能给你一些想法——通过GPU验证每个哈希码是代价如此的昂贵。如下所示:

MD5 23070.7 M/s
SHA-1 7973.8 M/s
SHA-256 3110.2 M/s
SHA-512 267.1 M/s
NTLM 44035.3 M/s
DES 185.1 M/s
WPA/WPA2 348.0 k/s

rainbow table如何呢?

Rainbow tables是大量的预先计算好的哈希值,权衡表为了源计算速度查找大量磁盘空间(和潜在的内存)( trading off table lookups to massive amounts of disk space (and potentially memory) for raw calculation speed)。他们现在完全过时了。人们不知道他们在做什么时将会变得烦躁。他们是在浪费时间,来听听Coda Hale的解释

Rainbow tables,尽管它们是最近流行的博客主题,但是已经是老古董了。破解密码可利用多个GPU大量的并行来实现,每秒候选密码可达到数十亿。你可以在不到2秒时间内测试不大于7个的所有小写字母密码。现在你也能租到约3$/小时的设备。如果是大约300$/小时的设备,你可以每秒破解大约500,000,000,000候选密码。

鉴于这种大规模的加密袭击经济学的转移,破解一个没有使用salt加密的对象而浪费TB级的磁盘空间没有任何意义。仅仅破解密码容易的多,即使一个好的SHA256哈希方案面对这些廉价有效的攻击依然是很脆弱的。

当我保存密码时我使用Salt算法,因此这些对我都没用

嘿,太棒了,你真是太聪明了,不仅使用了哈希,同时Salt哈希,恭喜你!

$saltedpassword = sha1(SALT . $password);

我知道你在想什么,“我可以隐藏Salt,因此攻击者不可能知道!”你当然可以试试,你可以把Salt放置在某个地方,例如放在另一个数据库中,或者放在配置文件中,或者一些具有额外保护层的安全设备中。在攻击事件中,攻击者获取哈希加密密码的数据库,但是不知何故或者没有Salt知识不能访问,理论上是可能的!

这将提供比任何实际安全的错觉,因为你既需要Salt也需要选择一个哈希算法来产生哈希码,并进行检查,一个攻击者有一个就会有另一个的。如果你已经泄露你的数据库密码,那么有理由假设他们同样有或者能得到你的秘密,隐藏Salt。

安全的第一准侧是始终做好最坏的打算,你为每个用户准备了一个随机Salt吗?当然,这是一个不错的做法,它至少可以混淆两个用户拥有相同的密码,但是现在,如果一个人愿意在视频卡硬件上花费几千元,单独的Salt算法已无法再救你,如果你认为他们能这么做,那么你就有麻烦了!

我太忙了以至于不能看完这些

如果你是一个用户:

确保你的密码为12位或者更多 最好更多. 我建议使用密码短语,它不仅比密码更容易记住,同时相对于仅根据长度进行暴力破解更安全些。

如果你是一名开发人员:

使用bcrypt或者PBKDF2专门哈希所有你需要保密的东西。 这些新的哈希算法是特意设计的,使用GPU破解还是有困难的。不要使用其他形式的哈希,因为GPU一年比一年快、并行度越来越高、更易于编程,几乎每一个其他流行的哈希方案很容易被一组普通GPU暴力破解。