问题标签 [hash-collision]

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

我正在考虑自己写，我想即使我做得不好，如果用户不知道我的哈希值，他也可能无法欺骗我的哈希值。

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

我有一个包含 5,651,744 行的表，主键由 6 列（int x 3、smallint、varchar(39)、varchar(2)）组成。我希望使用此表和另一个共享此主键的表以及添加的附加列但有 37m 行来提高性能。

为了添加一列来创建哈希键，我进行了分析，发现了 18,733 个冲突。

这大约是坏的两倍BINARY_CHECKSUM()

考虑到我覆盖的目标空间相对较小，这是否看起来太高（0.33%）？如果冲突如此之高，那么在连接中首先加入这个制造的密钥是否有好处，因为您仍然必须加入常规列以处理偶尔的冲突？

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

如果我只有 1 亿个 URL，答案会如何变化？

在我看来，碰撞将极为罕见，但这些事情往往令人困惑。

使用MD5以外的东西会更好吗？请注意，我不是在寻找安全性，只是一个很好的快速哈希函数。此外，MySQL 的原生支持也很好。

编辑：不完全重复

哈希函数中的多重冲突与第一或第二原像之间有什么区别。

• 第一次原像攻击：给定一个哈希 h，找到一条消息 m 使得

  哈希（m）= h。

• 第二原像攻击：给定一个固定的消息 m1，找到一个不同的消息 m2 使得

  哈希（m2）=哈希（m1）。

• 多重碰撞攻击：生成一系列消息 m1, m2, ... mN，这样

  哈希(m1) = 哈希(m2) = ... = 哈希(mN)。

维基百科告诉我们，原像攻击与碰撞攻击的不同之处在于，有一个固定的哈希或消息被攻击。

我对发表以下声明的论文感到困惑：

该技术不仅可以有效地搜索碰撞，而且还适用于探索 MD4 的第二原像。关于第二原像攻击，他们表明随机消息是概率为 2^–122 的弱消息，只需一次 MD4 计算即可找到与弱消息对应的第二原像。

MD4 的第二原像攻击

如果我理解作者似乎在说什么，他们开发了一种多重冲突攻击，其中包含足够大的消息集，给定一条随机消息，它与他们的多重冲突中的一个重叠的可能性很大，尽管非常小。碰撞。

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

• 如果多重冲突与 2^300 条其他消息发生冲突，这是否算作第二个原像，因为多重冲突可用于计算与之冲突的其中一条消息的“原像”？分界线在哪里，2^60、2^100、2^1000？

• 如果您可以生成所有以 23 开头的哈希摘要的原像，会怎样？当然它不符合原像的严格定义，但它也非常肯定是密码散列函数中的一个严重缺陷。

• 如果某人有一个大的多重冲突，那么他们总是可以恢复任何哈希与多重冲突冲突的消息的图像。例如，

  散列(m1) = 散列(m2) = 散列(m3) = h

  有人请求 h 的原像，他们以 m2 响应。这什么时候不再愚蠢而成为真正的攻击？

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

相关链接：

• 哈希碰撞问答
• 加密哈希
• eHash 主页

出于演示目的，有哪些字符串在散列时发生冲突的示例？MD5 是一个相对标准的散列选项，所以这就足够了。

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

输出是

1. 这就是“开放”的意思吗？
2. 整数 2 发生了什么？作为垃圾收集？
3. 有没有“封闭”的例子？

给定两条不同的消息，A 和 B（可能 20-80 个字符的文本，如果大小很重要的话），A 的 MD5 摘要与 B 的 MD5 摘要和 A 的 SHA1 摘要相同的概率是多少与 B 的 SHA1 摘要相同吗？那是：

假设没有恶意，即选择消息的目的不是为了发现冲突。我只是想知道这种情况自然发生的几率。

我认为机会“非常低”，但我不确定如何验证这一点。

更多信息：可能的消息池的大小受到限制，但很大（几亿）。生日悖论的情况正是我担心的。

This is more of a cryptography theory question, but is it possible that the result of a hash algorithm will ever be the same value as the source? For example, say I have a string:

If I get the SHA1 hash on it, the result is:

In theory, is there ever a case where these two values would match? I'm not asking about SHA1 specifically here - it's just my example. I'm just wondering if hashing algorithms are built in such a way as to prevent this.

假设我使用哈希来识别文件，所以我不需要它是安全的，我只需要尽量减少冲突。我在想我可以通过使用 SIMD 并行运行四个散列然后对最终结果进行散列来加速散列。如果哈希被设计为采用 512 位块，我只需单步执行文件，一次采用 4x512 位块并从中生成四个哈希；然后在文件的末尾，我将四个结果散列在一起。

我很确定这种方法会产生更差的哈希值......但是差多少？有没有粗略的计算？

根据各种来源，例如 Wikipedia 和 Google 发现的各种 .edu 网站，哈希表解决冲突的最常见方法是线性或二次探测和链接。简要提到了随机探测，但没有给予太多关注。我已经实现了一个使用随机探测来解决冲突的哈希表。假设发生碰撞，解决方法如下：

1. 对象的完整（32 位）散列用于播种线性同余随机数生成器。
2. 生成器生成 32 位数字并取模来确定哈希表中接下来要探测的位置。

这有一个非常好的特性，无论模数空间中有多少哈希冲突，只要完整的 32 位哈希空间中的冲突很少，查找和插入时间预计为 O(1)。因为探测序列是伪随机的，所以与线性探测不同，模空间冲突不会导致聚类行为。因为整个系统是开放寻址的并且不在任何地方使用链表，所以与链接不同，您不需要在每次插入时执行内存分配。

此外，由于散列的大小通常是地址空间的大小（在 32 位机器上为 32 位），因此在地址空间中容纳足够多的项是不可能在完整的 32 位散列中导致大量散列冲突的良好的散列方案下的空间。

那么，为什么要随机探索这种不受欢迎的冲突解决策略呢？