这次讨论起于下面这张梗图:有人愿意出 4000 元,寻找修改 PDF 却保持七种哈希或校验值全部不变的方法,或者找出七项结果都相同的不同文件。

看到这张图后,我更好奇的是一个数学问题:先不考虑怎么找到样本,能否严格证明,存在两个不同输入,能让这七项结果同时相同?于是我和 GPT 从这个问题出发,一步步讨论了输出组合的计数、鸽巢原理,以及“存在”和“找得到”之间的区别。
下面整理的是这次讨论的证明与边界。原图混合了“修改指定文件”和“自由寻找两个文件”两种要求;我们先证明后者在原始字节串上的存在性,再回头看它为什么没有直接解决原图中的 PDF 修改需求。
先把需求写成准确的命题
这里的七项是 MD5、CRC32、SHA-1、SHA-256、SHA-512、SHA3-256 和 SHA3-512。其中 CRC32 是校验码,不是密码学哈希。以下固定各算法的版本、参数和计算规则,全部对同一份完整字节串计算。
把它们记作 H₁ 到 H₇。我们要找的是同一对不同输入 A、B,满足:
这不是找七对文件,每对只满足一项;也不是要求 MD5(A) 等于 SHA-256(A)。比较始终发生在同一个算法、两个不同输入之间。
定义一个七元组,把每个输入的全部结果完整记录下来:
于是 F(A) = F(B) 当且仅当七个等式全部成立。把结果写成元组,或按固定长度拼接二进制摘要,只是记法变化,并没有减少条件,也没有赋予我们单独操控各项结果的能力。
我的理解:只看输入与输出,就已经够了
我觉得更简单直接的理解是:要证明七种哈希同时碰撞的情况存在,不必先研究算法之间会不会“互相冲突”。那样容易把存在性问题变成如何逐项构造碰撞的问题,反而复杂化了。直接从输入和最终输出出发:只要不同输入的数量大于输出组合的数量,根据抽屉原理(也叫鸽巢原理),就一定有不同输入得到完全相同的七项结果。
于是,关键就变成了:七项结果一共能表示多少种组合?这里有一个很有用的观察:七个固定长度输出的有序组合,与把这七段 bit 串按固定顺序拼接起来,是完全等价的表示。因为每段长度已知,拼接后仍能按固定边界拆回原来的七项,没有丢失任何信息。因此,拼接结果相同,当且仅当七项结果分别相同。
这里的 ‖ 表示拼接。七段加起来是 1856 位,因此这种表示一共能容纳 21856 种组合。实际算法未必能产生其中每一种,但我们只需要这个上界:输出最多有这么多种,就已经足够证明碰撞存在。
如果把输入抽象为任意长度的有限字节串,输入的可能性是无限的,而固定长度输出的可能性有限,碰撞自然不可避免。具体哈希标准可能限制消息长度,不过这个思路甚至不需要用到无限:只看全部恰好 233 字节的输入,就有 21864 种,已经超过输出的容量 21856。
更一般地,对算法共同支持的任意固定长度 L,只要 L ≥ 233 字节,全部该长度的原始字节串中就必然存在共同碰撞。这说的是整个候选集合中一定有碰撞,并不表示每个达到这个长度的文件都有碰撞对象,也不表示 233 字节是实际碰撞的最短长度。
对我来说,这个证明最关键的转变就是:不用追踪算法内部怎样计算,只要看清输入有多少种、最终输出最多能容纳多少种,结论就出来了。
不需要无限输入,233 字节就够了
七项输出的长度分别为 128、32、160、256、512、256、512 位,总和是:
位数依据来自 MD5 规范、CRC32 的规范示例、FIPS 180-4 和 FIPS 202。这里数的是二进制位,不是十六进制显示的字符数。
所以 F 的输出组合最多只有 21856 种。这里不要求七种函数独立,也不要求每种组合都能出现;相关性或不可达的组合只会让实际输出种类更少。
再令 S 为所有恰好 233 字节的输入。每字节有 256 种取值,因此:
鸽巢原理:把 M 个对象放进至多 K 个盒子,至少有一个盒子装着不少于 ⌈M/K⌉ 个对象。否则,每个盒子的数量都小于 M/K,加起来就不足 M,与总数矛盾。
按 F(x) 的值把 S 分组,每组就是一个“盒子”。至少有一组的大小不小于:
这一组中的输入彼此不同,但 F 值全部相同。任取其中两个,就是同时满足七项相等的共同碰撞。证毕。
为什么恰好选 233?
1856 位等于 232 字节。若固定输入长度为 L 字节,要让上述计数直接保证碰撞,只需 8L > 1856,即 L > 232,最小整数是 233。
这是这套固定长度计数证明的充分门槛,不是实际碰撞的最短长度。对 232 字节或更短的输入,上述数量上界不足以保证碰撞,但也不能排除碰撞。证明使用有限、很短的输入,还避开了具体哈希标准对最大消息长度的限制。
“改第二项,会不会破坏第一项?”
这是讨论中最容易卡住的地方:为满足另一项而修改文件,确实可能破坏已经满足的条件。但存在性证明根本没有修改文件。它是在一批不变的候选中,反复选取子集。
令 S₀ = S。第 i 步只在 Sᵢ₋₁ 内按 Hᵢ 分组,取最大的组 Sᵢ。若该算法输出 nᵢ 位,那么最多分出 2nᵢ 组,故:
| 本步新增条件 | 输出位数 | 保留输入至少为 |
|---|---|---|
| 起始集合 | — | 21864 |
| MD5 | 128 | 21736 |
| CRC32 | 32 | 21704 |
| SHA-1 | 160 | 21544 |
| SHA-256 | 256 | 21288 |
| SHA-512 | 512 | 2776 |
| SHA3-256 | 256 | 2520 |
| SHA3-512 | 512 | 28 = 256 |
因为 S₇ ⊆ S₆ ⊆ … ⊆ S₁,最后留下的每个输入都在此前选出的各组里,因而继承所有相等条件。最后仍至少剩下 256 个输入。这个证明与元组计数是同一件事的两种表达。
乘起来的是分组数量的上界,不是独立事件的概率。整个论证没有随机性或独立性假设;它也不意味着实际枚举这些集合是可行的。
存在性证明,不是搜索难度证明
“在有限时间内不可能找到”并不准确。这里的候选集合是有限的,每次哈希计算也会结束。理论上,依次枚举不同的 233 字节输入并记录七元组,至多计算 21856 + 1 个候选就必然发现重复。这是有限但极其庞大的穷举上界,不是必要计算次数的下界。
2928 从哪里来?
若额外假设 F 像一个均匀随机的 1856 位函数,不同输入的结果独立,那么在 q 个不同候选中,碰撞对数的期望为 q(q − 1) / (2 × 21856)。达到常数级碰撞概率所需的候选数因而约为:
这是理想随机函数模型下的生日估算,不能当作这七个真实算法组合的实际安全强度,更不能声称所有算法都必须执行这么多次计算。
一个简单反例:把同一个 SHA-256 摘要重复七遍,记录长度变成 1792 位,但一次 SHA-256 碰撞就让七段全部相等。输出更长,不自动意味着安全性同比增加。
即便采用不同函数,也要研究结构。Joux 的多重碰撞研究说明,对某些迭代式哈希的拼接,结构性攻击可以优于把总输出当随机函数的朴素估算。它不是这七项组合已有实用攻击的证明,而是提醒我们不能直接相加安全强度。
一个更稳妥的难度关系
任何能高效找出共同碰撞的方法,也就能高效给出 SHA-256 的碰撞;对其他分量同样如此。因此,只要其中一个分量仍具备抗碰撞性,共同碰撞就不能被高效找到。这是条件性的归约关系,不是对真实哈希的无条件时间下界证明。
NIST 对抗碰撞性的定义强调的正是找到不同输入、相同输出在计算上不可行,而非碰撞不存在。本文的现实难度判断依赖这种密码学假设;计数证明本身不能证明“几乎不可能找到”。
原图的 PDF 要求,比这个命题更强
自由选择 A、B,寻找任意共同碰撞,是一个存在量词命题。给定文件 A,再找 B ≠ A 且 F(B) = F(A),则是第二原像问题。鸽巢原理保证某个输出组里挤着多个输入,却不保证每个输出组都有多个输入。
例如,把四个输入映射到三个结果,完全可以出现分组大小 2、1、1。碰撞已经存在,但落在单元素组里的输入没有第二原像。这说明,单凭计数,不能推出某个指定文件一定有对应样本。
“合法 PDF”“显示特定内容”“只准修改某些位置”又增加了输入约束。全部 233 字节串并不都是合法 PDF,更不能保证碰撞的一组分别呈现想要的内容。要讨论受限集合,必须重新证明它的大小及性质;不能把任意字节串的结论直接移植过去。
说人话:柜子总会装重,但你未必找得到
把每个文件想成一张不同的卡片。七种算法就像七台机器,每台读完卡片后,都按自己的固定规则给它打一个编号。我们把七个编号完整写在一张标签上:只有七项分别都相同,两张标签才算相同。
再想象一个大仓库:每一种可能的标签对应一个柜子,卡片必须放进标签对应的柜子。虽然柜子多得难以想象,但编号的长度固定,所以柜子的数量有上限。
这时只要卡片比柜子多,就一定有柜子装了不止一张卡片。就像把 11 张卡片放进 10 个柜子,不管怎么放,都不可能每个柜子最多只有一张。同一个柜子里的两张不同卡片,就是七项同时碰撞的两个文件。前面的计算还告诉我们:把全部 233 字节的可能输入都算上,卡片数至少是柜子数上限的 256 倍,所以至少有一个柜子能装下 256 张不同卡片。

