什么时候使用破坏的哈希函数是安全的？

Question

使用像SHA-256这样的安全散列函数是微不足道的,并且继续使用MD5来实现安全性是鲁莽的行为.但是,我希望更好地理解哈希函数漏洞的一些复杂性.

已经为MD4和MD5生成了碰撞.根据NIST,MD5不是安全散列函数.生成冲突只需要2 ^39次操作,绝不能用于密码.然而,SHA-1很容易受到类似的碰撞攻击,其中可以在2 ^69次操作中发现碰撞,而蛮力是2 ⁸⁰.没有人生成SHA-1冲突,NIST仍然将SHA-1列为安全消息摘要功能.

那么什么时候使用破坏的哈希函数是安全的呢？即使功能被破坏,它仍然可以"足够大".根据Schneier的说法,易受冲突攻击的哈希函数仍然可以用作HMAC.我相信这是因为HMAC的安全性取决于其密钥,并且在获得此密钥之前无法找到冲突.一旦你在HMAC中使用了密钥,它就已经坏了,所以这是一个没有实际意义的问题.哈希函数漏洞会破坏HMAC的安全性？

让我们进一步了解这个属性.如果密码前面加盐,那么使用像MD4这样的非常弱的消息摘要是否可以安全地使用密码？请记住,MD4和MD5攻击是攻击前缀,如果预先添加了盐,则攻击者无法控制消息的前缀.如果盐真的是一个秘密,并且攻击者不知道,那么它是否附加在密码上是否重要？假设攻击者在获得整个消息之前无法生成冲突,这是否安全？

您是否知道在不引入漏洞的情况下可以在安全上下文中使用损坏的哈希函数的其他情况？

(请发布支持证据,因为它很棒!)

Answer 1

实际上,碰撞比在MD5和SHA-1上列出的更容易.可以在相当于2 ^26.5操作的时间内找到MD5冲突(其中一个"操作"是通过短消息计算MD5).有关详细信息和攻击的实现,请参阅此页面(我编写了该代码;它在64位模式下的2.4 GHz Core2 x86上发现平均14秒内发生冲突).

同样,对SHA-1的最着名的攻击是大约2 ^61次操作,而不是2 ^69次.它仍然是理论上的(尚未产生实际碰撞)但它在可行范围内.

至于对安全性的影响:哈希函数通常被认为具有三个属性:

• 没有preimage:给定y,找到x使得h(x)= y是不可行的.
• 没有第二个原像:给定x ₁,找到x ₂(不同于x ₁)使得h(x ₁)= h(x ₂)是不可行的.
• 没有碰撞:找到任何x ₁和x ₂(彼此不同)使得h(x ₁)= h(x ₂)是不可行的.

对于具有n位输出的散列函数,对于两个第一属性,在2 ^n个操作中存在通用攻击(无论散列函数的细节如何工作),对于第三个属性,存在2 ^n/2个操作.如果对于给定的散列函数,发现攻击,通过利用散列函数如何操作的特殊细节,找到比相应的通用攻击更快的原像,第二个原像或碰撞,那么哈希函数被称为被"打破".

但是,并非所有哈希函数的使用都依赖于所有三个属性.例如,数字签名首先散列要签名的数据,然后在算法的其余部分中使用散列值.这取决于对预成像和第二预成像的抵抗力,但数字签名本身并不受碰撞的影响.在某些特定的签名方案中,冲突可能是一个问题,攻击者可以选择要由受害者签名的数据(基本上,攻击者计算冲突,有一条消息由受害者签名,签名变为有效另一条消息).这可以通过在计算签名(在X.509证书的上下文中演示的攻击和解决方案)之前将一些随机字节预先添加到签名消息来抵消.

HMAC安全性依赖于散列函数必须满足的其他属性; 即,"压缩函数"(构建散列函数的基本砖)用作伪随机函数(PRF).有关PRF的详细信息是非常技术性的,但是,粗略地说,PRF应该与a无法区分 Random Oracle.一个随机的oracle被建模为一个黑盒子,其中包含一个侏儒,一些骰子和一本大书.在一些输入数据上,gnome选择一个随机输出(带有骰子)并在书中记下输入消息和随机选择的输出.gnome使用这本书检查他是否已经看到相同的输入消息:如果是,那么gnome返回的输出数量与之前相同.通过构造,您可以对给定消息上的随机oracle的输出一无所知,直到您尝试它为止.

随机oracle模型允许在PRF的调用中量化HMAC安全证明.基本上,证据表明HMAC不能在没有多次调用PRF的情况下被破坏,并且"巨大"我的意思是计算上不可行.

不幸的是,我们没有随机的神谕,所以在实践中我们必须使用散列函数.没有证据表明哈希函数确实存在,具有PRF属性; 现在,我们只有候选者,即我们无法证明他们的压缩函数不是PRF的函数.

如果压缩函数是PRF,则散列函数自动抵抗冲突.这是PRF魔力的一部分.因此,如果我们可以找到哈希函数的冲突,那么我们就知道内部压缩函数不是PRF.这不会将碰撞变成对HMAC的攻击.能够随意产生碰撞并没有帮助打破HMAC.但是,这些冲突表明与HMAC相关的安全证明不适用.保证无效.这与笔记本电脑完全相同:打开机壳并不一定会破坏机器,但之后你就自己动手了.

在Kim-Biryukov-Preneel-Hong文章中,提出了一些针对HMAC的攻击,特别是对HMAC-MD4的伪造攻击.该攻击利用了MD4(其"弱点")的缺点,使其成为非PRF.具有相同弱点的变体用于在MD4上产生冲突(MD4彻底破坏;一些攻击比哈希函数本身的计算更快地产生冲突!).因此,碰撞并不意味着HMAC攻击,但两种攻击都依赖于同一来源.但请注意,伪造攻击的成本为2 ⁵⁸,这是非常高的(没有产生实际的伪造,结果仍然是理论上的)但是远远低于HMAC预期的阻力水平(具有强大的哈希函数和 n)比特输出,HMAC应该抵抗高达2 ^n的工作因子; 对于MD4,n = 128).

因此,虽然碰撞本身并不意味着对HMAC的弱点,但它们都是坏消息.实际上,碰撞是很少设置的问题.但是知道冲突是否影响给定的散列函数使用是很棘手的,继续使用散列函数来证明碰撞是非常不明智的.

对于SHA-1,攻击仍然是理论上的,并且SHA-1被广泛部署.这种情况的描述如下:"警报已开启,但没有明显的火灾或烟雾.现在是时候走向出口 - 但不要跑."

有关该主题的更多信息,请首先阅读Menezes,van Oorschot和Vanstone 的应用密码学手册第9章,这是学徒密码学家必读的内容(不要与B. Schneier的"应用密码学"混淆) ,这是一本写得很好的介绍,但没有像"手册"那样彻底.