37

下面的摘录来自一篇文章，该文章解释了由于散列数据结构中使用的非随机散列函数而导致拒绝服务 (DoS) 攻击的可能性。

[…] 可以通过利用底层散列算法中的可预测冲突来利用该条件。

为了验证它，我查看了 Oracle 的 Java HashMap 的参考实现，并确实找到了使用的静态哈希函数：

    static int hash(int h) {
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
    }

关于该主题的另一篇论文说：

Tomcat 6.0.32 服务器在 i7 CPU 时间的大约 44 分钟内解析 2 MB 的冲突键字符串，因此具有大约 6 kbit/s 的攻击者可以保持一个 i7 内核持续忙碌。如果攻击者有一个千兆连接，他可以让大约 100.000 个 i7 核心保持忙碌

我们如何才能防范此漏洞。此外，我们使用的许多软件都是依赖此实现的开源软件（Tomcat 等）。

4

5 回答 5

54

了解攻击向量

HashMap 的工作原理

假设博客上的评论表单接受参数——名字、姓氏、评论——作为帖子参数。在内部，Tomcat 将这些参数存储为 HashMap。

这个HashMap的逻辑结构是这样的——


"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"

但物理结构不同。首先将键转换为 hashCode，然后将 hashCode 转换为数组索引。

理想的物理结构因此变成——


0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"

但是可能的键是无限的。所以在某些时候，两个键将具有相同的哈希码。这变成了哈希冲突。

随着碰撞，物理结构变为：


0 --> "Sripathi", "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"

哈希冲突和对性能的影响

当您有哈希冲突时，插入一个新条目意味着依次迭代单个哈希“桶”中的所有元素，只是为了找出它是否已经存在于映射中。如果所有元素散列到相同的值，则插入一个元素可能会接近 O(n) 复杂度。在这种最坏的情况下插入 n 个元素会使其复杂度为 O(n*n)。

简而言之：如果您插入数千个具有相同 hashCode 的键，服务器将需要大量 CPU 周期。

如何生成具有相同哈希的密钥？

在 Java 中，“Aa”和“BB”具有相同的哈希码。

由于一个名为“等效子字符串”的属性，我们可以生成其他几个具有相同哈希码的字符串，只需从这两个字符串开始。

第一次迭代：“AAAA”、“AABb”、“BbAA”、“BbBb”具有相同的哈希码

现在，我们有 4 个具有相同哈希码的字符串。我们可以对它们进行置换以生成 16 个具有相同哈希码的字符串。例如 ：


"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

所有这 16 个字符串都具有相同的哈希码。

您现在可以获取这 16 个字符串，并生成 256 个具有相同哈希码的字符串。

简而言之：生成一大组具有精确哈希码的字符串非常容易。

你如何攻击服务器？

  1. 创建数千个具有相同哈希码的字符串（见上文）
  2. 像这样构造一个 POST 请求 - AaAa=&AaBB=&BBAa=&BBBB= ....
  3. 提交表格
  4. 循环重复，并创建多个线程，使所有服务器资源都用完

因为这只是一个 POST 请求，攻击者也可以使用无辜的浏览器来攻击服务器。只需找到一个存在跨站脚本漏洞的网站，嵌入代码以发出 POST 请求，然后使用社交工程将链接传播给尽可能多的用户。

预防

一般来说，底层平台无法解决这个问题。这被认为是应用程序框架问题。换句话说，Tomcat 必须解决这个问题，而不是 Oracle/Sun。

可能的修复包括：

  1. 限制 POST 参数的数量- Tomcat 6.0.35+ 有一个新参数maxParameterCount。默认值为 10,000。越低越好，只要它不会破坏您的功能。

  2. 限制 POST 请求的大小- 为了使攻击起作用，有效负载必须很大。Tomcat 允许的默认 POST 为 2MB。将其减少到 200KB 将降低此攻击的有效性。tomcat中的参数是maxPostSize

  3. Web 应用程序防火墙- 如果您有 Web 应用程序防火墙，您可以将其配置为阻止看起来可疑的请求。这是一种反应性措施，但如果您无法使用上述解决方案之一，则很好。

仅供参考 - Tomcat 的文档在这里 - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html

于 2011-12-29T17:55:28.017 回答
3

最简单的解决方案是升级到固定版本的tomcat。但是，我怀疑您想知道 tomcat 人员需要更改的详细信息。

这种攻击通过利用散列数据结构的一个常见实现细节来进行 - 使用链表来保存所有散列相同的值。随着列表的大小变大，向此链接列表添加值效率低下。攻击者可以创建一个已知会生成冲突哈希的值列表，从而强制执行这种低效行为。为了防止这种情况，您有几个选择：

  • 防止冲突 - 通过在哈希函数中添加一些（伪）随机因子来防止攻击者生成冲突值。Perl 已经这样做了很长时间。

  • 为您的存储桶使用链表以外的其他东西 - 攻击有效，因为将 N 个项目插入到链表中具有 N^2 增长。如果您在插入时使用平衡树或其他具有 N logN 增长的结构，则应该可以缓解该问题。这可能会牺牲一些最佳/平均情况性能，以限制最坏情况的严重程度。

于 2011-12-29T16:44:03.967 回答
1

根据您提供的链接，受影响的 Tomcat 版本是 Apache Tomcat <= 5.5.34、<= 6.0.34、<= 7.0.22。该页面将 Apache Tomcat >= 5.5.35、>= 6.0.35、>= 7.0.23 列为固定版本。

于 2011-12-29T16:14:47.553 回答
0

这是一些用于生成这些密钥的 python 代码...尚未对其进行测试，但有兴趣获得有关它的反馈：

#!/usr/bin/python
import sys
alphabet = ["Aa","BB"]

def func(str, length):
                global alphabet
                if(length != 0):
                                for x in alphabet:
                                                new_str = str+x
                                                func(new_str, length-1)
                else:
                                sys.stdout.write(str+"=&")


for x in range(1,16):
        func("",x)
于 2012-05-29T17:31:14.813 回答
-1

当填充的条目达到阈值时，Java HashMap/HashTable 可以执行“resize”操作。很难说有一个固定的桶 HashMap 等着你。因为选择bucket的操作有两个步骤：一是取指定key的hash值；另一个主要步骤是对总桶大小进行余数运算（大小已通过“调整大小”进行更改）。

于 2012-01-06T06:16:10.677 回答