CRC32碰撞并非偶然：从仿射映射原理到工程防护

简介：围绕CRC32校验与碰撞问题整理的一份微型项目资源，面向需要理解循环冗余校验原理、从事数据完整性检测或研究短文件名下CRC碰撞现象的开发者与学习者。资源聚焦“如何计算CRC32”“不同数据为何可能产生相同校验值”以及“6位字符以内加密压缩包场景中的碰撞可能性”，以代码加文档的形式降低上手门槛。压缩包共6个文件，以3个Python脚本为主体，涉及CRC32计算、测试数据与碰撞测试，另含1份说明文档、1份项目说明和1份CI配置，整体仅24KB，结构紧凑，适合快速阅读与运行调试。目前已有727人浏览学习，内容虽然精简，但脚本与数据文件相互配合，可直接观察CRC32的具体输出，并通过修改测试数据进一步验证碰撞概率与边界条件。对希望结合实例掌握CRC32算法、排查压缩包校验异常或开展碰撞测试的读者而言，是一份轻量实用的参考实现。

1. CRC32 碰撞：不是偶然，是数学上必然

下载一个 4GB 的安装包，CRC32 校验通过，解压后程序却崩溃——这种事不常见但绝对存在。CRC32 所在的生态位是“完整性校验”，不是“安全校验”：它输出的 32 位余数只是 GF(2) 域上多项式除法的余数，既不抗随机碰撞，更挡不住蓄意构造。生日悖论下，约 7.7 万条数据就有 50% 的概率出现一对碰撞；而在攻击者手里，利用 CRC 的仿射结构，构造两个内容不同但 CRC32 相同的数据，开销可以低到几十次矩阵运算。下面把 CRC32 碰撞拆开讲：碰撞从哪儿来、怎么构造出来、线上哪些系统会被波及，以及不换哈希的前提下还能做什么补救。

2. CRC32 的结构：从多项式除法到 GF(2) 仿射映射

2.1 CRC32 的数学骨架：32 位余数的多项式除法

把一段数据看成 GF(2) 上的大多项式，CRC32 就是它除以生成多项式后的余数。标准 CRC-32/IEEE 802.3 的生成多项式是：

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

十六进制记法是 0x04C11DB7。实际工程里几乎没人直接做多项式除法，表驱动或位循环用的是 0xEDB88320，这是对 0x04C11DB7 做位反射后的结果，配合 refin/refout=true 的参数搭配。二者算出的 CRC32 值一致，只是内部位序不同。

最小实现甚至不用查表，用位循环即可复现上面参数：

def crc32_reflected(data: bytes, poly=0xEDB88320, init=0xFFFFFFFF, xorout=0xFFFFFFFF) -> int: crc = init for byte in data: crc ^= byte # 反射模式下字节先与低8位异或 for _ in range(8): # 每比特反馈一次 crc = (crc >> 1) ^ poly if crc & 1 else crc >> 1 return crc ^ xorout

这段代码里poly必须是反射多项式 0xEDB88320；每次迭代取寄存器最低位作为反馈位，等价于原始多项式逐位除法的镜像过程。init和xorout都是 0xFFFFFFFF，目的是让全零输入也有非零输出，避免“空数据校验值恒为 0”的退化。把它和zlib.crc32(b"abc")对拍，结果一致，就说明参数没配错。

2.2 为什么 CRC32 是“线性”的：碰撞的根源

观察上面的循环：每次操作只有异或、右移和按位常数选择，没有进位。异或在 GF(2) 上是加法，右移、异或反馈都是线性算符，于是整个 CRC 映射天然满足“异或分配律”。严格地说，因为有 init 和 xorout，CRC 是一个仿射映射：

C(x) = L(x) xor c0

其中 L 是 GF(2) 上的线性变换，c0 是由 init 和 xorout 决定的常量。对于任意两条等长消息 m 和 d：

C(m xor d) = C(m) xor L(d)

如果 d 是非零向量且落在 L 的核（kernel）里，即 L(d)=0，那么 m 与 m xor d 就有完全相同的 CRC32。这就是碰撞的构造入口。仿射性把“找碰撞”这个通常需要暴力搜索的问题，转化成了“解一个 GF(2) 线性方程组”的问题。

