实际上,对于MD5和SHA-1来说,碰撞比你列出的更容易。可以在等效于
226.5次操作的时间内(其中一次“操作”是计算MD5短消息的处理)找到MD5碰撞。有关详细信息和攻击实现,请参见
此页面(我编写了该代码;在64位模式下的2.4 GHz Core2 x86上,它平均可以在14秒内找到一个碰撞)。
同样,SHA-1的最佳已知攻击需要大约
261次操作,而不是
269。尽管还没有真正产生碰撞,但这仍然是可行的范畴。
至于对安全性的影响:哈希函数通常具有三个属性:
- 无预像:给定
y,不应易于找到
x使得
h(x) = y。
- 无第二预像:给定
x1,不应易于找到与
x1不同的
x2,使得
h(x1) = h(x2)。
- 无碰撞:不应易于找到任何不同的
x1和
x2,使得
h(x1) = h(x2)。
对于一个具有
n位输出的哈希函数,对于前两个属性,存在通用攻击(无论哈希函数的具体细节如何)需要
2n次操作;对于第三个属性,则需要
2n/2次操作。如果针对某个给定的哈希函数发现一种攻击方法,它能够利用哈希函数操作的特殊细节比相应的通用攻击更快地找到预像、第二预像或碰撞,则称该哈希函数已经“破解”。然而,并非所有哈希函数的使用都依赖于这三个属性。例如,数字签名从对待签名的数据进行哈希开始,然后哈希值在算法的其余部分中使用。这依赖于抵抗预像和第二预像,但数字签名本身不受冲突的影响。在某些特定签名场景中,攻击者可以选择由受害者签名的数据(基本上,攻击者计算出碰撞,让受害者签署一条消息,然后该签名也适用于另一条消息)。在计算签名之前,可以通过在签名消息之前添加一些随机字节来抵消此问题(攻击和解决方案在X.509证书的背景下得到证明)。
HMAC安全性依赖于哈希函数必须满足的“其他”属性;即“压缩函数”(哈希函数构建的基本模块)充当伪随机函数(PRF)。关于PRF是什么的详细信息相当技术化,但是大致上,PRF应该与随机神谕不可区分。随机神谕被建模为一个黑盒子,里面有一个小矮人、几个骰子和一本大书。对于某些输入数据,小矮人使用骰子随机选择一个输出,并在书中写下输入消息和随机选择的输出。小矮人使用书来检查他是否已经看到了同样的输入消息:如果是,那么小矮人返回与以前相同的输出。按照构造方法,你对于给定消息的随机神谕输出一无所知,直到你尝试它。
随机神谕模型允许HMAC安全证明用PRF调用量来量化。基本上,该证明表明,HMAC不能被破解而不需要调用PRF大量次数,而“大量”指的是计算上不可行的。
遗憾的是,我们没有随机神谕,因此在实践中必须使用哈希函数。目前还没有证明具有PRF属性的哈希函数确实存在;现在,我们只有候选函数,即我们不能证明(但)其压缩函数不是PRF的函数.
如果压缩函数是PRF,则哈希函数自动抵抗冲突。这是PRF的魔力的一部分。因此,如果我们能够找到哈希函数的冲突,则我们知道内部压缩函数不是PRF。这并不会将冲突变成攻击HMAC的手段。能够随意生成碰撞并不能帮助破坏HMAC。但是,这些冲突证明了与HMAC相关的安全性证明不适用。保证被破坏了。这就像一台笔记本电脑:打开机箱不一定会损坏机器,但之后你就要自己解决问题了。在
Kim-Biryukov-Preneel-Hong文章中,介绍了一些对HMAC的攻击,特别是对HMAC-MD4的伪造攻击。该攻击利用了MD4的缺陷(即其“弱点”),使其成为非PRF。同样的弱点变种被用于在MD4上生成碰撞(MD4已被彻底破解;某些攻击比哈希函数本身的计算更快地生成碰撞!)。因此,碰撞并不意味着HMAC攻击,但两个攻击都利用相同的源。需要注意的是,伪造攻击的代价为
258,这相当高(尽管还没有实际伪造产生,结果仍然是理论性的),但远低于预期从HMAC获得的抵抗级别(使用具有
n位输出的强大哈希函数,HMAC应该抵抗
2n的工作复杂度; 对于MD4,
n = 128)。
因此,虽然碰撞并不
per se影响HMAC的弱点,但它们是个坏消息。在实践中,碰撞只会影响极少数的设置。但是,要知道碰撞是否会影响散列函数的给定用法非常棘手,因此继续使用已经证明存在碰撞的哈希函数是相当不明智的。
对于SHA-1,攻击仍然是理论性的,而且SHA-1被广泛使用。情况被描述为:“警报已经响起,但没有看到火灾或烟雾。现在是走向出口的时候——但不是奔跑。”
有关此问题的更多信息,请先阅读Menezes、van Oorschot和Vanstone的
应用密码学手册第9章,这是学徒加密学家必须阅读的内容(不要与B. Schneier的“应用密码学”混淆,它是一本写得很好的介绍书,但远不如“手册”全面)。