你可能会担心:“为了让第二个编号一样,改了卡片,不就把第一个编号弄变了吗?”但这里根本没有改卡片,只是在给已经存在的卡片分类。我们证明的是一定有卡片会被分到同一个柜子,并没有找到一种能随意修改编号的方法。
知道柜子里一定有重复,和找出哪两张卡片重复,是两件事。我们只看数量,就能断定重复存在,却没有因此拿到那两张卡片。如果没有捷径,逐张计算和比较的工作量可能大到现实中根本做不完。不过,这个比喻和计数证明都不能排除捷径;“很难找到”还需要对算法安全性的判断。它也不是说永远找不到:理论上,把有限的候选查到足够多,就一定能找到。
最后,仓库里某个柜子装了多张卡片,不代表你手里这张卡片所在的柜子也有第二张。更不能保证第二张恰好是一份能正常打开、内容又符合要求的 PDF。
所以,数学能保证“某处一定有”,却没有替我们回答“具体在哪儿”“怎样找到”,更没有保证“你指定的这份文件就能改”。这正是那张梗图背后最有意思的区别。
参考资料
整理与核验日期:2026 年 9 月 20 日。本文的有限集合证明在正文中完整给出;算法位数、术语与结构性攻击的背景参考以下一手资料。
- RFC 1321:MD5。本文仅引用输出长度,不沿用旧文中的安全性猜测。
- RFC 1952:GZIP 中使用的 CRC32。CRC 变体需固定,32 位计数不依赖具体变体。
- FIPS 180-4:SHA-1 与 SHA-2。
- FIPS 202:SHA-3。
- NIST:哈希函数与抗碰撞、原像及第二原像性质。
- Antoine Joux,Multicollisions in Iterated Hash Functions,CRYPTO 2004。