哈希碰撞 – 有什么机会？

我有一些PHP动力网站上的代码，它创build了一个随机哈希（使用sha1() ），我用它来匹配数据库中的logging。

碰撞的几率是多less？我应该生成哈希，然后检查它是否在数据库中（我宁愿避免一个额外的查询）或自动插入它，基于它可能不会与另一个相撞的可能性。

如果你认为SHA-1做得好，你可以得出结论：有两个给定的消息具有相同的散列值（因为SHA-1产生一个160位散列值）。

2 ^ 160是一个可笑的大数目。大约10 ^ 48。即使你的数据库中有一百万个条目，那么这个条目仍然有10/42的概率，一个新的条目将共享相同的散列值。

SHA-1已经certificate是相当好的，所以我不认为你需要担心碰撞。

请注意，当使用SHA-1时，请使用PHP的raw_outputfunction，因为这会导致string更短，因此会使数据库操作更快一些。

编辑：为了解决生日悖论，一个数据库10 ^ 18（百万万）的条目有一个在0.0000000000003的碰撞约1的机会。真的不值得担心。

使用对称encryptionscheme和专用服务器密钥将ID（和其他值）encryption到客户端，并在接收时再次解密。注意你的encryption函数提供了机密性和完整性检查。

这使您在与客户交谈时可以使用合理的价值而不会发生任何冲突 ，与客户交谈时有很高的安全性，并降低了以大约2 ^ 160的价格登陆日常WFT的可能性。

又见Pound钉子：旧鞋或玻璃瓶？！

为什么不做一些保证不会发生冲突的事情，以及确保没有人能够更改GET参数来查看他们不应该做的事情：使用salt，将ID和它的散列组合起来。

 $salt = "salty"; $key = sha1($salt . $id) . "-" . $id; // 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5

即使你不小心偶然发现了两个与sha1 hash相同的数字（用你的salt），那么$ key仍然是不同的，你将避免所有的冲突。

如果使用数字递增的ID作为input，则SHA-1将碰撞的机会几乎为零。

如果ID是唯一的input，那么SHA-1似乎有点矫枉过正 – 从一个32位整数产生一个160位的散列。我宁愿使用模幂运算，例如select一个大的（32位）素数p，计算该组的模数生成器g，然后使用g ^ id。这将保证无冲突，只给32位“散列”。

SHA-1产生160位长的摘要。因此只要您less于2 ^（160/2）个条目，您就安全了。 2分是由于生日悖论。

从第一原则：

SHA-1产生一个160位的摘要。假设它均匀地使用整个比特空间（这大概是它devise的目的），那么在每个插入物上只有2 ^ -160的机会会碰撞。

因此，对于每个插入，假定没有碰撞应该是安全的，并且如果存在则处理错误。

这并不是说你可以完全忽略碰撞的可能性。

生日悖论表明，由于O（N ^ 2）可能的冲突，数据库中至less有一次碰撞的机会比你想象的要高。

如果您必须混淆url中的某些数据才能隐藏数据，则表示您做错了什么。

问这个问题，如果发生碰撞，会花费多less钱。如果这是一个免费的网站罚款。如果你正在经营一个赚钱的生意，一个贱货将花费你一百万美元的合同，那么我会再想一想。

我认为你正在做这个错误的方式。
我认为你需要保持唯一的ID，但是你想确保用户不能手动改变ID。

要做到这一点的一种方法是把ID和散列的ID（与一些额外的数据）在链接。

例如：（我的PHP是生锈的，所以一般algorithm会:)

 id = 5; hash = hash("My Private String " + id) link = "http://mySite.com/resource?id=" + id + "&hash=" + hash

然后，当你收到一个请求，只是validation你可以从ID重新生成散列。这确实会让你打开一个攻击来制定“我的私人string”，但是这在计算上会非常困难，而且你总是可以添加一些不直接对用户可用的东西（比如会话ID）。

有一个非常简单的规则来找出是否有哈希algorithm会有碰撞或没有。 如果一个algorithm的输出范围是一个有限数，那么迟早会有碰撞。

即使SHA1具有2 ^ 160哈希可能性的非常大的范围，它仍然是有限的数目。但是，可以在该函数上传递的input字面上是无限的。给定足够大的input数据集，碰撞必然会发生。

其他评论已经涵盖了你的概率，但是如果你务实地看待这个问题，那么你可以得到一个明确的答案。

你自己说过，你将会哈希你的连续ID。编写testing用例很容易。通过〜100,000,000个ID来迭代并检查碰撞。这不需要很长时间。另一方面，你可能会耗尽内存四分之一的方式。

我不认为sha1（）在这里会给你带来麻烦，弱随机数的产生更可能是碰撞的候选者。

Stefan Esser在这个话题上写了很好的文章。