Ruby 的 Hash 算法发现拒绝服务攻击 (CVE-2011-4815)

由 Urabe Shyouhei 发布于 2011 年 12 月 28 日

影响

这与计算复杂度有关。发现了一系列经过精心设计的、有意使哈希值发生冲突的字符串。攻击者可以通过提供这些字符串作为您 Rails 应用程序的 HTTP 请求的 POST 参数等方式，发起拒绝服务攻击。

详细描述

这种情况类似于 2003 年在 Perl 中发现的情况。在 Ruby 的 1.8 系列中，我们使用确定性哈希函数来哈希字符串。这里的“确定性”意味着除了输入字符串本身之外，不涉及任何其他信息来生成哈希值。因此，您可以提前计算字符串的哈希值。通过收集一系列具有相同哈希值的字符串，攻击者可以使 Ruby 处理哈希表的冲突桶（包括 `Hash` 类实例）。哈希表摊销 O(1) 的属性取决于哈希值分布的均匀性。通过提供这种精心设计的输入，攻击者可以让哈希表的性能远低于预期（在此情况下，构建一个 n 元素表的时间复杂度为 O(n^2)）。

受影响的版本

• 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 alexander.klink@nruns.com 和 Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de 报告此问题。

编辑 一些相关链接

• 此问题已分配 CVE 编号 CVE-2011-4815。
• oCERT.org 发布了关于此问题的 公告。
• JRuby 发布了 1.6.5.1 版本来修复相同的问题。其他 Ruby 的替代方案也可能受到影响。
• Twitter 账号 @hashDoS 收集有关哈希冲突攻击的信息。