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

Question

以下摘录来自一篇解释由于哈希数据结构中使用的非随机哈希函数而导致拒绝服务(DoS)攻击的可能性的文章.

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

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

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

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

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

我们如何防范此漏洞.此外,对于许多软件,我们使用的是依赖于此实现的开源(Tomcat等).

Answer 1

了解攻击向量

HashMap的工作原理

假设博客上的评论表单接受参数 - 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请求,然后使用社交工程将链接分散到尽可能多的用户.

预防

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

可能的修复包括:

1. 限制POST参数的数量 - Tomcat 6.035+有一个新参数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

Answer 2

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