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解析的方法。
五、总结
还是那句话,不要相信任何的用户输入。小心驶得万年船。