Skip to content
Published on

生日悖论与哈希碰撞 — 为什么 23 人中就有一半概率撞车

🇰🇷KO🇺🇸EN🇯🇵JA🇨🇳ZH
필사 모드
分享
Authors

引言 — 从一场派对说起的概率故事

假设一个房间里聚集了 23 个人。这其中有两人生日相同的概率是多少?大多数人会答"365 天里 23 个人……大概 6% 吧?"实际答案是 50.7%。超过了一半。

这个结果太违反直觉了,以至于得到了"生日悖论(birthday paradox)"这个名字。其实与其说是悖论,不如说是我们的直觉在回答一个错误的问题所产生的错觉。而一旦真正理解了这个错觉,一系列看似毫不相关的问题就会被串到一起 — UUID 为什么不会碰撞、哈希需要多少位才安全、哈希表该在什么时候扩容、git 为什么放弃了 SHA-1。

本文从派对上的概率问题出发,追踪这套数学能延伸到多远。如果想亲手生成哈希来找找感觉,不妨把本站的哈希生成器一起打开。

为什么 23 人就有 50%

关键在于我们究竟在数什么。直觉浮现出的问题是:"有没有人和我生日相同?"但真正的问题不是这个,而是:"任意两人的生日是否相同?"

23 人中能选出多少对人?这是组合数。

对数 = C(23, 2) = 23 × 22 / 2 = 253 对

253 对。每一对生日相同的概率是 1/365,而有了 253 对,其中出现一对撞车的空间就比感觉上要大得多。当人数增加时,人数本身是线性增长的(23、24、25……),但对数几乎是平方级增长的(约为 n²/2)。我们的直觉只盯着人数,却漏掉了真正重要的对数。

精确概率通过对立事件来计算 — 先求"没有一对相同"的概率,再用 1 减去它。

P(全不相同) = 365/365 × 364/365 × 363/365 × ... × 343/365
P(至少一对相同) = 1 − P(全不相同)

对 n 个人计算这个值,结果如下。

人数至少一对生日相同的概率
10约 11.7%
20约 41.1%
23约 50.7%
30约 70.6%
50约 97.0%
70约 99.9%

23 人时就已经过半,70 人时几乎可以说是必然。也可以用 Python 直接验证。

def birthday_prob(n, days=365):
    p_all_different = 1.0
    for i in range(n):
        p_all_different *= (days - i) / days
    return 1 - p_all_different

for n in (10, 20, 23, 30, 50, 70):
    print(n, round(birthday_prob(n) * 100, 1))

√N 直觉 — 本文真正的主角

比生日问题的具体数字重要得多的,是藏在它背后的规律。从 N 个可能值中随机抽取,大约抽到 √N 个左右时,碰撞(出现两个相同的值)就开始出现了。

生日问题里 N = 365,√365 ≈ 19.1。实际超过 50% 的那个点 — 23 人 — 正好就在这个 √N 附近。这不是巧合。

粗略地看为什么是 √N:抽取 n 个,大约会产生 n²/2 对,每对碰撞的概率是 1/N。碰撞对数的期望值约为 n²/(2N),而这个值大致等于 1 的那一点 — 也就是"现在该出现一次碰撞了"的那一点 — 正是 n ≈ √N。以 50% 概率为基准写得更精确一些,就是:

达到 50% 碰撞所需样本数 n ≈ 1.1774 × √N

这一个近似统摄了本文剩下的全部内容。要记住的只有一件事:碰撞始于 √N,而不是 N。 不能因为空间大就掉以轻心,要看的是它的平方根是多少。

转向 UUID 与哈希

现在离开派对,走进计算机的世界。软件里我们总是在制造"必须唯一的标识符":UUID、哈希值、令牌。这些本质上都等同于从一个非常大的箱子里随机抽取一个值。所以生日问题的数学原封不动地适用。

UUID version 4 携带 122 位随机比特(128 位中有几位用于版本号和变体标记)。可能值的数量 N 是 2¹²²,约等于 5.3 × 10³⁶。要让碰撞在这么大的空间里成为现实的担忧,需要生成约 √N 个,也就是约 2.3 × 10¹⁸ 个 UUID。

