标签: hash-collision

如果从1到X计数,其中X是第一个与前一个数字发生md5冲突的数字,那么X是多少？

我想知道我是否使用md5作为序列号,在碰撞之前我可以期望能够枚举多少单位.

当使用adler32()作为哈希函数时,应该会遇到罕见的冲突.

我们可以对碰撞概率进行精确计算,但粗略地说,
因为它是一个32位散列函数,所以
在几千个项目的样本集上不应该有很多碰撞.

情况并非如此.

这是一个例子:让我们采取包含中间日期的字符串,例如

"Some prefix text " + date + " some postfix text."

其中,dates`格式为yyyy-mm-dd,并在2012年循环.

这个例子中有91次碰撞!

更糟糕的是:有7个案例发生了3个日期相撞.

为什么这种常用的哈希函数表现如此糟糕？
或者我错过了什么？

以下是上述示例的详细结果:

0x592a0f1f: 2012-01-30, 2012-02-02, 2012-10-21
0x592b0f1f: 2012-02-11, 2012-10-30, 2012-11-02
0x593d0f20: 2012-01-31, 2012-02-03, 2012-10-22
0x593e0f20: 2012-02-12, 2012-10-31, 2012-11-03
0x59410f20: 2012-03-11, 2012-11-30, 2012-12-02
0x59560f21: 2012-03-30, 2012-04-02, 2012-12-21
0x59690f22: 2012-03-31, 2012-04-03, 2012-12-22

0x59020f1d: 2012-01-10, 2012-10-01
0x59150f1e: 2012-01-11, 2012-10-02
0x59160f1e: 2012-01-20, 2012-10-11
0x59170f1e: 2012-02-01, 2012-10-20
0x59180f1e: 2012-02-10, 2012-11-01
0x59280f1f: 2012-01-12, 2012-10-03
0x59290f1f: 2012-01-21, 2012-10-12
0x592c0f1f: 2012-02-20, 2012-11-11
0x592d0f1f: 2012-03-01, 2012-11-20
0x592e0f1f: 2012-03-10, …

我必须找到2 ^ 25个随机字符串的SHA256哈希值.然后寻找碰撞(使用生日悖论的最后一个,比如说只有50位的散列).

我在dict变量中存储字符串:hash对.然后使用值(而不是键)对变量进行排序,然后使用O(n)循环查找冲突.

问题是因为有2 ^ 25个字符串和它们的2 ^ 25个哈希值,所以dict变量中有2 ^ 50个值.这是非常耗费资源的.那么,我如何使用有限的RAM(例如1GB左右)来做到这一点？

我已经尝试过:
1.使用6GB交换空间运行它.该程序一夜之间运行,但仍未完成.这基本上比O(n_square)搜索更慢!哈希计算的RAM使用量约为3.2 GB.但在那之后,当涉及到sort命令时,使用的RAM再次开始拍摄!我虽然python排序使用In-Place-Quicksort :(
2.我只存储了哈希并发现了一个碰撞.但由于没有存储它,所以找不到相应的字符串.

我不应该使用数据库等.最多是一个文本文件,但这没有帮助.另外,我对Python很新,但不要限制你的答案水平.

PS:这是一项任务.有人声称在一分钟内发现了300MB RAM的冲突.不知道这是不是真的.我已经解决了问题,但答案无法实现!在工作中,所以现在无法访问代码.将很快添加.

码:

from Crypto.Hash import SHA256
import os
import random
import string
from operator import itemgetter

def shaa():

    trun=[]
    clist={}
    for i in range(0,33554432):

        sha=SHA256.new(str(i)).hexdigest()
        sha=int(bin(int(sha,16))[-50:],2)
        clist[i]=sha

    print 'Hashes done.'

    clist=sorted(clist.items(), key=itemgetter(1))  
    for i in range(0,33554432):

        if(clist[i]==clist[i+1]):
            #print string[i],string[i+1]
            print clist[i]
            return 1
    return 2

result=2
while(result==2):
    result=shaa()

我有一个代码,使用循环多项式滚动哈希(Buzhash)来计算n-gram源代码的哈希值.如果我使用小哈希值(7-8位),则存在一些冲突,即不同的n-gram映射到相同的哈希值.如果我将哈希值中的位增加到31,则有0次冲突 - 所有ngrams都映射到不同的哈希值.

我想知道为什么会这样？碰撞是否取决于文本中的n-gram数量或n-gram可以具有的不同字符数量,还是n-gram的大小？

如何在散列n-gram时使用滚动哈希值选择哈希值的位数？

这基本上是一个数学问题,但编程很相关:如果我有10亿个包含URL的字符串,并且我采用每个字符串的MD5哈希的前64位,我应该期望什么样的冲突频率？

如果我只有1亿个网址,答案会如何变化？

在我看来,碰撞将非常罕见,但这些事情往往令人困惑.

使用MD5以外的其他东西会更好吗？请注意,我不是在寻找安全性,只是一个很好的快速哈希函数.此外,MySQL中的本机支持很好.

编辑:不太重复

散列函数中的多重碰撞与第一或第二前映像之间的区别是什么.

• 第一个preimage攻击:给定一个哈希h,找到一个这样的消息

  hash(m)= h.

• 第二个preimage攻击:给定一个固定的消息m1,找到一个不同的消息m2

  hash(m2)= hash(m1).

• 多冲突攻击:生成一系列消息m1,m2,... mN,这样

  hash(m1)= hash(m2)= ... = hash(mN).

维基百科告诉我们,preimage攻击与碰撞攻击的不同之处在于存在被攻击的固定哈希或消息.

令我感到困惑的是那些make语句如下:

这些技术不仅有效地搜索碰撞,而且还适用于探索MD4的第二原像.关于第二个原像攻击,他们发现随机消息是一个概率为2 ^ -122的弱消息,它只需要一次性的MD4计算来找到对应于弱消息的第二个原像.

对MD4的第二次原像攻击

如果我理解作者似乎在说的是他们已经开发了一个多冲突攻击,其中包含一组足够大的消息,这些消息给出了随机消息,那么它与其中一个消息重叠的可能性非常小.碰撞.

我在许多论文中看到了类似的论点.我的问题是什么时候攻击不再是多次碰撞攻击并成为第二次原像攻击

• 如果多次碰撞与2 ^ 300其他消息发生碰撞,那么它会被计为第二个原像,因为多次碰撞可以用来计算它碰撞的其中一个消息的"前映像"吗？分界线在哪里,2 ^ 60,2 ^ 100,2 ^ 1000？

• 如果您可以生成以23开头的所有哈希摘要的原像,该怎么办？当然它不符合preimage的严格定义,但它也是加密哈希函数中的一个严重缺陷.

• 如果某人有大的多次碰撞,那么他们总能恢复与多次碰撞相冲突的任何消息的图像.例如,

  hash(m1)= hash(m2)= hash(m3)= h

  有人请求h的原像,他们用m2回复.什么时候停止愚蠢并成为真正的攻击？

经验法则？知道有关评估哈希函数攻击的任何好资源吗？

相关链接:

• HASH COLLISION Q&A
• 密码哈希
• eHash主页

根据各种来源,例如维基百科和谷歌发现的各种.edu网站,哈希表解决冲突的最常见方式是线性或二次探测和链接.简要提及随机探测,但没有给予太多关注.我已经实现了一个使用随机探测来解决冲突的哈希表.假设存在冲突,解决方案的工作方式如下:

1. 对象的完整(32位)散列用于为线性同余随机数生成器设定种子.
2. 生成器生成32位数字,并采用模数来确定哈希表中接下来要探测的位置.

这具有非常好的属性,无论模数空间中有多少哈希冲突,只要在完整的32位哈希空间中存在很少的冲突,查找和插入时间预期为O(1).由于探测序列是伪随机的,因此与线性探测不同,模数空间碰撞不会产生聚类行为.由于整个系统是开放式地址,并且不在任何地方使用链接列表,因此与链接不同,您不需要在每次插入时执行内存分配.

此外,因为散列的大小通常是地址空间的大小(32位机器上的32位),所以根本不可能在地址空间中容纳足够的项以在完整的32位散列中导致大量的散列冲突良好的哈希方案下的空间.

那么,为什么随机探测这种不受欢迎的碰撞解决策略呢？

当负载因子接近1时,哪种hashmap冲突处理方案更好,以确保最小的内存浪费？

我个人认为答案是使用线性探测进行开放式寻址,因为在发生冲突时不需要任何额外的存储空间.它是否正确？

我想知道将一堆MD5哈希值散列在一起以创建新哈希是否"安全",或者这是否会以任何方式增加冲突的概率.

背景:我有几个依赖的文件.每个文件都有一个关联的哈希值,该哈希值是根据它的内容计算的.我们称之为"单文件"哈希值.除此之外,该文件还应具有包含所有相关文件的哈希值,即"多文件"哈希值.

所以问题是:我可以只取相关文件的所有单文件MD5哈希值,连接它们,然后在连接值上计算MD5以获得多文件哈希值.或者这会导致MD5哈希比我将所有相关文件的内容连接在一起更容易发生冲突.

或者,我可以将单个文件哈希值合并在一起以生成多文件哈希值,或者这可能会导致更多冲突吗？

我有这个公式:

index = (a * k) % M

它将数字'k'从不同数字的输入集K映射到哈希表中的位置.我想知道如何编写一个非暴力程序,找到这样的'M'和'a',使'M'最小,并且给定的集合K没有碰撞.