什么时候使用损坏的哈希函数是安全的? [英] When is it safe to use a broken hash function?

问题描述

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

It is trivial to use a secure hash function like SHA-256, and continuing to use MD5 for security is reckless behavior. However, there are some complexities to hash function vulnerabilities that I would like to better understand.

冲突已 为 MD4 和 MD5 生成.根据 NIST，MD5 不是一个安全的散列函数.只需 2³⁹ 次操作即可生成碰撞和绝不应用于密码.然而，SHA-1 容易受到类似的碰撞攻击的攻击，在这种攻击中可以发现碰撞在 2⁶⁹ 操作中，而蛮力是 2⁸⁰.没有人产生 SHA-1 冲突，NIST 仍然将 SHA-1 列为安全消息摘要功能.

Collisions have been generated for MD4 and MD5. According to NIST, MD5 is not a secure hash function. It only takes 2³⁹ operations to generate a collision and should never be used for passwords. However SHA-1 is vulnerable to a similar collision attack in which a collision can be found in 2⁶⁹ operations, whereas brute force is 2⁸⁰. No one has generated a SHA-1 collision and NIST still lists SHA-1 as a secure message digest function.

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

So when is it safe to use a broken hash function? Even though a function is broken it can still be "big enough". According to Schneier a hash function vulnerable to a collision attack can still be used as an HMAC. I believe this is because the security of an HMAC is dependent on its secret key and a collision cannot be found until this key is obtained. Once you have the key used in an HMAC it's already broken, so it's a moot point. What hash function vulnerabilities would undermine the security of an HMAC?

让我们更进一步地了解这个属性.如果在密码前加上盐，那么使用非常弱的消息摘要(如 MD4)作为密码是否会变得安全?请记住，MD4 和 MD5 攻击是前缀攻击，如果添加了盐，那么攻击者将无法控制消息的前缀.如果盐确实是一个秘密，并且攻击者不知道，那么是否将它附加到密码中是否重要?假设攻击者在获得整个消息之前无法产生冲突是否安全?

Let's take this property a bit further. Does it then become safe to use a very weak message digest like MD4 for passwords if a salt is prepended to the password? Keep in mind the MD4 and MD5 attacks are prefixing attacks, and if a salt is prepended then an attacker cannot control the prefix of the message. If the salt is truly a secret, and isn't known to the attacker, then does it matter if it's appended to the password? Is it safe to assume that an attacker cannot generate a collision until the entire message has been obtained?

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

Do you know of other cases where a broken hash function can be used in a security context without introducing a vulnerability?

(请发布支持证据，因为它很棒！)

(Please post supporting evidence because it is awesome!)

推荐答案

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

Actually collisions are easier than what you list on both MD5 and SHA-1. MD5 collisions can be found in time equivalent to 2^26.5 operation (where one "operation" is the computation of MD5 over a short message). See this page for some details and an implementation of the attack (I wrote that code; it finds a collision within an average of 14 seconds on a 2.4 GHz Core2 x86 in 64-bit mode).

同样，对 SHA-1 最著名的攻击是大约 2⁶¹ 次操作，而不是 2⁶⁹.它仍然是理论上的(还没有产生实际的碰撞)，但它在可行的范围内.

Similarly, the best known attack on SHA-1 is in about 2⁶¹ operations, not 2⁶⁹. It is still theoretical (no actual collision was produced yet) but it is within the realm of the feasible.

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

As for implications on security: hash functions are usually said to have three properties:

• 无原像:给定 y，找到 x 使得 h(x) = y 应该是不可行的.
• 没有第二个原像:给定 x₁，找到 x₂ 应该是不可行的(不同从 x₁) 使得 h(x₁) = h(x₂).
• 没有冲突:找到任何 x₁ 和 x₂ 应该是不可行的(区别于彼此)使得 h(x₁) = h(x₂).

