标签: hash-collision

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

• 第一个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主页

如果有人故意尝试修改两个文件以具有相同的哈希值,那么有什么方法可以阻止它们？md5和sha1可以阻止多数情况吗？

我正在考虑写自己的,我想如果用户不知道我的哈希,我可能无法愚弄我的做法,即使我做得不好.

防止这种情况的最佳方法是什么？

我正在阅读关于Hashtable类的Java api文档,并遇到了几个问题.在文档中,它说" 请注意哈希表是打开的:在"哈希冲突"的情况下,单个存储桶存储多个条目,必须按顺序搜索. "我自己尝试了以下代码

Hashtable<String, Integer> me = new Hashtable<String, Integer>();
me.put("one", new Integer(1));
me.put("two", new Integer(2));
me.put("two", new Integer(3));
System.out.println(me.get("one"));  
System.out.println(me.get("two"));

输出是

1
3

1. 这是"开放"的含义吗？
2. 整数2发生了什么？收集为垃圾？
3. 有一个"封闭"的例子吗？

我需要一个4个字符的哈希.目前我正在使用md5()哈希的前4个字符.我正在散列一个长度不超过80个字符的字符串.这会导致碰撞吗？或者,碰撞的几率是多少,假设我的哈希值小于65,536(16 ⁴)个不同的元素？

显然,由于SHA-1散列每次出现有限数量的可能哈希值时会产生40个字符 - 有没有人确切地知道有多少？

我正在尝试对哈希实施碰撞攻击(我正在访问课程'加密').因此,我有两个哈希数组(=字节序列byte[]),并希望找到两个数组中都存在的哈希值.经过一些研究和大量思考后,我确信单核机器上的最佳解决方案是HashSet(添加第一个数组的所有元素,并检查contains第二个数组的元素是否已经存在).

但是,我想实现并发解决方案,因为我可以访问具有8个内核和12 GB RAM的计算机.我能想到的最好的解决方案是ConcurrentHashSet,可以通过它创建Collections.newSetFromMap(new ConcurrentHashMap<A,B>()).使用这个数据结构,我可以并行地添加第一个数组的所有元素,并且 - 在添加了所有元素之后 - 我可以同时检查via contains以获得相同的哈希值.

所以我的问题是:你知道为这个确切问题设计的算法吗？如果没有,您是否有使用此类ConcurrentHashSet有关问题和有效运行时复杂性的经验？或者你能推荐另一个可以帮助我的预建数据结构吗？

PS:如果有人对细节感兴趣:我打算使用Skandium来并行化我的程序.

我正在通过Java的hash方法实现put方法,并且遇到了这个:

// Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

虽然我知道需要一个密钥来检查冲突,但为什么Java存储密钥的哈希值并检查它？

我正在读关于Java的方法随机哈希键在这里
很显然的想法是,以确保在低位为"随机",以帮助分布,但我想明白这一点了.
因此,如果我们有一个大小为10的表,那么数字0,10,20,30,40等都落在桶0中,数字1,11,21,31等落在桶1等中(使用模10).
因此,改变位模式可以使它们进入不同的存储桶,而不是全部进入存储桶0.
但是我不清楚的是它是什么属性使得低阶位影响这一点,我们需要将它们随机化.所以我们有:

0000 0000 (0)  
0000 1010 (10)  
0001 0100 (20) 
0001 1110 (30)  
0010 1000 (40) 

低阶位的规律性是什么使它们被放置在同一个插槽中？
也许我对以下内容感到困惑？我的理解是,低阶位中的一些规律性会导致冲突,我们会尝试随机化比特来进行补偿

如何识别一个中的键是否std::unordered_map经历了哈希冲突？

也就是说，如何识别是否存在任何碰撞链？

相关链接:http://en.wikipedia.org/wiki/Hopscotch_hashing

跳房子哈希表似乎很棒,但我没有在文献中找到这个问题的答案:如果我的邻居大小为N并且(由于渎职或运气极差)会发生什么？我插入N + 1个元素,这些元素都是哈希同样的确切值？