什么时候安全使用破碎的散列函数？ [英] When is it safe to use a broken hash function?

问题描述

使用像SHA256这样的安全哈希函数是很容易的，并且继续使用md5来保证安全性是鲁莽的行为。然而，有一些复杂的哈希函数漏洞，我想更好地了解。

冲突已经 2 ^ 39次操作生成冲突，且永远不应用于密码。但是，SHA1很容易受到可发现冲突的类似冲突攻击在2 ^ 69操作，而蛮力是2 ^ 80th。没有人生成sha1冲突， NIST仍将sha1列为安全消息摘要函数。

那么什么时候安全使用破碎的散列函数呢？即使一个函数被破坏，它仍然可以是足够大。 根据Schneier ，易受攻击攻击的哈希函数可以仍然用作 HMAC 。我相信这是因为HMAC的安全性取决于其密钥，并且在获得该密钥之前不能发现冲突。一旦你使用的密钥在HMAC它已经破碎，所以这是一个疑问点。什么哈希函数漏洞会破坏HMAC的安全性？

让我们更进一步了解这个属性。如果密码前面有一个盐，那么使用一个非常弱的消息摘要（如md4）作为密码是否安全？请记住md4和md5攻击是前缀攻击，如果一个盐是前置的，那么攻击者不能控制消息的前缀。如果盐真的是一个秘密，并且攻击者不知道，那么它是否重要，如果它附加到密码？是否可以假设攻击者在获得整个消息之前不能产生冲突？

您知道其他情况下，破坏的散列函数可以在安全上下文中使用，而不会引入漏洞？

（请提供支持证据，因为它太棒了！）

解决方案

实际碰撞比在MD5和SHA-1上列出的碰撞更容易。可以在等效于 2 ^26.5 操作的时间中找到MD5冲突（其中一个操作是对短消息的MD5的计算）。有关详细信息，请参见此页和攻击的实现（我写的代码;它发现在平均14秒内在2.4 GHz的Core2 x86在64位模式下的冲突）。

类似地，对SHA-1最好的已知攻击是在 2 ⁶¹ 操作中，而不是 2 ⁶⁹ 。它仍然是理论的（没有产生实际的碰撞），但它是在可行的范围内。

对安全的影响：哈希函数通常被称为三个属性：

• 没有preimage：给定 y ，不可能找到，以便 h（x）= y 。


• 没有第二个preimage：给定 x ₁ >，则不可能找到 x ₂ （不同于 x ₁


• 没有冲突：它不应该是可行的找到任何 x ₁ 和 x ₂ sub> 1 ）= h（x <2>）
。

具有 n 位输出的散列函数，在 2 ⁿ 中有通用攻击（其工作与散列函数的细节无关）两个第一属性的操作，以及第三个的 2 ^{n / 2} 操作。如果对于给定的散列函数，找到攻击，通过利用散列函数如何操作的特殊细节，找到比相应的通用攻击更快的前像，第二前像或碰撞，则散列函数被称为bebroken。

但是，并非所有散列函数的使用都依赖于所有三个属性。例如，数字签名通过散列要签名的数据开始，然后在算法的其余部分中使用散列值。这依赖于对预图像和第二预图像的抵抗，但是数字签名本身不受冲突的影响。在某些特定签名情况下，冲突可能是一个问题，攻击者可以选择要由受害者签名的数据（基本上，攻击者计算冲突，有一个消息由受害者签名，签名变为有效其他消息）。这可以通过在计算签名之前（在X.509证书的上下文中展示的攻击和解决方案）将一些随机字节前缀到已签名的消息来抵消。

HMAC安全性依赖于散列函数必须满足的其他属性;即，压缩函数（其上构建了散列函数的基本砖）充当伪随机函数（PRF）。关于什么是PRF的细节是相当技术性的，但是，大体来说，PRF应该与< em>随机Oracle 不可区分。一个随机的oracle被建模为一个黑盒子，包含一个gnome，一些骰子和一本大书。在一些输入数据上，gnome选择随机输出（用骰子），并在书中写入输入消息和随机选择的输出。 gnome使用这本书来检查他是否已经看到相同的输入消息：如果是这样，那么gnome返回与以前相同的输出。通过构建，您可以在给定的消息上一个随机的oracle的输出没有任何知识，直到您尝试它。

随机的oracle模型允许HMAC安全证明被量化在PRF的调用。基本上，证明表明HMAC不能在没有调用PRF的情况下被破坏大量的次数，而巨大的意味着计算上不可行。

不幸的是，有随机的oracle，所以在实践中我们必须使用哈希函数。没有证据表明哈希函数真正存在，具有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 ⁿ 工作因子; > 对于MD4而言，这是非常不利的。）

因此，虽然冲突本身并不影响HMAC的弱点，新闻。在实践中，碰撞对于很少的设置是个问题。但是，知道碰撞是否会影响给定的哈希函数的使用是非常棘手的，继续使用已证明碰撞的哈希函数是非常不明智的。

对于SHA -1，攻击仍然是理论上的，SHA-1被广泛部署。情况已经这样描述：报警，但没有明显的火或烟，是时候走向出口 - 但不是运行。

有关此主题的详情，请先阅读手册应用密码学，Menezes，van Oorschot和Vanstone，这是一个学徒密码学家的必读书（不要与B. Schneier的应用密码学混淆，这是一个写得很好的介绍，但没有那么详尽手册）。

It is trivial to use a secure hash function like SHA256, 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.

Collisions have been generated for md4 and md5. According to NIST, md5() is not a secure hash function. It only takes 2^39th operations to generate a collision and should never be used for passwords. However SHA1 is vulnerable to a similar collision attack in which a collision can be found in 2^69 operations, whereas brute force is 2^80th. No one has generated a sha1 collision and NIST still lists sha1 as a secure message digest function.

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 collsion 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?

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!)

解决方案

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).

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:

• 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₂).

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".

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 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.

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.

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.

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.

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).

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.

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."

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屋！