哈希碰撞 - 发生的几率有多大？

Question

哈希碰撞 - 发生的几率有多大？

database-designhash

27

我在使用 PHP 的网站上编写了一些代码来创建一个随机散列值 (使用sha1())，并将其用于匹配数据库中的记录。

这种情况发生碰撞的几率是多少？我应该先生成哈希值，然后检查它是否在数据库中(我宁愿避免额外的查询)，还是根据它与其他数据发生碰撞的概率自动插入记录。

- alex

11

问一下，如果发生碰撞会花费你多少钱。如果这是一个免费的网站那就没问题。但如果你经营的是一个盈利性企业，而碰撞会导致你失去价值一百万美元的合同，那么你应该再三考虑。 - Martin York

如果您必须在URL中混淆某些数据以隐藏数据，则表示您正在做一些错误的事情。 - Arkh

为什么？想象一种情况，你正在销售数字商品，这些商品可以通过API访问。有些是定价的，有些不是。这是通过URL最好的方式来引用它们，而不需要用户更改URL并获取其他“未经授权”的应用程序进行下载。 - Faisal Abid

或者你可以实现访问级别，并在将数据盲目发送给他们之前检查人们是否有权访问您的数据。是的，你需要付出一些努力去做这件事，但你是为此而付费的，而不是通过已经失败了足够多次的安全性来实现安全性。永远不要相信来自用户的数据。 - Arkh

我倾向于同意这个观点。虽然在某些情况下，散列数据并关注其唯一性非常重要（例如，Mercurial ID），但如果出于安全原因必须隐藏ID，则这是一种非常危险的安全模型。如果您不需要这样做，为什么还要费心呢？ - dimo414

这里有一个明显的反例：密码重置URL。当你有多个元素协同工作时，它通常被认为是安全的。用户获得的东西 - 重置URL；他们知道或拥有的东西 - 控制他们的电子邮件地址和/或秘密问题的答案；他们必须做的事情 - 在重置电子邮件过期之前回复。 - Patrick M

11个回答

15

使用对称加密方案和私有服务器密钥对ID（以及其他值）进行加密，然后在收到时解密。要注意，您的加密函数应同时提供机密性和完整性检查。

这使您可以在与数据库通信时使用合理的值而不会产生任何冲突，在与客户端通信时提供更高的安全性，并将您降落在thedailyWTF的概率减少了2^160次方左右。

另请参见Pounding A Nail: Old Shoe or Glass Bottle?！

- David Schmitt

14

为什么不做一些能够保证没有冲突的事情，同时确保没有人可以更改GET参数来查看他们不应该查看的内容：使用盐值，将ID和其哈希组合在一起。

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

即使您意外地遇到两个具有相同SHA1哈希（使用您的盐）的数字，那么$key仍将不同，您将避免所有冲突。

- nickf

1

最好使用HMAC（在PHP中为hash_hmac），据说可以解决这种简单方案的一些弱点。http://en.wikipedia.org/wiki/HMAC - araqnid

5

如果您使用递增的数字ID作为输入，则SHA-1发生碰撞的几率几乎为零。

如果ID是唯一的输入，那么似乎使用SHA-1有些过度 - 从32位整数生成一个160位哈希值。我更愿意使用模幂运算，例如选择一个大的（32位）质数p，计算该组的模发生器g，然后使用g^id。这将保证无碰撞，并且只给出32位的“哈希值”。

- Martin v. Löwis

id不是唯一的输入。还有一些特定的数据和time() rand()来稍微混合一下。 - alex

2

只需生成160个随机比特位即足够独特——无需对任何内容进行哈希处理（它不会因哈希而更具独特性，也不会变得更随机）。 - Martin v. Löwis

4

SHA-1生成160位长的摘要。因此，只要你的条目少于2^(160/2)，你就是安全的。除以2是由于生日悖论。

- Szere Dyeri

8

“安全”这个词肯定是一个相对的概念。它不是说到了某个点就变得“安全”，然后再变得“不安全”。只有在特定点上讨论碰撞发生的可能性才有意义。原作者可能需要“百万分之一或以上的机会”，或者他可能需要“十亿分之一”的机会。 - Jon Skeet

@Szere Dyeri 记住，随机性是不可预测的 :) - Robert Gould

1

Jon，你是对的。更准确地说，在发生冲突之前可以生成的N位哈希数的期望数量是2^(N/2)，其中期望是分布的正式一阶统计量。 - Szere Dyeri

4

从最基本的原理来说：

SHA-1可以生成一个160位的摘要。假设它平均使用了整个比特空间（这应该是它设计时的考虑），每次插入的碰撞概率只有2^-160。

因此，对于每个插入操作，我们可以安全地假设没有碰撞，并在出现碰撞时处理错误。

但这并不意味着你可以完全忽略碰撞的可能性。

生日悖论表明，在你的数据库中至少有一次碰撞的机会比你想象的要高，因为有O(N^2)种可能的碰撞。

- Oddthinking

生日悖论将碰撞的机会提高到了0.00000000000000000017347234759768070944119244813919％。真的不值得担心。 - Jeff Hubbard

3

杰夫，我承认在几乎所有情况下都可以忽略碰撞风险。之前我没有进行计算。但是，你没有提及收集中有多少对象，所以你对碰撞概率的估计有些无意义。 - Oddthinking

1

有一个非常简单的规则可以找出任何哈希算法是否会发生冲突。 如果算法的输出范围是有限的数字，迟早会发生冲突。

尽管SHA1具有2^160个哈希可能性的非常大的范围，但它仍然是有限的数字。然而，可以传递给该函数的输入实际上是无限的。在足够大的输入数据集中，必定会发生冲突。

- Ketan Patil

1

问一下如果发生碰撞会花费多少钱。如果这是一个免费的网站那就没问题了。但如果你经营的是赚钱的业务，而覆盖将使你失去一份价值百万美元的合同，那么我认为你需要重新考虑。

我认为你的方法不对。
我认为你需要保留唯一标识符，但要确保用户无法手动更改该标识符。

一种方法是将ID和ID的哈希值（加上一些额外数据）放在链接中。

例如：（我的PHP有点生疏，所以以下是通用算法:）

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

那么当你收到请求时，只需验证您可以根据ID重新生成哈希。这确实让您容易受到攻击，以找出"My Private String"，但这将是相当计算困难的，您可以始终附加其他不直接向用户公开的唯一内容（例如会话ID）。

- Martin York

0

其他评论已经涵盖了概率问题，但是如果你从实际角度来看待这个问题，你可以为自己得到一个明确的答案。

你自己说过，你将要对连续的ID进行哈希。编写一个测试用例很容易。迭代 ~100,000,000 个 ID 并检查碰撞。这不需要太长时间。另一方面，你可能会在四分之一的时候就耗尽内存。

- Josh

0

我觉得 sha1() 在这里不会给你带来任何麻烦，较弱的随机数生成更可能成为碰撞的候选者。

Stefan Esser 写了一篇关于这个主题的好文章。

- Waquo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artelius · Accepted Answer

如果你认为SHA-1做得很好，那么你可以得出这样的结论：两个给定消息具有相同哈希的概率为2^160分之1（因为SHA-1生成160位哈希）。

2^160是一个极其庞大的数字，大约是10的48次方。即使在数据库中有一百万个条目，新条目共用相同哈希值的概率仍然是10的42次方分之1。

SHA-1已被证明相当不错，因此我认为您根本不需要担心冲突问题。

顺便说一句，在使用SHA-1时，请使用PHP的raw_output功能，因为这将导致字符串更短，从而使数据库操作更快一些。

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