由非随机哈希函数引起的应用程序漏洞

问题描述 投票：33回答：5

以下摘录来自article，它解释了由于哈希数据结构中使用的非随机哈希函数而导致拒绝服务（DoS）攻击的可能性。

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

为了验证它，我经历了Oracle的Java HashMap的参考实现，并且确实发现了一个使用的静态哈希函数：

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

关于这个主题的另一个paper告诉：

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

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

java security ddos
5个回答
51
投票

Understanding Attack Vector

HashMaps如何工作

假设博客上的评论表单接受参数 - first_name，last_name，comment - 作为post参数。在内部，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”具有相同的哈希码。

由于名为“Equivalent Substrings”的属性，我们可以使用相同的哈希码生成其他几个字符串，只需从这两个字符串开始。

第一次迭代：“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请求，然后使用社交工程将链接分散到尽可能多的用户。

Prevention

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

可能的修复包括：

  1. 限制POST参数的数量 - Tomcat 6.0.35+有一个新参数maxParameterCount。默认值为10,000。越低越好，只要它不会破坏你的功能。
  2. 限制POST请求的大小 - 为了使攻击有效，Payload必须是巨大的。 Tomcat允许的默认POST是2MB。将此减少到200KB将降低此攻击的有效性。 tomcat中的参数是maxPostSize
  3. Web应用程序防火墙 - 如果您有Web应用程序防火墙，则可以将其配置为阻止看起来可疑的请求。这是一种反应措施，但如果你不能使用上述解决方案之一，那就很好了。

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

3
投票

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

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

  • 防止冲突 - 通过在哈希函数中使用某些（伪）随机因子来防止攻击者生成冲突值。 Perl已经做了很长时间了。
  • 使用除了链接列表之外的东西 - 攻击有效，因为将N个项目插入到链接列表中会增加N ^ 2。如果在插入时使用平衡树或其他具有N logN增长的结构，则应该减轻问题。这可能会牺牲一些最佳/平均案例表现，以限制最坏情况下的糟糕程度。
1
投票

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

0
投票

当填充条目达到阈值时，Java HashMap / HashTable可以执行'resize'操作。很难说有一个固定的桶HashMap等着你。由于选择桶的操作有两个步骤：一个是取指定键的哈希值;另一个主要步骤是具有总存储桶大小的剩余操作（通过'调整大小'来改变大小）。

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)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.