有时应用程序使用不受信任的数据作为哈希映射中的键。一个简单的实现可以允许不受信任的数据导致拒绝服务攻击。

散列图很快 - O(1) - 在最好的情况下，但慢 - O(n) - 在最坏的情况下。这是因为键通常位于不同的桶中，但某些值可能会导致相同的散列 - 冲突 - 由较慢的链表处理。对于随机数据，碰撞将不常见。但是，某些实现存在一个漏洞，恶意数据可能会导致许多冲突，这会使哈希映射变慢。几年前，由于这个原因，出现了Linux 内核 DoS 。

Linux 漏洞的根本原因是散列是可预测的。通过在散列函数中引入一个远程用户不知道的密钥来修复它。我不确切知道 Rust 哈希映射是如何工作的，但我希望它们使用类似的键控哈希。

每当您使用不受信任的数据作为密钥时，您都应该选择更安全的散列。

对哈希表的插入、搜索和删除操作具有 O(n) 最坏情况行为。如果攻击者可以选择要插入哈希表的密钥并且他们可以自己计算哈希函数，那么这就为拒绝服务创造了机会。他们需要做的就是选择映射到同一个存储桶的键。

引用表明使用加密哈希算法（SHA、MD5、Blake、Skein 等）可以解决问题。这种解释是完全不正确的。Rust 的 HashMap 使用的算法称为SipHash。它是一种哈希算法。它是一种密码算法。但它不是cryptographic-hash-function。SipHash 在密码学领域的正确术语是PRF。

关键区别在于（在密码学中）散列函数的所有细节都可能是公共知识。另一方面，PRF 需要密钥。没有秘密信息，对于任何输入，都无法预测输出将是什么。（所有其他细节都是公开的。）

SHA-2 之类的东西不会阻止拒绝服务。对于非对抗性输入，它将完全没有偏见。（因为加密哈希函数可以建模为随机预言。）但是任何人都可以评估普通的 SHA-2，因此有人可以通过蛮力找到哈希表冲突。

加密哈希函数具有抗冲突性（至少具有 256 位输出）这一事实并不能转化为在哈希表的情况下没有冲突。最终，对于具有n 个存储桶的表，您的哈希函数将减少为n 个可能值之一。通过反复试验，您可以找到大约每n次尝试映射到特定存储桶的输入。没有哈希表使用足够的桶来使这成为不可能。

无论散列函数有多好，使用无键散列函数本质上都容易受到拒绝服务的攻击。攻击者和带有哈希映射的服务器都查询同一个预言机这一事实使 DOSer 能够使用专门选择的输入来占用你的 CPU。

如果使用正确，像 SipHash 这样的 PRF 就没有这个漏洞。服务器使用从 2 ¹²⁸个可能的函数池中选择的预言机/函数。为了利用基于 PRF 的（哈希表）哈希函数，攻击者要么需要猜测他应该使用 2128 个函数中的哪一个（“密钥恢复”），要么在 PRF 中找到独立于密钥的偏差^（一种区分 PRF 和随机预言机的方法）。

最后，还存在涉及哈希算法的更多令人困惑的细微差别。但是简单总结一下：

• 密码散列函数是所有普通散列函数的子集
• 在密码散列函数的经典定义下，不需要随机性。然而，随机性无论如何都是所有大牌加密哈希函数的一个特征。
• 并非所有 PRF 都是加密哈希函数
• 并非所有加密哈希函数都是 PRF
• 算法可以具有 PRF 和密码散列函数的属性。
  • Blake2、Skein 和 KMAC 具有两组属性
  • SHA-2 和 SHA-3 系列是（未加密的）加密哈希函数的示例
  • SipHash 只是一个 PRF（和一个普通但不是加密的哈希函数）
• 可以使用典型的加密散列函数来构造 PRF，但散列函数本身不一定是 PRF。
• “随机散列”和“通用散列”在某些方面类似于 PRF，但它们没有相同的安全要求。
  • 即使 MurmurHash3 的种子是随机的，也可以创建碰撞

我同意这有点含糊，这在很大程度上取决于哈希图的使用方式。

这是我的猜测：假设您正在从用户那里获取一些输入，比如说[Firstname.Lastname]并将其用作哈希表中的查找值。假设您正在使用带首字母的简单哈希函数构建哈希表，这样[Firstname.Lastname] --> FL攻击者就可以轻松地将大量哈希值提交给同一事物。这实际上会将您的哈希表变成一个列表，从而否定使用哈希表的所有性能增益。缓慢查找 = 拒绝服务。

AA -> [ ]
AB -> [ ]
...
FK -> [ ]
FL -> [First.Last, F1.F2, F1.F2, Fanotheu.Lonteuh, ...]
FM -> [ ]
...
ZZ -> [ ]

加密哈希函数是专门为防止这种情况而设计的，因为很难构造两个具有相同哈希值的不同输入（称为冲突）。

我什么时候应该选择更安全的散列而不是更快的散列？

答案很简单：只要查找值由用户提供并且可能被恶意制作，就选择加密哈希。如果查找值来自您认为是非恶意且均匀分布的某个内部来源，那么您可以使用更快的散列。