来感受一下这个数字有多大。即便每秒不停地生成十亿个(10⁹)UUID,要达到 50% 的碰撞概率也需要数百年。这就是为什么实践中我们可以放心地把 UUIDv4 当作"不会碰撞"来用。严格来说碰撞是可能的,只是概率小到可以忽略。

这里正体现出 √N 直觉的威力。122 位空间的安全性不是 122 位,而是其一半 —— 约 61 位。衡量抗碰撞性时,永远要把比特数对半折算。

估算哈希碰撞概率

密码学哈希函数也是同样的故事。哈希函数把任意长度的输入映射为固定长度的输出。若输出是 b 位,可能的哈希值就有 2ᵇ 个。不同输入产生相同哈希值,就是碰撞。

把生日近似直接套用过来,大约哈希了 2^(b/2) 个不同输入之后,碰撞概率就会变得可观。归纳如下。

哈希输出位数全空间 N开始担心碰撞的点(约 √N)
32 位2³² ≈ 43 亿约 2¹⁶ = 65,536 个
64 位2⁶⁴约 2³² ≈ 43 亿个
128 位2¹²⁸约 2⁶⁴ 个
256 位2²⁵⁶约 2¹²⁸ 个

32 位哈希仅在约 6.5 万个值左右,碰撞概率就达到了一半。43 亿这个空间大小之所以会误导人,原因就在这里 — 真正的安全余量是它的平方根,仅有 6.5 万。

还有一个便于估算极小碰撞概率的公式。当 N 很大、样本数 n 远小于 √N 时,碰撞概率大致为:

P(碰撞) ≈ n² / (2N)

举例来说,往一个 128 位哈希(N = 2¹²⁸)里塞入十亿个值(n = 10⁹ ≈ 2³⁰),碰撞概率约为 (2³⁰)² / (2 × 2¹²⁸) = 2⁶⁰ / 2¹²⁹ = 2⁻⁶⁹。实际上等于零。

为什么 128 位就够用

现在可以回答"为什么是 128 位"了。128 位哈希或标识符的抗碰撞性处于 √N 的量级,也就是 2⁶⁴ 次尝试。2⁶⁴ 约为 1.8 × 10¹⁹。

看看这个规模在物理上意味着什么。即便动用地球上最快的超级计算机集群,以每秒数万亿次(约 2⁴⁰)的速度计算哈希,要达到 2⁶⁴ 次也需要数十万年。偶然撞上一次随机碰撞的概率实际上为零。

这里需要区分两种"抗性"。

  • 抗碰撞性(collision resistance):攻击者寻找任意两个哈希值相同的输入。生日攻击在这里适用,难度是 2^(b/2)。128 位时就是 2⁶⁴。
  • 抗原像性(preimage resistance):为给定的特定哈希值找到对应的输入。这里生日技巧不适用,难度是 2ᵇ。128 位时就是 2¹²⁸。

也就是说,同样是 128 位,"攻破特定的一个值"要难得多,是 2¹²⁸;而"找到任意一次碰撞"相对容易,是 2⁶⁴。这就是为什么在需要强抗碰撞性的场合,128 位被认为不够,要用 256 位。SHA-256 采用 256 位,正是为了确保这份余量(2¹²⁸ 的抗碰撞性)。

哈希表 — 反过来利用碰撞的地方

到目前为止,碰撞一直是件坏事。但在哈希表里,碰撞是无法避免的日常,设计上甚至是以碰撞为前提的。这是因为这里的哈希空间是故意设小的。

哈希表先对键做哈希,再对桶数 m 取余数作为索引。

index = hash(key) % num_buckets

桶只有 m 个,N = m 就非常小。按照生日问题的规律,只需插入约 √m 个键,碰撞就会开始出现。桶有 100 个的话,仅仅十几个键就已经常见碰撞了。所以哈希表并不试图消除碰撞,而是专注于在碰撞发生时优雅地处理它。典型做法有把同一桶挂成链表的链接法(chaining),以及寻找下一个空位的开放寻址法(open addressing)。

负载因子与扩容

支配哈希表性能的值是负载因子(load factor)。

负载因子 α = 已存储项数 n / 桶数 m

