且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

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

更新时间:2022-12-03 09:05:47

了解攻击向量



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.


  1. 创建数千个具有相同哈希码的字符串(见上文)

  2. 构建这样的POST请求 - AaAa =& AaBB =& BBAa =& BBBB = ....

  3. 提交表格

  4. 循环重复,创建多个线程以便所有服务器资源都用完

  1. Create thousands of string that have the same hash code (see above)
  2. Construct a POST request like this - AaAa=&AaBB=&BBAa=&BBBB= ....
  3. Submit the form
  4. 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.

可能的修复包括:


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

  1. 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