为什么HashMap需要加密安全散列函数？

Question

我正在读一本关于HashMap 哈希函数的Rust书,我无法理解这两句话.

默认情况下,HashMap使用加密安全散列函数,可以抵御拒绝服务(DoS)攻击.这不是最快的哈希算法,但是随着性能下降而带来更好的安全性的权衡是值得的.

我知道什么是加密安全哈希函数,但我不理解它背后的基本原理.根据我的理解,一个好的哈希函数HashMap应该只有三个属性:

• 确定性的(同一个对象具有相同的哈希值)
• 非常快
• 在散列值中具有均匀的位分布(意味着它将减少冲突)

在加密安全散列函数中,其他属性与散列表的99%(甚至99.99%)时间并不相关.

所以我的问题是:"对DoS攻击和更好的安全性的抵抗"甚至意味着在HashMap的背景下？

Answer 1

让我们开始向后:你如何做HashMap？

多年来,基于Hash Flooding的各种软件堆栈遭到多次攻击.如果您知道某个站点是由哪个框架提供支持的,因此使用了哪个哈希函数,并且此哈希函数不具有加密安全性,那么您可以预先计算一组大量字符串哈希到相同的数字.

然后,您只需将此集合注入站点,并且对于每个(简单)请求,它执行不成比例的大量工作,因为插入N个元素需要执行O(N ²)操作.

Rust是在后见之明的情况下构思出来的,因此默认情况下注意避免这种攻击,并推断真正需要性能的用户HashMap只需切换哈希函数即可.

Answer 2

假设我们用来HashMap 在 Web 应用程序中存储一些用户数据。假设用户可以以某种方式选择（部分）密钥- 也许密钥是上传文件的用户名或文件名或类似的东西。

如果我们没有使用加密安全的哈希函数，这意味着攻击者可能会制作多个输入，这些输入都映射到相同的输出。当然，哈希映射必须处理冲突，因为它们自然发生。

但是当发生不自然的许多冲突时，哈希映射实现可能会做一些奇怪的事情。例如，查找某些键的运行时间可能为 O(n)。或者哈希映射可能认为它必须因为所有冲突而增长；但是增长并不能解决问题，所以哈希映射会增长，直到所有内存都用完。无论哪种情况，都不好。哈希映射只是假设统计上很少发生冲突。

当然，这不是“窃取用户数据”攻击——至少不是直接攻击。但是，如果系统的某一部分薄弱，这会使攻击者更容易发现其他弱点。

加密安全的散列函数可以防止这种攻击，因为攻击者不可能制作映射到相同值的多个密钥（至少在不尝试所有密钥的情况下不可能）。

99%（甚至 99.99%）的时间与哈希表并不真正相关。

是的，大概。但这很难平衡。我想我们都会同意，如果 20% 的用户由于不安全的哈希函数而在他们的应用程序中遇到安全问题（而 80% 不关心），使用“默认安全”方法仍然是一个好主意。5%/95% 怎么样？1%/99% 怎么样？很难说阈值在哪里，对吧？

已经有很多关于这个的讨论。因为是的，大多数人只注意到哈希映射的缓慢。也许我上面描述的情况非常罕见，默认情况下不值得减慢所有其他用户的代码。但这已经决定了，默认的哈希函数不会改变，幸运的是你可以选择自己的哈希函数。