为什么 HashMap 需要加密安全的哈希函数？
Why does HashMap need a cryptographically secure hashing function?
我在看一本关于HashMaphashing functions的Rust书，我看不懂这两句话
By default, HashMap uses a cryptographically secure hashing function that can provide resistance to Denial of Service (DoS) attacks. This is not the fastest hashing algorithm available, but the trade-off for better security that comes with the drop in performance is worth it.
我知道什么是加密安全散列函数，但我不明白它背后的基本原理。根据我的理解，HashMap 的一个好的哈希函数应该只有三个属性：
- 确定性（同一对象具有相同的哈希值）
- 非常快，
- 哈希值中的位分布均匀（意味着它将减少冲突）
加密安全哈希函数中的其他属性在 99%（甚至可能是 99.99%）的时间内与哈希表并不相关。
所以我的问题是：什么是“抵抗 DoS 攻击和更好的安全性”
" 甚至在 HashMap 的上下文中是什么意思？
如果服务器应用程序将用户输入（例如 Web 应用程序中的 post 数据）存储在散列 table 中，恶意用户可能会尝试提供大量输入，这些输入都具有相同的哈希值，导致大量哈希冲突，从而显着减慢地图上的操作，以至于它可以用作 DoS 攻击（如 this article 中所述）。
如果哈希是加密安全的，攻击者将很难找到具有相同哈希值的输入。
让我们从头开始：你如何对 HashMap 进行 DoS？
多年来，针对基于Hash Flooding的各种软件堆栈的攻击已经多次发生。如果您知道站点由哪个框架提供支持，因此使用了哪个散列函数，并且此散列函数不是加密安全的，那么您可以预先计算，离线，大量字符串散列为相同的数字。
然后，您只需将这个集合注入网站，对于每个（简单的）请求，它都会做大量的工作，因为插入 N 个元素需要 O(N2) 操作。
Rust 的构想是事后诸葛亮，因此注意避免这种攻击默认，推理真正需要性能的用户 HashMap会简单地切换哈希函数。
假设我们使用 HashMap 在 Web 应用程序中存储一些用户数据。 假设用户可以通过某种方式选择（部分）密钥 – 也许密钥是用户名或上传文件的文件名或类似的东西。
如果我们不使用加密安全散列函数，这意味着攻击者可能 制作全部映射到相同输出的多个输入 。当然，哈希映射必须处理冲突，因为它们是自然发生的。
但是当不自然地发生许多冲突时，哈希映射实现可能会做一些奇怪的事情。例如，查找某些键的 运行时间可能为 O(n)。或者 hash map 可能认为由于所有的冲突它必须增长；但是增长并不能解决问题，因此散列映射 增长直到所有内存都被使用 。无论哪种情况，都是不好的。哈希图只是假设从统计上讲，碰撞很少发生。
当然，这不是 "stealing user data" 攻击——至少不是直接攻击。但是，如果系统的某一部分较弱，攻击者就更容易找到其他弱点。
加密安全散列函数可防止这种攻击，因为攻击者不可能制作映射到相同值的多个密钥（至少不能不尝试所有密钥）。
is not really relevant 99% (maybe even 99.99%) of the time for hash tables.
是的，可能。但这很难平衡。我想我们都会同意，如果 20% 的用户会因为不安全的哈希函数而在他们的应用程序中遇到安全问题（而 80% 的用户不关心），使用 "secure by default" 方法仍然是个好主意。 5%/95%呢？ 1%/99%呢？很难说门槛在哪里，对吧？
关于这个已经有很多讨论了。因为是的，大多数人只注意到哈希映射的缓慢。也许我上面描述的情况非常罕见，默认情况下不值得放慢所有其他用户的代码。但这已经决定了，默认的哈希函数不会改变，幸运的是你可以选择自己的哈希函数。
我在看一本关于HashMaphashing functions的Rust书，我看不懂这两句话
By default, HashMap uses a cryptographically secure hashing function that can provide resistance to Denial of Service (DoS) attacks. This is not the fastest hashing algorithm available, but the trade-off for better security that comes with the drop in performance is worth it.
我知道什么是加密安全散列函数，但我不明白它背后的基本原理。根据我的理解，HashMap 的一个好的哈希函数应该只有三个属性：
- 确定性（同一对象具有相同的哈希值）
- 非常快，
- 哈希值中的位分布均匀（意味着它将减少冲突）
加密安全哈希函数中的其他属性在 99%（甚至可能是 99.99%）的时间内与哈希表并不相关。
所以我的问题是：什么是“抵抗 DoS 攻击和更好的安全性” " 甚至在 HashMap 的上下文中是什么意思？
如果服务器应用程序将用户输入（例如 Web 应用程序中的 post 数据）存储在散列 table 中，恶意用户可能会尝试提供大量输入，这些输入都具有相同的哈希值，导致大量哈希冲突，从而显着减慢地图上的操作，以至于它可以用作 DoS 攻击（如 this article 中所述）。
如果哈希是加密安全的，攻击者将很难找到具有相同哈希值的输入。
让我们从头开始：你如何对 HashMap 进行 DoS？
多年来，针对基于Hash Flooding的各种软件堆栈的攻击已经多次发生。如果您知道站点由哪个框架提供支持，因此使用了哪个散列函数，并且此散列函数不是加密安全的，那么您可以预先计算，离线，大量字符串散列为相同的数字。
然后，您只需将这个集合注入网站，对于每个（简单的）请求，它都会做大量的工作，因为插入 N 个元素需要 O(N2) 操作。
Rust 的构想是事后诸葛亮，因此注意避免这种攻击默认，推理真正需要性能的用户 HashMap会简单地切换哈希函数。
假设我们使用 HashMap 在 Web 应用程序中存储一些用户数据。 假设用户可以通过某种方式选择（部分）密钥 – 也许密钥是用户名或上传文件的文件名或类似的东西。
如果我们不使用加密安全散列函数，这意味着攻击者可能 制作全部映射到相同输出的多个输入 。当然，哈希映射必须处理冲突，因为它们是自然发生的。
但是当不自然地发生许多冲突时，哈希映射实现可能会做一些奇怪的事情。例如，查找某些键的 运行时间可能为 O(n)。或者 hash map 可能认为由于所有的冲突它必须增长；但是增长并不能解决问题，因此散列映射 增长直到所有内存都被使用 。无论哪种情况，都是不好的。哈希图只是假设从统计上讲，碰撞很少发生。
当然，这不是 "stealing user data" 攻击——至少不是直接攻击。但是，如果系统的某一部分较弱，攻击者就更容易找到其他弱点。
加密安全散列函数可防止这种攻击，因为攻击者不可能制作映射到相同值的多个密钥（至少不能不尝试所有密钥）。
is not really relevant 99% (maybe even 99.99%) of the time for hash tables.
是的，可能。但这很难平衡。我想我们都会同意，如果 20% 的用户会因为不安全的哈希函数而在他们的应用程序中遇到安全问题（而 80% 的用户不关心），使用 "secure by default" 方法仍然是个好主意。 5%/95%呢？ 1%/99%呢？很难说门槛在哪里，对吧？
关于这个已经有很多讨论了。因为是的，大多数人只注意到哈希映射的缓慢。也许我上面描述的情况非常罕见，默认情况下不值得放慢所有其他用户的代码。但这已经决定了，默认的哈希函数不会改变，幸运的是你可以选择自己的哈希函数。