6

我有一个数据库驱动的 Web 应用程序，其中所有数据行的主键都被混淆如下：SHA256（内容类型 + 主键 + 机密），截断为前 8 个字符。内容类型是一个简单的词，例如“post”或“message”，而秘密是一个 20-30 字符的 ASCII 常量。结果存储在单独的索引列中，以便快速查找数据库。

在这种情况下，如何计算哈希冲突的概率？我根本不是数学家，但一位朋友声称，由于生日悖论，10,000 行的 8 字符截断的碰撞概率约为 1%。这种说法有任何道理吗？

4

1 回答 1

8

是的，有一个碰撞概率，它可能有点太高了。确切的概率取决于“8 个字符”的含义。

“8 个字符”是否意味着：

  • A）您存储 8 个十六进制字符的哈希？那将存储 32 位。
  • B) 你存储 8 个 BASE-64 字符？那将存储 48 位。
  • C）您存储 8 个字节，以某种单字节字符集编码/或以某种破坏方式被破解为字符编码？那将存储 56-64 位，但如果您不正确编码，您将遇到字符转换问题。
  • D）你存储8个字节，作为字节？这真正存储了 64 位哈希。

将二进制数据存储为 A) 十六进制或 D) 二进制字节是我的首选。但我绝对建议重新考虑您的“密钥混淆”方案或显着扩展存储的密钥大小以减少（当前过度）密钥冲突的可能性。

来自维基百科： http ://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem

这种更一般意义上的生日问题适用于散列函数：在发生冲突之前可以生成的 N 位散列的预期数量不是 2^N，而是只有 2^(N/2)。

由于在对您的设计的最保守的上述理解中（将其读取为 A，8 个十六进制字符 == 32 位），如果您的方案以约 64,000 行的规模存储，则预计会遭受冲突。我认为这样的结果对于所有严肃的甚至是玩具的系统都是不可接受的。

事务表可能有数量，允许业务增长，从 1000 到 100,000 个事务/天（或更多）。系统应设计为可运行 100 年（36500 天），并内置 10 倍增长因子，因此..

为了使您的键控机制真正强大且专业有用，您需要能够将其扩展为可能处理约 360 亿 (2^35) 行而不会发生冲突。这意味着 70+ 位哈希。

例如，源代码控制系统 Git 存储 160 位 SHA-1 哈希（40 个十六进制字符 == 20 字节或 160 位）。存储的不同文件修订少于 2^80 个时，预计不会发生冲突。

更好的设计可能是，而不是完全散列和伪随机化密钥并希望（反对希望）以避免冲突，将 8-10 位散列预置/附加/折叠到密钥中。

这将生成一个更大的密钥，包含原始密钥的所有唯一性以及 8-10 位验证。然后将验证访问密钥的尝试，超过 3 个无效请求将被视为通过“探测”密钥空间来违反安全性的尝试，并会触发半永久锁定。

这里唯一的主要成本是适度减少给定 int 大小的可用键空间大小。进出浏览器的 32 位 int 将有 8-10 位专用于安全性，因此留下 22-24 位用于实际密钥。所以你会在不够用的地方使用 64 位整数。

于 2014-02-16T00:08:13.923 回答