由 Urabe Shyouhei 发布于 2011年12月28日
影响
这与计算复杂度有关。 发现精心构造的一系列字符串会故意彼此碰撞它们的哈希值。 通过这些序列，攻击者可以发起拒绝服务攻击，例如，将其作为 HTTP 请求的 POST 参数发送到您的 Rails 应用程序。
详细描述
这种情况类似于 2003 年 Perl 中发现的情况。在 Ruby 的 1.8 系列中，我们使用确定性的哈希函数来哈希字符串。这里的“确定性”意味着除了输入字符串本身之外，没有其他信息参与生成哈希值。 因此，您可以预先计算字符串的哈希值。 通过收集一系列具有相同哈希值的字符串，攻击者可以让 Ruby 处理哈希表的冲突桶（包括 Hash 类实例）。哈希表的均摊 O(1) 属性取决于哈希值分布的均匀性。 通过提供这种精心构造的输入，攻击者可以让哈希表的工作速度远低于预期（即在本例中构建一个 n 元素表的时间复杂度为 O(n2)）。
受影响的版本
- Ruby 1.8.7-p352 及所有更早版本。
所有 Ruby 1.9 系列不受此类攻击的影响。 它们与 Ruby 1.8 系列不共享哈希实现。
解决方案
我们的解决方案是通过一些 PRNG 生成的随机位来扰乱字符串哈希函数。 这样做后，字符串的哈希值不再是确定性的。 也就是说，String#hash 的结果仅在当前进程的生命周期内一致，并且在下次启动时将生成不同的数字。 为了打破这种情况，攻击者必须创建一组对这种扰乱具有鲁棒性的字符串。 这被认为是非常困难的。
请升级到 ruby 1.8.7-p357。
注意
-
请记住，该解决方案并不 意味着我们的哈希算法是加密安全的。 简单来说，我们修复了哈希表，但我们没有修复
String#hash的弱点。 攻击者仍然可以在获得字符串及其从String#hash返回的哈希值对后利用它。 您必须 不要泄露String#hash的输出。 如果需要这样做，请考虑改用安全的哈希算法。 其中一些（例如 SHA256）在 Ruby 的标准库中提供。 -
对于那些了解我们代码库中替代哈希算法的人：我们不支持它们（默认情况下禁用它们）。 选择它们，我们认为您可以阅读 C，并且可以理解默认哈希算法的问题所在。 请确保您自行承担选择的安全风险。
鸣谢
感谢 Alexander Klink [email protected] 和 Julian Waelde [email protected] 报告此问题。
编辑 一些相关链接
- CVE-2011-4815 被分配给此问题。
- oCERT.org 发布了关于此问题的 一份公告。
- JRuby 发布了 版本 1.6.5.1 以修复相同的问题。 其他 Ruby 替代方案也可能受到影响。
- Twitter 帐户 @hashDoS 收集有关哈希冲突攻击的信息。