同理，消息越长，输入维度越高，而输出只有 32 维，核必然非空。所以 CRC32 的碰撞不是小概率事件，而是结构性的必然。任何一个消息长度超过 4 字节的 CRC 映射，都存在可构造的非零碰撞差。

2.3 自然碰撞与蓄意构造：概率和能力的差距

被动场景下，随机数据产生 CRC32 碰撞遵循生日界限：对于 32 位输出，碰撞概率达到 50% 所需的样本量约 sqrt(2^33 * ln 2) ≈ 77163 条。如果数据量只有几千条，概率很低，这也是大多数网络传输校验敢用 CRC32 的原因。

但蓄意场景完全不同。线性方程组在 32 维空间求解，代价是大约 32^3 次布尔运算，对现代 CPU 连 1 毫秒都用不上。也就是说，只要内容可以被人为调整，碰撞就不再是“遇到”的问题，而是“想造就有”的问题。理解这一点，才能解释后续章节里那些看似诡异的工具和攻击。

这一章建立了两个核心认知：CRC32 是 GF(2) 上的仿射映射；碰撞源于线性算子 L 的核。接下来就把这两个认知落到代码里。

3. 构造 CRC32 碰撞：从 Z3 到线性方程组

3.1 跑通第一对碰撞：用 Z3 约束求解

如果只是想要一对“能用”的碰撞，最直接的方法是用 SMT 求解器 Z3，把 CRC32 的位循环原样写成 BitVec 约束，再让求解器找两个不同消息。8 字节消息的自由度是 64 位，CRC 相等只有 32 个约束，解空间存在。

from z3 import * POLY = BitVecVal(0xEDB88320, 32) ZERO = BitVecVal(0, 32) def crc32_z3(buf): crc = BitVecVal(0xFFFFFFFF, 32) for b in buf: crc = crc ^ ZeroExt(24, b) for _ in range(8): crc = LShR(crc, 1) ^ If(crc & 1 == 1, POLY, ZERO) return crc ^ BitVecVal(0xFFFFFFFF, 32) s = Solver() m1 = [BitVec(f"m1_{i}", 8) for i in range(8)] m2 = [BitVec(f"m2_{i}", 8) for i in range(8)] # 前4字节固定为 ABCD，便于肉眼对照 for i in range(4): s.add(m1[i] == BitVecVal(ord("ABCD"[i]), 8)) s.add(m2[i] == BitVecVal(ord("ABCD"[i]), 8)) # 后4字节至少有一位不同 s.add(Or([m1[i] != m2[i] for i in range(4, 8)])) s.add(crc32_z3(m1) == crc32_z3(m2)) if s.check() == sat: model = s.model() a = bytes([model.eval(x).as_long() for x in m1]) b = bytes([model.eval(x).as_long() for x in m2]) import zlib print("m1:", a.hex(), hex(zlib.crc32(a))) print("m2:", b.hex(), hex(zlib.crc32(b))) else: print("unsat")

代码里的LShR是逻辑右移，Z3 中必须用它而不是>>，后者对 BitVec 是算术右移。ZeroExt(24, b)把 8 位字节扩展到 32 位寄存器宽度。跑出来的两个 8 字节消息前四字节相同，后四字节不同，但zlib.crc32的结果完全一致。

Z3 适合教学和一次性任务，它的缺点是代码被塞进 SMT 编码后很难扩展到更长消息，而且求解时间不稳定。实际生产里构造碰撞，更常用的是下一节的线性代数方法。

3.2 可控尾块：让任意文件 CRC 等于目标值

比“找到两个碰撞”更实用的是可控尾部注入：给定任意前缀 P，找到 4 字节 tail，使得CRC32(P || tail) == target，其中 target 可以随便指定。这等价于 CRC 函数关于 tail 的可逆性问题，而依然是仿射性给的底气。

处理完前缀后，CRC 寄存器停在状态 state。接下来处理 4 字节 tail 时，可以用一个函数 f(tail32) 描述从 tail 到最终 CRC 的映射。因为整条链路是仿射的：

f(tail) = M · tail xor b

其中 M 是 32×32 的 GF(2) 矩阵。构造 M 不需要解析多项式：取零输入求 b，再对每个 bit i 置 1 求 f(1<<i)，异或掉 b，就得到 M 的第 i 列。之后解 M · tail = target xor b 即可。

