math - 与截断的 SHA-256 哈希发生冲突的概率

Question

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

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

Answer 1

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

“8 个字符”是指:

A) 您存储了哈希的 8 个十六进制字符？那将存储 32 位。

B) 您存储了 8 个 BASE-64 字符？那将存储 48 位。

C) 您存储了 8 个字节，以某种单字节字符集/编码或以某种损坏的方式破解为字符编码？这将存储 56-64 位，但如果您没有正确编码，您将遇到字符转换问题。

D)您将 8 个字节存储为字节？这真正存储了 64 位的哈希值。

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

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

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

由于以上对您的设计的最保守的理解(将其读作 A，8 个十六进制字符 == 32 位)，如果您的方案以 ~64,000 行的规模存储，则预计会发生冲突。我认为这样的结果对于所有严肃的甚至是玩具的系统都是 Not Acceptable 。

交易表可能有数量，允许业务增长，从 1000 - 100,000 交易/天(或更多)。系统应设计为运行 100 年(36500 天)，并内置 10 倍的增长因子，因此..

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

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

一种可能的更好的设计可能是，而不是完全散列和伪随机化 key 并希望(反对希望)避免冲突，而是将 8-10 位散列的 8-10 位添加到 key 中。

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

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