能否获得相同的SHA1哈希值？

Question

给定两个不同的字符串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等信息。

- Andriy Drozdyuk

---

由于SHA-1算法生成的摘要长度为160位，因此对于一个固定的字符串来说，发生碰撞的概率始终高于2^-160。 - kennytm

这个想法听起来不错，伙计，但是为什么呢？虽然你可以。 - tony9099

@tony9099，这不仅仅是一个想法了，对吧？ - Patrick Bassut

因为现在存在一种非暴力攻击方式来创建相同的SHA1哈希值，所以被提名重新开放。 - 1615903

对于SHA-1在输入“S1”和“S2”不同的情况下产生相同结果的示例，请参见https://shattered.io/ - 生成哈希碰撞需要6500个CPU年和100个GPU年的组合工作，因此生成其他碰撞尚未被认为是容易的。谷歌支付了该项目以实践证明SHA-1不再适用于加密目的。它仍然可以用于校验和，例如验证文件在传输过程中是否损坏。 - Mikko Rantalainen

Answer 1

您所描述的被称为“碰撞”。碰撞是必然存在的，因为SHA-1接受的许多不同消息作为输入要比它可以产生的不同输出多（SHA-1可以吃掉最多2^64位的任何位字符串，但仅输出160位；因此，至少一个输出值必须多次出现）。这个观察结果对于任何输出小于其输入的函数都有效，无论该函数是“好”的哈希函数还是其他函数。

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

（这是2^80而不是2^160，因为使用2^80个字符串，您可以生成约2^159对字符串。这通常被称为“生日悖论”，因为当应用于生日碰撞时，它会让大多数人感到惊讶。请参见维基百科页面上的相关内容。）

现在我们强烈怀疑SHA-1并不像随机预言机那样行为，因为生日悖论方法是随机预言机的最佳碰撞搜索算法。然而，有一种已经公开的攻击应该在大约2^63步骤内找到一个碰撞，比生日悖论算法快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位的字符串，则此类概率相当无意义。

- Thomas Pornin

---

如果你使用40位的输入字符串进行哈希，那么它们产生相同值的概率非常低。但是你需要耗费几天或几周的时间用计算机穷举所有可能性来确定是否真的不存在碰撞（对于40位字符串，这是可行的）。当然，如果没有发生碰撞，那么你实际上拥有一个从所有字符串到不同160位值的映射。对于“隐藏敏感信息”，关键词是“机密性”，你应该研究加密而不是哈希。 - Thomas Pornin

我发现意识到大多数国家公共彩票中获胜的几率惊人地小，但奖金通常每周或在几周内支付，所以无论几率多么小，它们都会发生，这有助于理解。2^-x可能是一个非常小的数字，但是没有确定性，无论碰撞是否会发生。或者确切地说：2^-x既不是一也不是零。同样，尽管机会很小，但没有任何阻止hash（1）与hash（2）匹配，无论您对其进行何种限制。 - andora

在撰写本文时，单向函数是否存在仍然是一个开放的理论问题。如果不存在，则在多项式时间内可计算的每个哈希函数都容易受到碰撞攻击的威胁。 - Tim Seguine

这里没有提到的一件事是，虽然有大量的字节流会与任何给定的字节流发生碰撞，但其中非常少的字节流是有效的名称（如您的示例）或有效的代码（如git示例）。因此，在真正随机的输入空间中，碰撞的概率为2^(-160)，但输入空间通常不是随机的。我对自己的统计技能不够自信，无法权威地说这使得碰撞的可能性更小，但我认为它可能确实如此，并且在很大程度上是如此。 - bodgesoc

https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html - tony9099

Answer 2

是的，这是可能的，因为有鸽巢原理的存在。

大多数哈希函数（包括sha1）具有固定的输出长度，而输入则是任意大小的。因此，如果你尝试足够长的时间，就可以找到它们。

然而，密码哈希函数（例如sha-family、md-family等）旨在最小化这种碰撞的发生。已知的最佳攻击需要 2^63 次尝试才能找到碰撞，因此在实践中机会是2^(-63)，也就是几乎为0。

- Henri

---

我刚打算在编辑我的回答时提到鸽巢原理。哈哈，我现在要撤掉它，因为看起来像是我抄袭了你。 - AaronLS

最好的攻击需要2^63个工作量，并不意味着任意两个哈希发生碰撞的机会是1/2^63，所有已知的攻击都需要构造两个发生碰撞的消息，而不是找到一个原像。 - Nick Johnson

Answer 3

git使用SHA1哈希作为ID，截至2014年仍未发现已知的SHA1冲突。显然，SHA1算法是神奇的。我认为，如果你的字符串长度不太长，那么冲突就不存在，因为如果存在的话，它们早就被发现了。但是，如果你不相信魔法，也不想赌博，你可以在DB中生成随机字符串并将其与ID关联起来。但是，如果你使用SHA1哈希，并成为第一个发现冲突的人，你可以在那时更改系统以使用随机字符串，保留SHA1哈希作为遗留ID的“随机”字符串。

- Vlad Kornea

---

截至今天，SHA1已经有了公开的碰撞：https://shattered.it/ - Dave L.

Answer 4

一个散列函数中几乎总会发生碰撞。到目前为止，SHA1在生成不可预测的碰撞方面非常安全。危险在于当可以预测碰撞时，不需要知道原始哈希输入就可以生成相同的哈希输出。

例如，去年针对MD5的攻击针对SSL服务器证书签名，如Security Now播客第179集所示。这使得高级攻击者可以为伪造的网站生成虚假的SSL服务器证书，并伪装成真正的东西。因此，强烈建议避免购买MD5签名的证书。

- spoulson

Answer 5

你所说的是碰撞。以下是有关SHA1碰撞的文章：http://www.rsa.com/rsalabs/node.asp?id=2927。

编辑：另一个回答者提到了鸽巢原理，但为了澄清，这就是为什么它被称为鸽巢原理，因为如果你有一些凿出来供邮鸽筑巢的洞口，但是你有更多的鸽子而不是洞口，那么一些鸽子（输入值）必须共享一个洞口（输出值）。

- AaronLS