delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

29 Jan 2010

用户口令的验证问题

口令是许多系统中用于判断用户身份的重要手段。当然,使用口令作为身份验证方法是很不靠谱的(例如,许多用户会使用弱口令,或者在多个系统中使用同样的口令,以及它存在对称失密问题,等等),不过因为口令便于携带(相对于私钥)和实现,因此仍然被广泛使用。

验证用户口令有很多种不同的方法。最原始的方法,就是将用户输入的口令与我们保存的口令相比较,如果相同,就认为是验证通过。但是这样一来,我们就必须保存用户的口令,而保存用户的口令会导致很多问题,例如,假如系统用于保存口令的数据库被攻陷,直接泄露用户的明文口令肯定不是一件好事。

于是,我们可以对前面的方法进行改进,即,只保存用户口令的散列(hash)字符串,而不是口令的明文。散列算法是一种单向的计算,即散列函数 H 对明文信息 p 计算出的结果 h:

H(p) = h

从 p 根据 H 推算出 h 需要的计算工作很容易完成,而通过 h 则很难推出 p(一般来说,散列算法生成的输出结果是固定长度的,因此这个过程几乎一定会导致熵的减少,从而使 h 中包含的信息少于 p)。安全的散列算法还需要提供一些其他的特性,例如"雪崩效应(Avalanche effect)",即明文信息p中哪怕仅仅改变1个bit,也会导致输出的h中多个bit的变化;输出的散列值均匀分布,等等。目前比较常用的安全散列算法是SHA2。

不过,仅仅使用散列算法来处理字符串并不能解决所有的问题。随着计算技术,特别是分布式计算和存储技术的不断发展,使得产生某种散列算法每一种散列输出,并保存一个可能的、与之对应的输入变得越来越容易。例如,SHA256 ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad对应的一个可能的字符串是abc,如果我们只保存密码的hash数据的话,攻击者遇到ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad时,无论用户真正的密码为何,便总可以使用等效字符串"abc"来进入系统。

挫败这种攻击的方法是使用一个额外的随机串,并且在保存密码时,每次都生成一个新的随机串,将其以明文方式和散列串放在一起。例如,在保存密码时随机生成的随机串是hFaSV2,我们便把它和用户的密码abc连在一起去计算散列值,即,SHA256 (“hFaSV2abc”) = 31945b4ad715f72214a8c84a3b63aa5aecf3ba9419a7687d90351da4d525d1fa,保存的时候可以写成$hFaSV$31945b4ad715f72214a8c84a3b63aa5aecf3ba9419a7687d90351da4d525d1fa$,这样在用户再次输入密码时,便可以配合这个串来进行验证。由于我们的随机串对每一个用户而言都不一样,攻击者就没有办法通过查找事先计算的字典来得到等价的字符串了。

然而,近几年的密码学研究成果还增加了另外一种形式的攻击,即,某些算法在有一部分已知明文的时候,可以以较低的代价推算出能够得到等价散列串的其他字符串。因此,前面的方法还需要进行进一步的改进。除了使用更好的散列算法之外,还可以通过多次散列得到的反馈来提高推算等价串的代价,也就是说,原先的系统中,我们计算的是:

H'(s, p) = H(s + p) = h

而改进的系统中,我们计算的则是:

H''(s, p) = H(H(s + p) + s+p) = h

上面的方法可以做多轮以加强效果,这里,我们将散列得到的信息以一定的方式反馈到散列函数的输入中。这样做的结果是,攻击者虽然了解我们生成的随机串 s,以及最后的结果p,但却没有很好的办法去推算我们在计算过程中使用的中间结果H(s+p)。这种做法可以挫败一整类这样的攻击。

在 *BSD 和 Linux 中的密码文件里所使用的 MD5 就是采用这样的方法,其实现中将散列串的输出结果以及原字符串不断地以输入的形式反馈到散列函数中,从而达到提高攻击门槛的目的。


Archived: 2 Comments

文化人 | February 20, 2010 3:47 PM

菜咸了,可以加生土豆片儿吸盐.

sp55aa.org | March 7, 2010 2:06 AM

记得OpenBSD里面的口令加密算法用john去破解时效率非常低, 速度是普通MD5的几百分之一, 难道也是进行了很多次的hash?