• No preimage: given y, it should not be feasible to find x such that h(x) = y.
• No second preimage: given x₁, it should not be feasible to find x₂ (distinct from x₁) such that h(x₁) = h(x₂).
• No collision: it should not be feasible to find any x₁ and x₂ (distinct from each other) such that h(x₁) = h(x₂).

对于具有 n 位输出的散列函数，在 2ⁿ 中存在通用攻击(无论散列函数的细节如何都有效) 对前两个属性进行操作，对第三个属性进行 2^n/2 操作.如果对于给定的散列函数，发现攻击，通过利用散列函数如何操作的特殊细节，比相应的通用攻击更快地找到原像、第二原像或冲突，则称散列函数为被打破".

For a hash function with a n-bit output, there are generic attacks (which work regardless of the details of the hash function) in 2ⁿ operations for the two first properties, and 2^n/2 operations for the third. If, for a given hash function, an attack is found, which, by exploiting special details of how the hash function operates, finds a preimage, a second preimage or a collision faster than the corresponding generic attack, then the hash function is said to be "broken".

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

However, not all usages of hash functions rely on all three properties. For instance, digital signatures begin by hashing the data which is to be signed, and then the hash value is used in the rest of the algorithm. This relies on the resistance to preimages and second preimages, but digital signatures are not, per se, impacted by collisions. Collisions may be a problem in some specific signature scenarios, where the attacker gets to choose the data that is to be signed by the victim (basically, the attacker computes a collision, has one message signed by the victim, and the signature becomes valid for the other message as well). This can be counteracted by prepending some random bytes to the signed message before computing the signature (the attack and the solution where demonstrated in the context of X.509 certificates).

HMAC 安全性依赖于散列函数必须满足的 other 属性；即，压缩函数"(构建散列函数的基本块)充当伪随机函数(PRF).关于什么是 PRF 的详细信息是相当技术性的，但粗略地说，PRF 应该与 Random Oracle 没有区别.随机预言机被建模为一个黑匣子，其中包含一个侏儒、一些骰子和一本大书.在一些输入数据上，gnome 选择一个随机输出(用骰子)并在书中写下输入消息和随机选择的输出.gnome 使用这本书检查他是否已经看到相同的输入消息:如果是，则 gnome 返回与以前相同的输出.通过构造，在您尝试之前，您可能对给定消息上的随机预言机的输出一无所知.

HMAC security relies on an other property that the hash function must fulfill; namely, that the "compression function" (the elementary brick on which the hash function is built) acts as a Pseudo-Random Function (PRF). Details on what a PRF is are quite technical, but, roughly speaking, a PRF should be indistinguishable from a Random Oracle. A random oracle is modeled as a black box which contains a gnome, some dice and a big book. On some input data, the gnome select a random output (with the dice) and writes down in the book the input message and the output which was randomly selected. The gnome uses the book to check whether he already saw the same input message: if so, then the gnome returns the same output than previously. By construction, you can know nothing about the output of a random oracle on a given message until you try it.

随机预言机模型允许在 PRF 的调用中量化 HMAC 安全证明.基本上，证明表明如果不大量调用 PRF 就无法破坏 HMAC，而巨大"是指计算上不可行的.

The random oracle model allows the HMAC security proof to be quantified in invocations of the PRF. Basically, the proof states that HMAC cannot be broken without invoking the PRF a huge number of times, and by "huge" I mean computationally infeasible.

不幸的是，我们没有随机预言机，所以在实践中我们必须使用哈希函数.没有证据证明散列函数确实存在，具有 PRF 属性；目前，我们只有候选函数，即我们无法证明(还)它们的压缩函数不是 PRF 的函数.

Unfortunately, we do not have random oracles, so in practice we must use hash functions. There is no proof that hash functions really exist, with the PRF property; right now, we only have candidates, i.e. functions for which we cannot prove (yet) that their compression functions are not PRF.

