破碎哈希函数何时使用是安全的？

Question

使用安全哈希函数（例如SHA-256）是非常简单的，而继续使用MD5来保证安全性则是不负责任的行为。然而，哈希函数漏洞中存在一些复杂性，我希望能更好地理解。

已经生成了MD4和MD5的碰撞。根据NIST的说法，MD5不是安全的哈希函数。只需2¹⁹次操作即可生成碰撞，不应该用于密码。然而，SHA-1也容易受到类似的碰撞攻击，其中2^69次操作就可以找到碰撞，而暴力破解需要2^80次。目前尚未产生 SHA-1 碰撞，NIST 仍将 SHA-1列为安全的消息摘要函数。

那么，什么情况下使用破解的哈希函数才是安全的呢？即使一个函数被破解了，它仍然可以足够"大"。根据Schneier的说法，易受碰撞攻击的哈希函数仍可用作HMAC。我认为这是因为HMAC的安全性取决于其秘密密钥，并且在获得此密钥之前，无法找到碰撞。一旦您拥有在HMAC中使用的密钥，它已经失效了，因此这是一个无意义的点。哪些哈希函数漏洞会削弱HMAC的安全性？

让我们更深入地探讨这个属性。如果在密码前面添加盐，那么是否可以使用非常弱的消息摘要，例如MD4？请记住，MD4和MD5攻击是前缀攻击，如果添加了盐，则攻击者无法控制消息的前缀。如果盐是真正的秘密，并且攻击者不知道它，那么将其附加到密码是否重要？可以安全地假设攻击者在获取整个消息之前无法生成碰撞吗？

您是否知道其他情况下可以在安全环境中使用破解的哈希函数而不会引入漏洞？(请提供支持证据，因为它很棒！)

- rook

---

维基百科关于HMAC的文章(http://en.wikipedia.org/wiki/HMAC)称`使用完整版本的MD4可以被伪造`。这份文档(http://eprint.iacr.org/2006/187.pdf)解释了背后的数学原理，但我并不完全理解。也许你会对它感兴趣。 - Sripathi Krishnan

Answer 1

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

同样，SHA-1的最佳已知攻击需要大约2⁶¹次操作，而不是2⁶⁹。尽管还没有真正产生碰撞，但这仍然是可行的范畴。

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

- 无预像：给定y，不应易于找到x使得h(x) = y。 - 无第二预像：给定x₁，不应易于找到与x₁不同的x₂，使得h(x₁) = h(x₂)。 - 无碰撞：不应易于找到任何不同的x₁和x₂，使得h(x₁) = h(x₂)。

对于一个具有n位输出的哈希函数，对于前两个属性，存在通用攻击（无论哈希函数的具体细节如何）需要2ⁿ次操作；对于第三个属性，则需要2^n/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攻击，但两个攻击都利用相同的源。需要注意的是，伪造攻击的代价为2⁵⁸，这相当高（尽管还没有实际伪造产生，结果仍然是理论性的），但远低于预期从HMAC获得的抵抗级别（使用具有n位输出的强大哈希函数，HMAC应该抵抗2ⁿ的工作复杂度； 对于MD4，n = 128）。

因此，虽然碰撞并不per se影响HMAC的弱点，但它们是个坏消息。在实践中，碰撞只会影响极少数的设置。但是，要知道碰撞是否会影响散列函数的给定用法非常棘手，因此继续使用已经证明存在碰撞的哈希函数是相当不明智的。

对于SHA-1，攻击仍然是理论性的，而且SHA-1被广泛使用。情况被描述为：“警报已经响起，但没有看到火灾或烟雾。现在是走向出口的时候——但不是奔跑。”

有关此问题的更多信息，请先阅读Menezes、van Oorschot和Vanstone的应用密码学手册第9章，这是学徒加密学家必须阅读的内容（不要与B. Schneier的“应用密码学”混淆，它是一本写得很好的介绍书，但远不如“手册”全面）。

- Thomas Pornin

---

你的惊人回答已经完美地回答了我所有问题。 - rook

Answer 2

只有在碰撞的后果无害或微不足道时，例如将文件分配到文件系统上的桶中时，才可以安全使用破碎的哈希函数。

- Ignacio Vazquez-Abrams

---

+1 我的一些支持证据与你的陈述相矛盾，但没关系。 - rook

Answer 3

当你不关心它是否安全时。

说真的，在几乎所有的编程语言中使用安全哈希函数并不需要额外的努力，而且性能影响可以忽略不计，所以我不明白为什么你不会这样做。

[实际阅读了您的问题后编辑]

根据Schneier的说法，一个容易受到碰撞攻击的哈希函数仍然可以用作HMAC。我认为这是因为HMAC的安全性取决于其秘密密钥，只有在获得此密钥之后才能找到碰撞。

实际上，这主要是因为能够为哈希生成碰撞不一定会帮助您为哈希的哈希（与HMAC使用的异或结合）生成碰撞。

那么，如果在密码前面放置盐，是否可以使用非常弱的消息摘要（例如md4）来进行密码保护？

不行，除非哈希具有预像攻击，允许您在输入前面添加数据。例如，如果哈希是H（pass + salt），我们需要一种预像攻击，使我们能够找到pass2，使得H（pass2 + salt）= H（pass + salt）。

过去曾经发生过后缀攻击，所以我相信前缀攻击也是可能的。

- BlueRaja - Danny Pflughoeft

Answer 4

下载站使用MD5哈希作为校验和，以确定文件在下载过程中是否损坏。我认为，破碎的哈希对于此目的已经足够好了。

假设一个中间人攻击者决定修改文件（例如zip归档文件或exe文件）。现在，攻击者必须完成两件事情：

1. 找到哈希碰撞并创建一个修改后的文件。 2. 确保新创建的文件也是有效的exe或zip归档文件。

使用破碎的哈希，第一步会更容易些。但同时确保碰撞满足文件的其他已知属性则需要更高的计算成本。

这是完全基于我的个人理解，我可能是完全错误的。

- Sripathi Krishnan

---

如果你已经看到这些哈希值是如何存储在服务器上的，那么如果你有文件共享的写入权限，你就可以更改哈希值并完成它。 - Jason

Answer 5

答案完全取决于你使用它的用途。如果你需要防止某人在几毫秒内产生碰撞，我会比需要防止某人在几十年内产生碰撞更不担心。

你实际上要解决什么问题？

- Alun Harford

---

我正在尝试解决更好地理解消息摘要函数的问题。 - rook

Answer 6

使用MD4之类的密码时，大部分担忧与当前已知攻击的关系较小，而更多地与一旦被分析到碰撞生成变得容易的程度，通常被认为相当可能有人能够利用这些知识来创建预像攻击有关。如果发生这种情况，基本上该哈希函数的所有可能用途都会变得容易受到攻击。

- Jerry Coffin