是否可以获得相同的SHA1哈希？

Question

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

SHA1(S1) == SHA1(S2)

是真的？

1. 如果是 - 有什么概率？
2. 如果没有 - 为什么不呢？
3. 输入字符串的长度是否有上限,获取重复的概率为0？OR是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的行为类似于"随机oracle"(一个基本上返回随机值的概念对象,唯一的限制是,一旦它在输入m上返回输出v,它必须始终在输入m上返回v),然后对于任何两个不同的串S1和S2,碰撞概率应为2 ^( - 160).仍然假设SHA-1表现得像一个随机的oracle,如果你收集了很多输入字符串,那么你应该在收集了大约2 ^ 80个这样的字符串之后开始观察碰撞.

(那是2 ^ 80而不是2 ^ 160因为,有2 ^ 80个字符串,你可以制作大约2 ^ 159对字符串.这通常被称为"生日悖论",因为当应用于碰撞时,它对大多数人来说是一个惊喜在生日上.请参阅有关该主题的维基百科页面.)

现在,我们强烈怀疑,SHA-1并没有真正像一个随机预言,由于生日悖论的方法是随机预言的最佳碰撞搜索算法.然而,已发布的攻击应该在大约2 ^ 63步中发现碰撞,因此比生日悖论算法快2 ^ 17 = 131072倍.在真正的随机预言中,这样的攻击不应该是可行的.请注意,这次攻击尚未实际完成,它仍然是理论上的(有些人尝试但显然找不到足够的CPU能力)(更新:截至2017年初,有人确实用上述方法计算了SHA-1碰撞,它完全像预测的那样工作).然而,理论看起来很健康,而且看来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位的字符串.

Answer 2

是的,因为鸽子洞的原则是可能的.

大多数哈希(也是sha1)具有固定的输出长度,而输入具有任意大小.所以如果你尝试的时间足够长,你可以找到它们.

但是,加密散列函数(如sha-family,md-family等)旨在最大限度地减少此类冲突.已知的最佳攻击需要2 ^ 63次尝试才能找到碰撞,所以机会是2 ^( - 63),实际上是0.

Answer 3

git使用SHA1哈希作为ID，2014年仍然没有已知的SHA1冲突。显然，SHA1算法是不可思议的。我认为这是个不错的选择，因为长度不长的字符串不存在碰撞，因为它们现在已经被发现。但是，如果您不信任魔术并且不是博彩人，则可以生成随机字符串，并将其与数据库中的ID关联。但是，如果您确实使用SHA1哈希并成为第一个发现冲突的人，则可以将系统更改为当时使用随机字符串，而将SHA1哈希保留为旧ID的“随机”字符串。

Answer 4

在散列函数中几乎总是可能发生冲突。迄今为止，SHA1 在产生不可预测的冲突方面已经非常安全。危险在于，当可以预测冲突时，无需知道原始哈希输入即可生成相同的哈希输出。

例如，去年针对 SSL 服务器证书签名发起了针对 MD5 的攻击，例如Security Now播客第 179 集。这使得老练的攻击者能够为流氓网站生成伪造的 SSL 服务器证书，这似乎是真实存在的. 因此，强烈建议避免购买 MD5 签名的证书。