非随机散列函数导致的应用程序漏洞 [英] Application vulnerability due to Non Random Hash Functions
问题描述
以下摘录来自文章，该文章解释了拒绝服务 (DoS) 攻击的可能性因为散列数据结构中使用了非随机散列函数.
Below excerpt is from an article that explains possibility of Denial Of Service(DoS) attack because of non random hash functions used in Hash Data Structures.
[…] 可以通过利用底层散列算法中的可预测冲突来利用该条件.
[…] the condition can be leveraged by exploiting predictable collisions in the underlying hashing algorithms.
为了验证它，我查阅了 Oracle 的 Java HashMap 的参考实现，确实找到了使用的静态哈希函数:
In order to verify it I went through reference implementation of Java HashMap from Oracle and indeed found a static hash functions used:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
关于该主题的另一篇论文说明:
Another paper on the topic tells:
Tomcat 6.0.32 服务器解析 2 MB 的冲突键字符串大约44 分钟的 i7 CPU 时间，因此大约 6 kbit/s 的攻击者可以持续保持一个 i7 核心忙.如果攻击者有千兆连接，他可以让大约 100.000 个 i7 内核保持忙碌
A Tomcat 6.0.32 server parses a 2 MB string of colliding keys in about 44 minutes of i7 CPU time, so an attacker with about 6 kbit/s can keep one i7 core constantly busy. If the attacker has a Gigabit connection, he can keep about 100.000 i7 cores busy
我们如何防范此漏洞.此外，我们使用的许多软件都是依赖此实现的开源软件(Tomcat 等).
How can we safeguard against this vulnerability. Moreover so with so many of softwares we use being open source (Tomcat etc.) which rely on this implementation.
推荐答案
了解攻击向量
HashMap 的工作原理
假设博客上的评论表单接受参数——名字、姓氏、评论——作为帖子参数.在内部，Tomcat 将这些参数存储为 HashMap.
Understanding Attack Vector
How HashMaps work
Say a comment form on a blog accepts the parameters – first_name, last_name, comment – as post parameters. Internally, Tomcat stores these parameters as a HashMap.
这个HashMap的逻辑结构是这样的——
The logical structure of this HashMap is like this -
"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"
但是物理结构是不同的.键先转换成hashCode，然后hashCode转换成数组索引.
But the physical structure is different. The keys are first converted into a hashCode, and then the hashCode is converted into an array index.
理想的物理结构就变成了 -
0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"
但是可能的键是无限的.因此，在某些时候，两个键将具有相同的哈希码.这变成了哈希冲突.
But the possible keys are infinite. So at some point, two keys will have the same hash code. This becomes a hash collision.
通过碰撞，物理结构变成:
0 --> "Sripathi", "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"
哈希冲突和对性能的影响
当您遇到哈希冲突时，插入新条目意味着顺序迭代单个哈希存储桶"中的所有元素，以查明它是否已存在于映射中.如果所有元素散列到相同的值，则插入一个元素可以接近 O(n) 复杂度.在这种最坏的情况下插入 n 个元素使其复杂度为 O(n*n).
Hash Collisions and impact on performance
When you have hash collisions, inserting a new entry means iterating over all the elements in a single hash "bucket" sequentially just to find out if it already exists in the map. Inserting one element can approach O(n) complexity if all elements hash to the same value. Inserting n elements in this worst case makes it O(n*n) complexity.
简而言之:如果您插入数千个具有相同 hashCode 的键，服务器将需要大量 CPU 周期.
In short : If you insert thousands of keys that have the same hashCode, the server will require a lot of CPU cycles.
在 Java 中，Aa"和BB"具有相同的哈希码.
In Java, "Aa" and "BB" have the same hash code.
因为有一个叫做Equivalent Substrings"的属性，我们可以生成几个具有相同哈希码的其他字符串，只需从这两个字符串开始.
Because of a property called "Equivalent Substrings", we can generate several other strings with the same hashcode, just by starting with these 2 strings.
第一次迭代:AAAA"、AABb"、BbAA"、BbBb"具有相同的哈希码
First Iteration : "AAAA", "AABb", "BbAA", "BbBb" have the same hash code
现在，我们有 4 个具有相同哈希码的字符串.我们可以对它们进行置换以生成 16 个具有相同哈希码的字符串.例如:
Now, we have 4 strings with the same hash code. We can permute them to generate 16 strings that will have the same hash code. For example :
"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",
所有这 16 个字符串都具有相同的哈希码.
All these 16 strings have the same hash code.
您现在可以使用这 16 个字符串，并生成 256 个具有相同哈希码的字符串.
You can now take these 16 strings, and generate 256 strings that have the same hashcode.
简而言之:生成具有准确哈希码的大量字符串非常容易.
In short : It is very easy to generate a large set of strings that will have the exact hash code.
- 创建数千个具有相同哈希码的字符串(见上文)
- 像这样构造一个 POST 请求 - AaAa=&AaBB=&BBAa=&BBBB= ....
- 提交表单
- 循环重复，创建多个线程，使所有服务器资源都用完
因为这只是一个 POST 请求，攻击者也可以使用无辜的浏览器来攻击服务器.只需找到一个存在跨站脚本漏洞的网站，嵌入代码发出 POST 请求，然后使用社会工程学将链接传播给尽可能多的用户.
Because this is just a POST request, an attacker can also use innocent browsers to attack a server. Just find a website with a cross site scripting vulnerability, embed code to make a POST request, and then use social engineering to spread the link to as many users as you can.
一般来说，底层平台无法解决这个问题.这被认为是应用程序框架问题.换句话说，Tomcat 必须解决这个问题，而不是 Oracle/Sun.
In general, the underlying platform cannot fix this. This is considered to be a application framework problem. In other words, Tomcat has to fix this, not Oracle/Sun.
可能的修复包括:
限制 POST 参数的数量 - Tomcat 6.0.35+ 有一个新参数 maxParameterCount.默认值为 10,000.越低越好，只要它不破坏您的功能.
Restrict the number of POST parameters - Tomcat 6.0.35+ has a new parameter maxParameterCount. The default value is 10,000. The lower the better, as long as it does not break your functionality.
限制 POST 请求的大小 - 为了使攻击有效，有效载荷必须很大.Tomcat 允许的默认 POST 是 2MB.将其减少到 200KB 将降低此攻击的有效性.tomcat中的参数是maxPostSize
Restrict the size of the POST request - For the attack to work, the Payload has to be huge. The default POST allowed by Tomcat is 2MB. Reducing this to say 200KB will reduce the effectiveness of this attack. The parameter in tomcat is maxPostSize
Web 应用程序防火墙 - 如果您有 Web 应用程序防火墙，您可以将其配置为阻止看起来可疑的请求.这是一种被动措施，但在您无法使用上述解决方案之一的情况下非常有用.
Web Application Firewall - If you have a web application firewall, you can configure it to block requests that look suspicious. This is a reactive measure, but is nice to have in case you cannot use one of the above solutions.
仅供参考 - Tomcat 的文档在这里 - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html
FYI - Tomcat's documentation is here - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html
这篇关于非随机散列函数导致的应用程序漏洞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
