两个不同的输入算出同一个摘要,就是哈希碰撞。工程上只关心三件事:它是否必然存在、多久会出现、能不能被人为构造。答案分别是鸽笼原理、生日悖论、MD5/SHA-1 的现状——三者共同决定校验与密码存储该怎么选算法。
碰撞必然存在:鸽笼原理
哈希把任意长度的输入压缩成固定长度的输出:SHA-256 永远输出 256 位,可能的输出只有 2²⁵⁶ 种,而输入是无限的。无限映射到有限,必然有多个输入共享同一个输出——这一步不需要任何高深数学。
「存在」不等于「随机能撞到」。2²⁵⁶ 的输出空间大到随机碰撞几乎不会发生,所以现实中的碰撞风险不是「运气差」,而是「有人刻意构造」。这需要在下一页的计算里说清楚。
生日悖论:把「不可能」变成「算得清」
「多少个随机输入之后,碰撞概率过半?」直觉是「试一半输出空间」,实际答案小得多:23 个人里有两人生日相同的概率已超过 50%(一年 365 天)。对 b 位哈希,这个数量约为 2^(b/2),不是 2^b。
import math
def collision_prob(bits, n):
N = 2 ** bits
return 1 - math.exp(-n * (n - 1) / (2 * N))
# 32 位截断(比如只取 SHA-256 摘要的前 8 个十六进制字符)
for n in (10_000, 50_000, 77_000, 100_000):
print(n, f'{collision_prob(32, n)*100:.1f}%')
# 10000 → 1.2% 50000 → 25.3% 77000 → 49.9% 100000 → 68.8%
77000 个随机输入就让 32 位哈希的碰撞概率过半,正好落在 2^(32/2) = 65536 附近。注意概率的增长方式:从 1 万到 7.7 万,只多了不到 7 倍输入,概率却从 1.2% 涨到 49.9%——它随 n²/N 增长,不是线性。所以「我只存了几万条指纹,应该不会撞」在 32 位下是个错误直觉。
64 位要到约 5×10⁹ 才过半;MD5 的 128 位按同一公式只需约 2⁶⁴ 次运算,这个量级已经到了专用硬件的射程内——这正是 SHA-1 被实际攻破的路径。
亲手造一次碰撞,比看概率表更有说服力
把 SHA-256 截断到前 2 个十六进制字符(8 bit,只有 256 种输出),暴力枚举几秒就能撞:
import hashlib
seen = {}
for i in range(1_000_000):
s = f'oltool-{i}'
h = hashlib.sha256(s.encode()).hexdigest()[:2]
if h in seen:
print(f'碰撞: {seen[h]!r} 与 {s!r} 前 2 位都是 {h!r}(第 {i} 次尝试)')
break
seen[h] = s
# 碰撞: 'oltool-21' 与 'oltool-24' 前 2 位都是 '7b'(第 24 次尝试)
两个「碰撞」的完整哈希是 7b3f71f6… 与 7bf43201…:前 2 位相同,整体毫不相干。这说明截断牺牲的是碰撞抗性,不是单向性——找不回原文,但很容易造出一个「看起来一样」的指纹。
工程含义很直接:给定条数 m 与可接受概率 p,用上面的 collision_prob 扫不同的 bits,直到 p 落在阈值以下,而不是「取 8 位看着够长」。指纹越短,撞车来得越快,而且比直觉快得多。
MD5 与 SHA-1:碰撞可以「下单」
MD5 的现状不是理论:从 2004 年起,选择前缀碰撞逐步工程化,攻击者能构造两个内容不同、MD5 相同的文件——真实世界的伪造证书(2008 年 rogue CA)与 Flash 文件伪装都源于此。SHA-1 在 2017 年被 SHAttered 攻击实现真实碰撞(约 2⁶³ 次运算、约 11 万美元 GPU 时),PDF 伪造 PoC 随后公开。
威胁模型因此改变:你不需要担心「恰好撞上」,需要担心「有人故意造一对」。攻击者准备两份预算表——一份给你看、一份给你签——只要签字系统用 MD5/SHA-1,两份文件的哈希就一样,事后无法证明你签的是哪一份。
SHA-256 用输出长度与内部结构堵住这条路:256 位对应生日界约 2¹²⁸,远超可行算力;且构造碰撞需要打破压缩结构本身,目前没有已知方法。
两类场景,两种威胁模型
| 场景 | 碰撞的影响 | 要求 |
|---|---|---|
| 文件完整性校验 | 攻击者可构造「恶意文件 + 你要的哈希」成对出现 | 用未被破解的算法(SHA-256 起);哈希来自独立可信渠道 |
| 密码存储 | 攻击者不需要碰撞——直接枚举更便宜 | 与碰撞无关:需要盐 + 慢哈希(bcrypt/argon2) |
第二行经常被混为一谈。在密码存储的威胁模型里,「构造两个同哈希的密码」没有意义——攻击者直接试常见密码更快。所以「MD5 碰撞已破」不是「MD5 存密码不安全」的主要原因;真正原因是它太快。
另一个常被问到的问题:哈希相同,文件就一定相同吗?在算法未被攻破时,工程上可以当作等价,逻辑上只是「极大概率」。这是校验能成立的全部根基——确定性 + 足够大的输出空间:
import hashlib
hashlib.sha256(b'hello world').hexdigest()
# → b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9(任何机器、任何时间都相同)