哈希碰撞 – 有什么机会?

我有一些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在这个话题上写了很好的文章 。