cryptography - 是否有可能获得相同的 SHA1 哈希值？

Question

这个问题已经有答案了:

Probability of SHA1 collisions (3 个回答)

已关闭 6 年前。

给定两个不同的字符串 S1 和 S2 (S1 != S2) 是否可能:

SHA1(S1) == SHA1(S2)

这是真的吗？

1. 如果是 - 概率是多少？
2. 如果不，为什么不呢？
3. 输入字符串的长度是否存在上限，在该上限下出现重复的概率为 0？或者 SHA1 的计算(因此重复的概率)与字符串的长度无关？

我试图实现的目标是散列一些敏感的 ID 字符串(可能与其他一些字段(如父 ID)连接在一起)，以便我可以使用散列值作为 ID(例如在数据库中)。

示例:

Resource ID: X123
Parent ID: P123

我不想公开我的资源标识的性质以允许客户端看到“X123-P123”。

相反，我想创建一个新的列哈希(“X123-P123”)，假设它是 AAAZZZ。然后客户端可以请求 id 为 AAAZZZ 的资源，而不知道我的内部 id 等。

Answer 1

您所描述的称为碰撞。冲突必然存在，因为 SHA-1 接受更多不同的消息作为输入，它可以产生不同的输出(SHA-1 可以吃掉最多 2^64 位的任何位串，但仅输出 160 位；因此，至少有一个输出值必须弹出几次)。此观察结果对于输出小于输入的任何函数都有效，无论该函数是否是“好的”哈希函数。

假设 SHA-1 的行为类似于“随机预言机”(一个基本上返回随机值的概念对象，唯一的限制是一旦它在输入 m< 上返回输出 v/em>，此后它必须始终在输入 m 上返回 v)，那么对于任意两个不同的字符串 S1 和 S2，碰撞概率应为 2^(- 160)。仍然在 SHA-1 表现得像随机预言的假设下，如果您收集许多输入字符串，那么您将在收集大约 2^80 个这样的字符串后开始观察冲突。

(这是 2^80 而不是 2^160，因为使用 2^80 个字符串，您可以生成大约 2^159 对字符串。这通常被称为“生日悖论”，因为当适用于生日时的碰撞。有关该主题，请参阅 the Wikipedia page。)

现在我们强烈怀疑 SHA-1 的行为确实不像随机预言，因为生日悖论方法是随机预言的最佳碰撞搜索算法。然而，有一个已发布的攻击应该在大约 2^63 步内找到碰撞，因此比生日悖论算法快 2^17 = 131072 倍。对于真正的随机预言机来说，这样的攻击不应该是可行的。请注意，这次攻击实际上尚未完成，它仍然是理论上的(有些人 tried but apparently could not find enough CPU power )(更新:截至 2017 年初，有人确实计算了 SHA-1 collision使用上述方法，并且效果与预期完全一致)。然而，这个理论看起来很合理，而且 SHA-1 确实不是一个随机预言。相应地，至于碰撞的可能性，嗯，所有的赌注都没有。

关于你的第三个问题:对于一个具有n位输出的函数，如果你可以输入超过2^n个不同的消息，那么必然会发生冲突，即如果最大输入消息长度大于n。由于边界 m 低于 n，答案并不那么容易。如果函数表现为随机预言，则碰撞存在的概率会随着 m 降低，并且不是线性降低，而是在 m=n/2 附近急剧截止>。这与生日悖论的分析相同。对于 SHA-1，这意味着如果 m < 80 则很可能不存在冲突，而 m > 80 则很可能存在至少一次冲突( m > 160 这成为必然)。

请注意，“存在碰撞”和“您发现碰撞”之间是有区别的。即使碰撞必须存在，每次尝试的概率仍然是 2^(-160)。上一段的意思是，如果你不能(概念上)尝试 2^160 对字符串，那么这样的概率就毫无意义。因为您将自己限制为少于 80 位的字符串。