我在我的 PHP 驱动的网站上有一些代码，它创建了一个随机散列（使用sha1()），我用它来匹配数据库中的记录。
发生碰撞的可能性有多大？我应该生成哈希，然后首先检查它是否在数据库中（我宁愿避免额外的查询）还是自动插入它，基于它可能不会与另一个发生冲突的概率。
alex
问问题
17849 次
11 回答
28
如果您假设 SHA-1 做得很好，您可以得出结论，两条给定消息具有相同哈希的可能性为 2^160 分之一（因为 SHA-1 产生 160 位哈希）。
2^160 是一个大得离谱的数字。大约是 10^48。即使您的数据库中有一百万个条目，新条目共享相同哈希的机会仍然是 10^42 分之一。
SHA-1 已被证明相当不错，所以我认为您根本不需要担心碰撞。
附带说明一下，当您使用 SHA-1 时，请使用 PHP 的raw_output功能，因为这会导致字符串更短，从而使您的数据库操作更快一些。
编辑：为了解决生日悖论，具有 10^18（一百万）条目的数据库有大约 0.0000000000003 中的 1 发生碰撞的机会。真的不值得担心。
于 2008-11-18T06:03:26.763 回答
16
当您将 ID（和其他值）发送到客户端并在接收时再次解密时，使用对称加密方案和私有服务器密钥来加密它们。请注意您的加密函数提供机密性和完整性检查。
这允许您在与 DB 交谈时使用合理的值而不会发生任何冲突，在与客户端交谈时非常安全，并将您登陆thedailyWTF的概率降低大约 2^160。
另见敲钉子：旧鞋还是玻璃瓶？！
于 2008-11-18T08:35:40.013 回答
14
为什么不做一些保证不会发生冲突的事情，并确保没有人可以更改 GET 参数来查看他们不应该查看的内容：使用盐，结合 id 和它的哈希。
$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5
即使您不小心偶然发现了两个具有完全相同的 sha1 哈希（使用您的盐）的数字，那么 $key 仍然会有所不同，您将避免所有冲突。
于 2008-11-18T12:31:26.747 回答
5
如果您使用数字递增的 ID 作为输入，那么 SHA-1 碰撞的机会几乎为零。
如果 ID 是唯一的输入，那么 SHA-1 似乎有点矫枉过正——从 32 位整数生成 160 位散列。我宁愿使用模幂运算，例如选择一个大的（32 位）素数 p，计算该组的模生成器 g，然后使用 g^id。这将保证无冲突，并且仅提供 32 位“哈希”。
于 2008-11-18T06:07:23.183 回答
4
SHA-1 产生 160 位长的摘要。因此，只要您的条目少于 2^(160/2) 个，您就是安全的。除以 2 是由于生日悖论。
于 2008-11-18T06:03:52.490 回答
4
从第一原则：
SHA-1 产生一个 160 位的摘要。假设它均匀地使用整个位空间（这大概是它的设计目的），那么每次插入只有 2^-160 的机会会发生冲突。
所以对于每个插入，假设没有碰撞应该是安全的，如果有则处理错误。
这并不是说您可以完全忽略碰撞的机会。
生日悖论表明，由于 O(N^2) 可能的冲突，您的数据库中至少存在一次冲突的可能性比您猜测的要高。
于 2008-11-18T06:04:31.427 回答
1
问一个问题，如果发生碰撞，你会付出什么代价。如果这是一个免费网站很好。如果您正在经营一家赚钱的企业，而一项覆盖将花费您一百万美元的合同，那么我会再想一想。
我认为你正在以错误的方式解决这个问题。
我认为您需要保留唯一 ID，但要确保用户不能手动更改 ID。
执行此操作的一种方法是将 ID 和 ID 的哈希（带有一些额外数据）放入链接中。
例如：（我的 PHP 生锈了，所以一般算法是：）
id = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash
然后，当您收到请求时，只需验证您是否可以从 ID 重新生成哈希。这确实使您容易受到攻击以计算出“我的私人字符串”，但这在计算上将非常困难，并且您始终可以附加用户无法直接使用的其他独特内容（例如会话 ID）。
于 2008-11-18T08:20:50.183 回答
1
有一个非常简单的规则可以确定任何散列算法是否会发生冲突。如果算法的输出范围是有限数，那么迟早肯定会发生冲突。
即使 SHA1 具有非常大的 2^160 散列可能性范围，它仍然是一个有限的数字。但是，可以在该函数上传递的输入实际上是无限的。给定足够大的输入数据集，必然会发生冲突。
于 2017-10-04T11:48:59.547 回答
0
其他评论已经涵盖了您的概率，但是如果您务实地看待这一点，那么您可以自己得到明确的答案。
您自己说过您将散列您的顺序 ID。编写测试用例很容易。遍历约 100,000,000 个 id 并检查冲突。这不会花费很长时间。另一方面，您可能会用完四分之一的内存。
于 2008-11-18T08:35:34.197 回答
0
我认为 sha1() 在这里不会给您带来任何麻烦，弱随机数生成更有可能发生碰撞。
Stefan Esser 写了一篇关于这个话题的好文章。
于 2008-11-18T21:57:10.460 回答
0
发生碰撞的可能性有多大？
n 个散列与S不同的可能散列的总数碰撞的确切概率是：
（哈希函数的完美行为，生日悖论，等等等等……）
您将无法直接计算，因为这些数字很大，所以我们使用限制并做出 2 个假设：
有了这两个假设，碰撞的概率可以用以下公式计算：
现在您可以计算一些n条记录的冲突概率。对于 sha1 (S=2^160) 的任何少于 2^70 条记录，这非常准确，近似值越差，n越接近 2^80。
例子
例如，如果您要保存大量用户，特别是与世界上的人相同的数量（约 80 亿），并且您正在使用 sha1 (S=2^160)，那么发生冲突的概率为2.5e -29（注意两个假设成立）。给您一个参考，赢得 Euromillion 大奖的概率约为7e-9。
好奇心：如何处理更大（更大？！）的数字？
没有第二个假设，直接计算极限。
例如，第一次碰撞预计在S的平方根附近（在 sha1 n=2^80 的情况下）。在该值下，第二个条件不成立，但我们可以直接计算限制：
这是大约 40%。碰撞的概率。
于 2020-11-06T13:11:35.657 回答