给定两个不同的字符串 S1 和 S2 (S1 != S2) 是否有可能：
SHA1(S1) == SHA1(S2)
是真的？
我试图实现的目标是散列一些敏感的 ID 字符串（可能与父 ID 等其他一些字段连接在一起），以便我可以使用散列值作为 ID（例如在数据库中）。
例子：
Resource ID: X123
Parent ID: P123
我不想公开我的资源标识的性质以允许客户看到“X123-P123”。
相反，我想创建一个新的列哈希（“X123-P123”），假设它是 AAAZZZ。然后客户端可以请求 ID 为 AAAZZZ 的资源并且不知道我的内部 ID 等。
您所描述的称为碰撞。冲突必然存在，因为 SHA-1 接受更多不同的消息作为输入，它可以产生不同的输出（SHA-1 可以吃掉最多 2^64 位的任何位串，但只输出 160 位；因此，至少有一个输出value 必须弹出多次）。这个观察对于任何输出小于输入的函数都是有效的，不管这个函数是否是一个“好”的散列函数。
假设 SHA-1 的行为类似于“随机预言机”（一个基本上返回随机值的概念对象，唯一的限制是，一旦它在输入m上返回输出v，此后它必须始终在输入m上返回v），那么对于任何两个不同的字符串 S1 和 S2，碰撞概率应为 2^(-160)。仍然假设 SHA-1 表现得像一个随机预言机，如果您收集许多输入字符串，那么您将在收集大约 2^80 个这样的字符串后开始观察冲突。
（这是 2^80 而不是 2^160，因为使用 2^80 个字符串，您可以制作大约 2^159 对字符串。这通常被称为“生日悖论”，因为当应用于碰撞时，大多数人都会感到惊讶生日。请参阅有关该主题的 Wikipedia 页面。）
现在我们强烈怀疑 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 位的字符串，那么这样的概率是毫无意义的。
是的，这是可能的，因为鸽子洞原理。
大多数哈希（也是 sha1）具有固定的输出长度，而输入是任意大小。因此，如果您尝试足够长的时间，您可以找到它们。
但是，密码散列函数（如 sha 系列、md 系列等）旨在最大限度地减少此类冲突。已知的最佳攻击需要 2^63 次尝试才能找到碰撞，因此机会为 2^(-63)，在实践中为 0。
git使用 SHA1 哈希作为 ID， 2014 年仍然没有已知的 SHA1 冲突。显然，SHA1 算法很神奇。我认为对于您的长度的字符串不存在碰撞是一个不错的选择，因为它们现在已经被发现了。但是，如果您不相信魔法并且不是赌徒，您可以生成随机字符串并将它们与您数据库中的 ID 相关联。但是，如果您确实使用 SHA1 哈希并成为第一个发现冲突的人，您可以更改您的系统以在那时使用随机字符串，保留 SHA1 哈希作为旧 ID 的“随机”字符串。
在散列函数中几乎总是可能发生冲突。迄今为止，SHA1 在生成不可预测的冲突方面非常安全。危险在于，当可以预测碰撞时，无需知道原始哈希输入即可生成相同的哈希输出。
例如，去年针对 SSL 服务器证书签名进行了针对 MD5 的攻击，例如Security Now播客第 179 集。这使得老练的攻击者能够为流氓网站生成伪造的 SSL 服务器证书，并且看起来是真实的东西. 因此，强烈建议避免购买 MD5 签名的证书。
你所说的叫做碰撞。这是一篇关于 SHA1 冲突的文章： http ://www.rsa.com/rsalabs/node.asp?id=2927
编辑：所以另一个回答者比我提到鸽子洞原理大声笑，但要澄清这就是为什么它被称为鸽子洞原理，因为如果你有一些洞可以让信鸽筑巢，但你的鸽子比洞多，那么一些鸽子（输入值）必须共享一个洞（输出值）。