java 如何生成Hash攻击数据?

上次我们讨论了如何进行Hash攻击,最重要步骤就是生成攻击数据。本文对如何生成攻击数据进行了研究。

参考:https://yq.aliyun.com/articles/93526

 

一、如何生成攻击数据

(1)解析hash算法

要找出hash值一致的key,首先要研究java中的hash算法。

因为攻击的key为String字符串,所以查看String.class中的hashcode()方法:

尝试使用此算法进行手工计算。

以字符串“asd”为例,val数组为[97 100 115],计算过程为((0 + 97)* 31 + (0 + 97)) * 31 + ((0 + 97)* 31 + (0 + 97)),结果为96882。

将此算法写成一个静态方法,查看hash的结果:

TestCreate.java

运行结果为:

显然,核心算法为:

即F(n) = 31 * F(n-1) + str[i]。

(2)逆推hash算法

现在已知核心算法为F(n) = 31 * F(n-1) + str[i],将F(n-1)替换为x,将str[i]替换为y,可以得到这样的公式:F(n) = 31 * x + y。

其中,x和y均为字符,F(n)位hash值。我们不难找到这样的组合:

于是我们得到了三个“种子”,“at”、“bU”和“c6”(三者计算的hash值均为3132)。此三者的任意组合(当然字符串的长度要一致)的hash值均相等。

如果我们需要生成长度为22位的字符串(即11个种子的组合),推算将获得3^11 = 177 147 个key。

(3)获取所有组合

现在我们需要获获取这三个种子组成22位长度字符串的所有组合。

这个算法可能不太好想。于是先简化问题:“现有abc三个字符,列举这三个字符组成的长度为3的所有组合”。

我们尝试使用迭代来解决这个问题,解决方案如下:

TestPermutation.java

运行结果为:

成功列举了所有组合。获取种子的所有组合也是同理:

CreateAttackData.java

运行结果为:

正好为预计的key的数量。

这里有个问题:我使用了HashMap来装载所有攻击数据的键值对(为了方便使用jackson生成json),在Jdk 1.8中,因为HashMap使用红黑树进行了优化,所以不会遇到链表过长的问题。但是在jdk 1.8以下的版本,这种做法无异于对本机进行攻击,将造成cpu使用率飙升。所以低版本的jdk不适合运行此程序。

那么低版本的jdk怎么办?可以这样解决:使用List装载所有生成的key,然后写个循环拼接json。当然最简单的方式是换用其他(没有hash冲突的)语言写个脚本生成json。

(4)获取攻击数据(json)

CreateAttackData.java

之后就能在项目文件下获取attack.json文件,里面就是可用于攻击的数据。

这里补充一个有意思的问题:我尝试使用bejson网站校验攻击数据(黏贴到文本框中),然后我的chrome就卡死了,只能关闭窗口,其他操作一律没有响应,推测是成功攻击了本机的js(cpu使用率50%左右,平时只有3%)。

我猜测bejson判断字符串是否为json的的js中应该有类似的代码:

导致发生了hash攻击。但是,之后我查看了inore.js,没有发现类似的代码(或许只是字符串太长,js判断是否为json时耗费了大量资源而已?)。

二、总结

本来我想练习一下算法,结果尝试了半天都没写出来,感觉有点难受。但是解决问题的思路还可以,最终还是圆满解决了。