哈希碰撞详解:生日悖论、真实实验与为什么 MD5 必须淘汰

两个不同的输入算出同一个摘要,就是哈希碰撞。工程上只关心三件事:它是否必然存在、多久会出现、能不能被人为构造。答案分别是鸽笼原理、生日悖论、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(任何机器、任何时间都相同)

工程结论:四条边界

  • 碰撞必然存在(鸽笼),但出现时间可算(生日界 2^(b/2))——所以概率是可以管理的,不是玄学。
  • MD5 / SHA-1 出局于一切对抗场景,包括文件签名、证书、防篡改标识;非对抗的去重与缓存键仍可用,但没有理由不用 SHA-256。
  • 校验的信任来自渠道:算法只是必要条件,摘要必须取自独立可信源,流程见文件完整性校验。
  • 密码存储防的是枚举,不是碰撞:盐 + 慢哈希,参数与迁移见密码哈希指南。
  • 截断指纹的位数按条数与概率反推,不要凭感觉取 8 位、16 位。

速查与选型:哈希算法参考、文本哈希工具。

常见问题

哈希碰撞会让我的下载文件校验失效吗?

现实中不会。SHA-256 有 2²⁵⁶ 种输出,随机两个文件碰撞的概率约 1/2²⁵⁶——比连续中彩票还低几个数量级。需要担心的不是「偶然撞上」,而是攻击者刻意构造:MD5 的碰撞已经可以按需生成,所以校验下载文件必须用 SHA-256 起步,且哈希必须来自官方渠道(官网/HTTPS 页面),而不是下载链接旁边的同一来源。

SHA-256 会像 MD5 一样被破解吗?

目前没有。MD5 的碰撞攻击在 2004 年被证明可实际构造,SHA-1 在 2017 年被 Google 与 CWI 实现了真实碰撞(SHAttered,约 2⁶³ 次运算),两者都属「构造性破解」。SHA-256 至今没有已知的实际碰撞,输出空间 2²⁵⁶ 也让暴力路径不可行。密码学的历史规律是「算法终会退役」,所以工程上的正确姿势是跟随标准演进(如今更推荐 SHA-3/BLAKE3 用于新系统),而不是赌某个算法永远安全。

两个文件的哈希相同,它们就一定相同吗?

在哈希未被破解的前提下,实践上可以认定相同——但逻辑上这是「高度可能」而非「必然」:哈希把无限输入映射到有限输出,碰撞在数学上一定存在。工程上的含义是:用未被破解的哈希(SHA-256)做校验时,可以放心把「哈希相同」当作「文件相同」;用 MD5 时则不能——攻击者可以构造两个 MD5 相同但内容不同的文件。

为什么两段完全不同的文字,哈希只差几个字符?

因为哈希输出是均匀分布的固定长度摘要:改变输入的一个字母,输出的是「重新随机洗牌」而非「局部修改」。所以两个相近输入的哈希在视觉上毫无关联——这不是缺陷,恰恰是雪崩效应,它让攻击者无法通过观察输出猜测输入的变化方向。

← 返回博客首页