一个关于生日的反直觉概率,为什么让 256 位哈希的抗碰撞强度只剩 128 位。
先做个热身题:一个房间里要有多少人,才能让"至少两人同一天生日"的概率超过 50%?大多数人凭直觉会说一两百。正确答案是 23。这个反直觉的事实,直接决定了所有哈希函数的真实安全强度。
为什么是 23 而不是 183?关键在于:我们要找的不是"某个特定的人和你同天生日",而是"任意两人同天生日"。人越多,可配对的组合数暴涨——23 个人能凑出 23×22/2 = 253 对,每一对都有一次"撞上"的机会。概率是这样算的:
随着 n 增加,连乘里每一项都略小于 1,乘起来掉得很快。到 n=23,不相同的概率跌破 50%。
现在把"生日"换成"哈希值"。一个 n 位哈希有 2ⁿ 个可能取值。攻击者想找一对碰撞(两个不同输入、相同哈希),要试多少次?生日悖论给出答案:
这就是那个惊人的结论:找碰撞的成本,只有暴力找原像的平方根。
| 哈希 | 输出位数 n | 抗原像强度 (2ⁿ) | 抗碰撞强度 (2^{n/2}) |
|---|---|---|---|
| MD5 | 128 | 2¹²⁸ | 2⁶⁴(已可实做) |
| SHA-1 | 160 | 2¹⁶⁰ | 2⁸⁰ → 实测 2⁶³ |
| SHA-256 | 256 | 2²⁵⁶ | 2¹²⁸(安全) |
你想要 128 位的抗碰撞安全,就必须选 256 位的哈希。SHA-256 的 "256" 不是冗余——它一半的强度"交税"给了生日攻击。同样的道理贯穿密码学:对称密钥要 256 位才有抗量子的 128 位等效强度(第 26 章)。永远按"最弱的那条攻击路径"来估算真实强度。
2^128 我们搜不动,但生日攻击的威力可以在小尺度上完整重现。下面的 Demo 把 SHA-256 截断到你指定的位数(比如 32 位),然后不断哈希随机字符串,把结果存进一张表,直到撞上一个已经出现过的哈希——那就是一个碰撞。
注意观察"尝试次数":对于 n 位截断哈希,你会发现它通常在 2^(n/2) 附近就撞上了,而不是 2^n。把位数从 24 调到 40,亲眼看着所需次数按平方根规律增长。
"找到两个哈希相同的随机串"听起来像学术游戏,但它能造成真实伤害,尤其配合选择前缀技巧(让碰撞的两份文件各自以攻击者想要的内容开头):
今天你几乎不该在任何安全场景用 MD5 或 SHA-1——包括"给文件算个校验和防篡改"、"给 API 请求签名"、"生成 token"。它们能挡住随手的错误,但挡不住蓄意的攻击者。默认用 SHA-256。
唯一的例外:非安全用途的哈希,比如哈希表分桶、缓存 key、文件去重——这些场景不在乎有人蓄意造碰撞,用 MD5 甚至更快的非加密哈希(如 xxHash)都行。分清"防意外"和"防敌人",是工程判断力的一部分。
抗碰撞是哈希"对内"的软肋。它还有一处"对外"的结构性弱点:当你天真地用哈希去做认证(证明消息来自持有密钥的人)时,SHA-2 的内部构造会反过来咬你一口。这就是下一章——长度扩展攻击,以及正确的解法 HMAC。