如果压缩函数是一个PRF那么哈希函数会自动抵抗冲突.这就是 PRF 的魅力所在.因此，如果我们可以找到哈希函数的冲突，那么我们知道内部压缩函数不是 PRF.这不会将冲突转变为对 HMAC 的攻击.能够随意产生冲突无助于破坏 HMAC.但是，这些冲突表明与 HMAC 相关的安全证明不适用.保证无效.这与笔记本电脑一样:打开机箱不一定会损坏机器，但之后您就得靠自己了.

If the compression function is a PRF then the hash function is automatically resistant to collisions. That's part of the magic of PRF. Therefore, if we can find collisions for a hash function, then we know that the internal compression function is not a PRF. This does not turn the collisions into an attack on HMAC. Being able to generate collisions at will does not help in breaking HMAC. However, those collisions demonstrate that the security proof associated with HMAC does not apply. The guarantee is void. That's just the same than a laptop computer: opening the case does not necessarily break the machine, but afterwards you are on your own.

在 Kim-Biryukov-Preneel-Hong 文章中，对 HMAC 的一些攻击是提出，特别是对 HMAC-MD4 的伪造攻击.该攻击利用了 MD4 的缺点(它的弱点")，使其成为非 PRF.具有相同弱点的变体被用于在 MD4 上产生冲突(MD4 被彻底破坏；一些攻击产生的冲突比哈希函数本身的计算更快！).因此，冲突并不意味着 HMAC 攻击，但两种攻击都以相同的源为食.但是请注意，伪造攻击的成本是 2⁵⁸，这是相当高的(没有产生实际的伪造，结果仍然是理论上的)但远低于抵抗力HMAC 的预期水平(具有 n 位输出的稳健散列函数，HMAC 应能抵抗高达 2ⁿ 的工作因子；n = 128 对于 MD4).

In the Kim-Biryukov-Preneel-Hong article, some attacks on HMAC are presented, in particular a forgery attack on HMAC-MD4. The attack exploits the shortcomings of MD4 (its "weaknesses") which make it a non-PRF. Variants of the same weaknesses were used to generate collisions on MD4 (MD4 is thoroughly broken; some attacks generate collisions faster than the computation of the hash function itself !). So the collisions do not imply the HMAC attack, but both attacks feed on the same source. Note, though, that the forgery attack has cost 2⁵⁸, which is quite high (no actual forgery was produced, the result is still theoretical) but substantially lower than the resistance level expected from HMAC (with a robust hash function with an n-bit output, HMAC should resist up to 2ⁿ work factor; n = 128 for MD4).

因此，虽然冲突本身并不意味着 HMAC 的弱点，但它们是个坏消息.在实践中，碰撞对于很少的设置来说是一个问题.但是要知道冲突是否会影响哈希函数的给定用法已经够棘手了，继续使用已经证明有冲突的哈希函数是非常不明智的.

So, while collisions do not per se imply weaknesses on HMAC, they are bad news. In practice, collisions are a problem for very few setups. But knowing whether collisions impact a given usage of hash functions is tricky enough, that it is quite unwise to keep on using a hash function for which collisions were demonstrated.

对于 SHA-1，攻击仍然是理论上的，SHA-1 被广泛部署.这种情况是这样描述的:警报响起，但没有可见的火或烟雾.是时候向出口走去——但不要跑."

For SHA-1, the attack is still theoretical, and SHA-1 is widely deployed. The situation has been described like this: "The alarm is on, but there is no visible fire or smoke. It is time to walk towards the exits -- but not to run."

有关该主题的更多信息，请先阅读 Handbook of Applied Cryptography 的第 9 章，由 Menezes、van Oorschot 和 Vanstone 合着，密码学学徒必读(不要与 B. Schneier 的应用密码学"相混淆，这是一个写得很好的介绍，但远不如手册").

For more information on the subject, begin by reading the chapter 9 of the Handbook of Applied Cryptography, by Menezes, van Oorschot and Vanstone, a must-read for the apprentice cryptographer (not to be confused with "Applied Cryptography" by B. Schneier, which is a well-written introduction but nowhere as thorough as the "Handbook").

这篇关于什么时候使用损坏的哈希函数是安全的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！