import struct def _step(crc: int, byte: int) -> int: crc ^= byte for _ in range(8): crc = (crc >> 1) ^ (0xEDB88320 if crc & 1 else 0) return crc def digest(prefix: bytes) -> int: crc = 0xFFFFFFFF for b in prefix: crc = _step(crc, b) return crc def crc_after_tail(state: int, tail32: int) -> int: for b in struct.pack("<I", tail32): state = _step(state, b) return state ^ 0xFFFFFFFF def build_system(prefix: bytes): state = digest(prefix) base = crc_after_tail(state, 0) # f(0) = b cols = [crc_after_tail(state, 1 << i) ^ base for i in range(32)] mat = [] for out_bit in range(32): mask = 0 for in_bit, colvec in enumerate(cols): if (colvec >> out_bit) & 1: mask |= 1 << in_bit mat.append(mask) return mat, base

注意struct.pack("<I", ...)用的小端序，这对应 refin=true。digest里暂不执行 xorout，crc_after_tail最后才做xor 0xFFFFFFFF，这样f的仿射常数没有被提前抵消。cols缓存可以避免 1024 次重复计算 32 位循环，是这段代码的关键优化。

3.3 GF(2) 高斯消元：32 元线性方程在无依赖环境下求解

有了 M 和 b，剩余问题是解 M·tail = target xor b。可以用 numpy 的 mod-2 运算，但这里给一个纯 Python 实现，任何环境都能跑：

def solve_gf2(mat, rhs): aug = [mat[i] | (((rhs >> i) & 1) << 32) for i in range(32)] pivot = {} row = 0 for col in range(32): sel = -1 for r in range(row, 32): if (aug[r] >> col) & 1: sel = r break if sel == -1: continue aug[row], aug[sel] = aug[sel], aug[row] for r in range(32): if r != row and ((aug[r] >> col) & 1): aug[r] ^= aug[row] pivot[col] = row row += 1 for r in range(32): if (aug[r] & 0xFFFFFFFF) == 0 and ((aug[r] >> 32) & 1): raise ValueError("no solution") x = 0 for col, r in pivot.items(): if (aug[r] >> 32) & 1: x |= 1 << col return x

aug的低 32 位是系数行，第 32 位是右侧常数。行消元和普通高斯消元完全一致，只不过每步异或替换了线性组合。消成 RREF 后，每个主元列对应的行末位就是该变量的取值；自由变量统一取 0。如果某行系数全零但右侧为 1，说明方程组无解。

下面验证完整流程：

prefix = b"hello, crc32 collision" target = 0xDEADBEEF mat, base = build_system(prefix) tail = solve_gf2(mat, target ^ base) data = prefix + struct.pack("<I", tail) import zlib print(f"tail={tail:08x}") print(hex(zlib.crc32(data))) # 0xdeadbeef

target ^ base就是方程右边。解出的 tail 附加到任意 prefix 后，CRC32 正好等于 target。这个技巧在改固件、修压缩包、规避旧校验时都出现过；它证明 CRC32 的碰撞能力可以精确到任意目标值，而非只能“凑对”。

3.4 这些参数在构造里各扮演什么角色

上一节的代码默认了标准 CRC-32 的四个参数。改参数时要注意三处连锁反应：一是 poly 换成目标实现的反射多项式；二是struct.pack("<I")在 refin=false 时要改成">I"，否则 bit 顺序对不上；三是 init 和 xorout 虽然只影响 base 和最后一步，但如果拿zlib.crc32对拍，二者也必须一致。用crcmod的话，检查Crc(0x104C11DB7, rev=False, initCrc=...)之类的构造函数，原理一样，只是 API 命名不同。

提示：如果你用zlib.crc32对拍，得到的永远是全 0xFFFFFFFF xorout 的参数组合；crcmod 默认参数可能不同，构造矩阵前先确认参数一致。

4. CRC32 碰撞的现实影响：哪些系统会真的出事

4.1 内容寻址与对象去重：静默数据错配

以 CRC32 作为内容寻址键的系统，把文件的 CRC32 当作文件名或存储地址。碰撞发生时两个不同文件会映射到同一个键，后端“先查后写”的逻辑会认为数据已存在，直接复用旧对象。坏处是静默的：读端拿到的对象不是自己请求的对象，但哈希一致，调用方无法察觉。