负载因子低时碰撞稀少,查找平均接近 O(1)。但负载因子升高后,每个桶里堆积的项越来越多,碰撞变得频繁,查找也因为要遍历这些链条而变慢。因此大多数哈希表实现在负载因子越过某个阈值后,会增加桶数并重新安置所有项。这就是扩容(resizing),也叫重新哈希(rehashing)。

  • Java 的 HashMap 默认负载因子阈值是 0.75。项数超过桶数的 75% 时,桶数翻倍。
  • Python 的 dict 在超过约 2/3(约 0.66)时开始扩容。
  • Go 的 map 也在类似的阈值下增长。

扩容需要把所有项重新插入新桶,代价是 O(n)。看起来很贵,但得益于成倍扩容的策略(均摊翻倍,amortized doubling),添加单个项的平均成本依然保持 O(1)。这与队列或动态数组扩容时成倍增长是同一个原理 — 偶尔一次操作代价很大,但把这份代价摊到中间那些廉价操作上,平均下来就是常数时间。

这里有一个有趣的对比。在密码学中,碰撞始于 √N 是一种威胁,于是我们把空间做得很大来避开它。在哈希表中,我们接受同样的 √N 现象,把空间保持得很小,转而通过碰撞处理和扩容来管理性能。同一套数学,截然相反的策略。

碰撞真正要命的时刻 — git 从 SHA-1 转向 SHA-256

碰撞概率从理论变成真实事件的代表性案例,是 git。

git 用内容的哈希来标识每一个对象(提交、树、blob)。很长一段时间里这个哈希是 SHA-1,输出 160 位。按生日规律,SHA-1 的抗碰撞性是 2^(160/2) = 2⁸⁰ 次尝试。多年以来,这个量级一直被认为足够安全。

问题出在两方面。第一,2⁸⁰ 并非无穷大,随着算力的发展,它逐渐进入了可触及的范围。第二,更决定性的是,SHA-1 并非纯粹的随机函数。由于内部结构存在弱点,人们发现了一种方法,能以远低于暴力穷举所需的 2⁸⁰ 的成本制造出碰撞。

2017 年,谷歌与 CWI 真的做到了让两份不同的 PDF 文件拥有相同的 SHA-1 哈希。这次名为"SHAttered"的攻击以约 2⁶³ 量级的计算量制造出了碰撞,远低于理论安全线 2⁸⁰。这对作为内容寻址存储的 git 来说是直接威胁 — 如果两个被恶意构造的对象拥有相同的哈希,就存在把其中一个悄悄替换成另一个的空间。

于是 git 从两个方向做出了应对。

  • 短期防御:引入了能检测 SHAttered 类型碰撞的强化版 SHA-1(带有 collision detection 的变体),用来过滤已知的攻击模式。
  • 根本解法:推进将哈希函数本身迁移到 SHA-256。SHA-256 输出 256 位,抗碰撞性跃升到 2¹²⁸,使得在可预见的未来,不仅是随机碰撞,连结构性攻击也实际上变得不可能。

git 的教训很明确。"现在够用的位数"不会永远够用。当算力的进步与哈希函数自身弱点的发现叠加在一起时,昨天的安全线就会变成今天的漏洞。这正是为什么安全系统总是要预留充裕的余量(比如 SHA-256 的 2¹²⁸)来设计。

小结 — 一套数学,多副面孔

生日悖论看起来像是派对上的趣味把戏,但实际上是贯穿整个计算领域的根本原理。

  • 核心规律:在 N 个空间中,碰撞始于 √N,而不是 N。
  • UUID·哈希:因此 b 位的抗碰撞性实质上只有 b/2 位。128 位之所以安全,是因为 2⁶⁴ 这堵墙在物理上难以逾越。
  • 哈希表:同样的 √N 现象使得碰撞不可避免,所以要管理负载因子,在阈值处成倍扩容。
  • git:当 SHA-1 的 2⁸⁰ 抗性被 SHAttered 攻破后,转向了 SHA-256 的 2¹²⁸。昨天的够用,可能变成明天的不够用。

这一切都源自一个简单的观察:对数是以人数的平方增长的。下次生成 UUID 或选择哈希大小时,不妨想的不是空间的大小,而是它的平方根。真正的安全余量,永远在那里。

如果想亲自生成多种哈希算法的输出并比较其大小,欢迎到哈希生成器里试一试。

参考资料

Discuss on Twitter • View on GitHub