java Hash碰撞攻击

看到一篇讲述Hash碰撞攻击的文章。我从来没有注意过这个问题,所以亲手实践一下。

参考:https://yq.aliyun.com/articles/92194?t=t1

 

一、攻击原理

在HashMap中,元素的位置是由key决定的。我们对key进行一系列的hash算法,从而决定该元素的bucket位置。如果该位置存在复数元素,那么将形成链表。

元素应该尽量离散(存在不同位置的bucket中),操作效率才会高。理想状况如下:

999

那么问题来了:hash算法是非随机的,如果存在一系列不同的key,这些key计算得到的hash值都是相同的,那么所有key所在的bucket位置都相同,那么HashMap中某位置的链表将会无限延长。

1000

如果链表超长,那么该HashMap查询和插入的效率将会变低,进行操作时将占用大量系统资源。

所有和HashMap数据结构相近的集合(比如HashTable),都会遇到这个问题。

二、具体攻击步骤

(1)获取种子

在Java里,Aa和BB这两个字符串的hash code(或hash key) 是一样的,也就是Collision。

写个测试验证一下:

TestHash.java

结果为:

到这里我们得到了两个种子“Aa”和“BB”。

(2)生成更多攻击数据

于是,我们就可以组合这两个种子生成更多的hash key相同的字符串。比如:”AaAa”, “AaBB”, “BBAa”, “BBBB”。其实就是一个排列组合,写个程序就搞定了。

我们可以不停进行迭代,从而拥有更多组合。

在实际构造攻击数据时,不会采用以上方法。具体方法可以参考:

java 如何生成Hash攻击数据?

(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.5秒左右。可以发现,在jdk 1.8中,对HashMap的攻击毫无效果。主要是因为jdk 1.8中重写了HashMap,在链表长度大于8时,会使用红黑树记录元素,无法形成超长链表。

对于json解析库,在jdk 1.8中,Jackson中用LinkeHashMap来保存数据,所以也不会受到攻击影响。

但是,如果把这里的HashMap换成HashTable,可以形成超长链表,起到攻击效果。

运行结果为:

大概运行了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解析的方法。

五、总结

还是那句话,不要相信任何的用户输入。小心驶得万年船。

发表评论

电子邮件地址不会被公开。 必填项已用*标注