对哈希而言“安全”意味着什么

任何将输入映射为固定大小输出的函数，最终都会把两个不同的输入映射到同一个输出，因为输入有无穷多个而输出只有有限个。哈希安全并不意味着碰撞不可能存在；它意味着无法以可行的工作量找到它们。三个不同的性质刻画了这一点。

三个性质

  • 原像抗性。 给定一个哈希值 h，要找到任何满足 hash(m) = h 的输入 m 是不可行的。这是单向性质：一个指纹不应泄露是什么产生了它。对一个 n 位哈希，这大约需要 2ⁿ 的工作量。
  • 第二原像抗性。 给定一个特定输入 m1，要找到一个具有相同哈希的不同输入 m2 是不可行的。攻击者无法伪造第二份与给定文档指纹相符的文档。同样大约 2ⁿ 的工作量。
  • 碰撞抗性。 要找到产生相同哈希值的任意两个不同输入是不可行的。攻击者可以同时选择两者，这使它成为三者中最易攻击的。

生日界

碰撞抗性弱于另外两者，原因微妙，即生日悖论。在一个仅 23 人的房间里，两人生日相同的概率约为 50%，因为配对的数量呈二次增长。同样的效应适用于哈希：在一个 n 位哈希中找到一次碰撞只需大约 2^(n/2) 次尝试，而非 2ⁿ。

这将对碰撞的有效强度减半：

  • 提供约 128 位的碰撞抗性（2¹²⁸ 的工作量），这远在可及范围之外。
  • 像 这样的 128 位哈希即便不因其他原因被攻破，也仅提供约 64 位的碰撞抗性，这就是为何输出大小本身重要。

因此现代哈希使用 256 位或更多：以便把那个减半后的数字舒适地保持在任何攻击者的可及范围之外。

为何一次被找到的碰撞是危险的

当碰撞抗性失效时，攻击者可以制造两个具有相同哈希的输入，让其中之一被签名或被信任，再用另一个替换它。SHAttered 展示了两个具有相同 SHA-1 摘要的 ；Flame 恶意软件用一次 MD5 碰撞伪造了一张受信任证书。两种情形下签名对两份文档都有效，因此一个经过验证的签名不再能证明你实际收到了哪一份。这就是为何在对手可以选择输入之处不可使用 MD5 和 SHA-1 的具体原因。

哈希工具 允许你对任意输入进行哈希并比较摘要，从而亲眼看到一个改变的位会产生完全不同的指纹，全部在你的浏览器中计算，不发送任何内容。