这种系统在早期 P2P 分块、分布式缓存、文件去重软件里都真实存在。32 位空间在千万级对象规模下，已有碰撞不是骇人听闻而是可以预见的。正确做法是用 128 位以上哈希做寻址键；在保留 CRC 的旧系统里，至少要叠加对象长度、元数据再哈希，并在写入前做二次确认。

4.2 缓存 Key 与限流指纹：错误命中和串台

把多个字段拼起来做 CRC32 生成缓存 key，是另一种高频用法。正常情况下随机碰撞概率不高，但一旦出现，高并发下两个用户会共享同一份缓存内容，轻则数据错乱，重则把计费、风控的判定结果串给无关用户。攻击者更可以直接构造碰撞，尝试把目标 key 的缓存内容替换。

这类场景的问题不在 CRC32 算得快不快，而在语义上：缓存 key 要求“不同输入得到不同输出”，这恰恰是 CRC 没有的设计目标。替换成 64 位或 128 位非加密哈希（如 XXH3、MurmurHash3 的 128 位变体）性价比最高，同样快但空间大得多。

4.3 固件与安装包校验：从防误码变成防篡改的误用

很多嵌入式设备至今用 CRC32 校验固件：升级包头部的 CRC 字段是明文存储。固件被修改后，只要重新算一个合法 CRC 并写回字段，开机校验就能通过。对于恶意升级、版权绕过这类场景，CRC32 没有任何防御能力。

这里的典型误用是用 CRC 代替 MAC 或签名。如果威胁模型里存在“有人能改文件但校验不更新”，那么必须换成带密钥的 HMAC 或数字签名，不是换一个更长多项式就能解决。若暂时无法换，至少把 CRC 校验配合启动流程中的版本号、平台 ID 一起绑定，增加攻击者构造成本。

4.4 数据库页校验和日志行校验：从概率到可利用

数据库页校验里，CRC32 主要用于检测介质静默损坏，面向随机位翻转，这一用途是合理的。但 MySQL binlog 的 checksum、消息队列单条消息的 CRC 字段同样只有 32 位，在高吞吐系统中会出现偶发校验和碰撞。非恶意情况下概率极低，可一旦有发送端 bug 或内存损坏，碰撞会掩盖整条消息的错误，排障时比直接报错难得多。

在这些系统里建议至少记录 CRC 的透传路径，出现“校验通过但内容解析失败”的告警时，把碰撞当先行指标处理。能用 64 位校验就不要贪图 32 位的速度，特别是消息量大到小时级亿万条时，生日概率已经从“忽略不计”变成“迟早遇上”。

5. 不换哈希的增强路径与替换梯度

CRC32 在检测随机误码的领域仍不可替代：网络帧尾部、磁盘块校验、压缩包结构校验这些场景，目标都是“抓住翻转的 bit”，攻击者不在威胁模型内，32 位冗余足够。换掉它反而可能因为实现复杂引入新问题。

5.1 依然可以放心用的三个场景

传输链路误码检测、内存 bit flip 防护、非对抗环境下的数据块快检，这三个场景把 CRC32 用在它该在的位置。判断标准很简单：输入内容是否可能被人为构造？如果不会，CRC32 的碰撞概率在可接受范围。

5.2 最低成本增强：CRC32C、长度与随机盐

如果暂时不能换，最低成本的增强是把三个独立信号叠起来：内容本身、内容长度、随机盐。

随机盐只在“碰撞由外部预置”的场景有效：每条记录生成随机 4 字节前缀，攻击者无法提前准备固定碰撞。但注意它仍然是 32 位空间里的游戏，防御的是随机碰撞，不是带算力的恶意构造。

5.3 需要抗碰撞时的替换梯度

需要真正抗碰撞时，替换梯度按速度和语义选：

决定前先回答一个问题：如果碰撞被构造出来，系统会不会把错误数据当正确数据用？不会，就留在 CRC；会，就把抵御恶意构造的责任交给密码学哈希。上线前把碰撞响应日志打出来，比把希望寄托在“应该碰不上”上更实际。

本文还有配套的精品资源，点击获取