由于非随机哈希函数而导致的应用程序漏洞
以下摘录来自一篇文章 ，解释了由于散列数据结构中使用的非随机散列函数而导致拒绝服务（DoS）攻击的可能性。
可以通过利用底层散列algorithm中的可预测冲突来利用该条件。
为了validation它，我经历了从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时间内parsing2MB的冲突密钥string，所以约6kbit / s的攻击者可以让一个i7内核持续忙碌。 如果攻击者有千兆连接，他可以保持大约100.000个i7内核忙碌
我们如何防范这个漏洞呢？ 此外，有很多软件，我们使用开源（Tomcat等），依靠这种实现。
了解攻击vector
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”的属性，我们可以使用相同的哈希码生成其他几个string，只需从这两个string开始。
第一次迭代：“AAAA”，“AABb”，“BbAA”，“BbBb”具有相同的哈希码
现在，我们有4个具有相同散列码的string。 我们可以对它们进行sorting，生成16个具有相同散列码的string。 例如 ：
"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa", "BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa", "AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa", "BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",
所有这16个string都有相同的散列码。
您现在可以使用这16个string，并生成具有相同哈希码的256个string。
简而言之：生成一大串具有精确哈希码的string非常容易。
你如何攻击服务器？
- 创build数千个具有相同散列码的string（请参阅上文）
- 构build一个像这样的POST请求 – AaAa =＆AaBB =＆BBAa =＆BBBB = ….
- 提交表单
- 重复一个循环，并创build多个线程，以便所有服务器资源都用完
由于这只是一个POST请求，攻击者也可以使用无辜的浏览器攻击服务器。 只要find一个具有跨站点脚本漏洞的网站，embedded代码来发布POST请求，然后使用社会工程将链接传播给尽可能多的用户。
预防
一般来说，底层平台无法解决这个问题。 这被认为是一个应用程序框架问题。 换句话说，Tomcat必须解决这个问题，而不是Oracle / Sun。
可能的修复包括：
-
限制POST参数的数量 – Tomcat 6.035+有一个新的参数maxParameterCount 。 默认值是10,000。 越低越好，只要不破坏你的function。
-
限制POST请求的大小 – 为了使攻击行得通，Payload必须是巨大的。 Tomcat允许的默认POST是2MB。 减less200KB会降低这种攻击的效果。 tomcat中的参数是maxPostSize
-
Web应用程序防火墙 – 如果您有Web应用程序防火墙，则可以将其configuration为阻止看起来可疑的请求。 这是一种被动的措施，但如果您不能使用上述解决scheme之一，则很有帮助。
仅供参考 – Tomcat的文档在这里 – http://tomcat.apache.org/tomcat-6.0-doc/config/http.html
最简单的解决scheme是升级到固定版本的tomcat。 不过，我怀疑你想知道tomcat人们需要改变的细节。
这种攻击通过利用哈希数据结构的通用实现细节来工作 – 使用链表来保存哈希值相同的所有值。 给这个链表添加值效率不高，因为列表的大小变大了。 攻击者可以创build已知会产生冲突散列值的列表，强制执行这种低效的行为。 为了防止这一点，你有几个select：
-
防止冲突 – 通过在散列函数中join一些（伪）随机因子来防止攻击者产生冲突的值。 Perl已经做了很长时间了。
-
除了链表之外的东西，为你的桶使用 – 攻击是有效的，因为将N个项目插入到链表中有N ^ 2个增长。 如果您使用平衡树或插入时具有N logN增长的其他结构，则应该缓解该问题。 这可能会牺牲一些最好/平均的情况下的performance，以限制最糟糕的情况是多么糟糕。
受影响的Tomcat版本是Apache Tomcat <= 5.5.34，<= 6.0.34，<= 7.0.22根据您提供的链接。 该页面将Apache Tomcat> = 5.5.35，> = 6.0.35，> = 7.0.23列为固定版本。
当填充条目达到阈值时，Java HashMap / HashTable可以执行“resize”操作。 很难说有一个固定的桶HashMap在等着你。 由于select桶的操作有两个步骤：一是取指定键的哈希值; 另一个主要步骤是剩余操作与总桶大小（大小已被改变'resize'）。
这里有一些python代码来生成这些键…还没有testing过，但会有兴趣得到它的反馈：
#!/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)
