由非随机哈希函数引起的应用程序漏洞 [英] 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);
}
另一个论文告诉：
Tomcat 6.0.32服务器解析2 MB字符串在i7 CPU时间大约
44分钟内碰撞密钥，所以一个大约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的工作原理
说博客上的评论表单接受参数 - first_name，last_name，comment作为后期参数。在内部，Tomcat将这些参数存储为HashMap。
Understanding Attack Vector
How HashMap's 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 sequentially just to find out if it already exists in the map. Inserting one element becomes O(n) complexity. Inserting n elements 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 = ....
- 提交表格
- 循环重复，创建多个线程以便所有服务器资源都用完
- Create thousands of string that have the same hash code (see above)
- Construct a POST request like this - AaAa=&AaBB=&BBAa=&BBBB= ....
- Submit the form
- Repeat in a loop, and create several threads so that all server resources are used up
因为这只是一个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.035+有一个新参数 maxParameterCount 。默认值为10,000。越低越好，只要它不会破坏你的功能。
Restrict the number of POST parameters - Tomcat 6.035+ 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请求的大小 - 为了使攻击有效，Payload必须是巨大的。 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.
FYI - 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屋！
