CRC32 四字节原像:GF(2) 线性矩阵求逆从已知 CRC 还原 ZIP 未知内容
ctf/misc · verified
一句话结论
CRC32 对固定长度输入是 GF(2) 上的仿射变换;当一个 ZIP 条目只含 4 字节内容、CRC32 已知时,可构造 32×32 的线性矩阵并求逆,从 CRC ^ CRC(0000) 直接解出这 4 个字节,无需爆破 2^32 空间;把多个条目的 4 字节结果按序拼接即可还原隐藏消息。
原理
- CRC32 的更新过程只包含异或与移位,对消息比特是线性的:对固定长度
L,存在 32×32 的 GF(2) 矩阵M,使CRC(m) = M·m ⊕ c,其中c = CRC(0^L)。 - 对 4 字节消息,
m有 32 个比特,M是 32×32 方阵;标准 CRC32 多项式下该映射是双射,因此M可逆。 - 构造方法:令
e_j为“第 j 位为 1、其余为 0”的 4 字节消息,计算col_j = CRC(e_j) ⊕ CRC(0000),得到M的 32 个列向量;再用高斯消元求M^{-1}。 - 已知
CRC(m)后,m = M^{-1}·(CRC(m) ⊕ CRC(0000));按位拼回 4 字节即可。 - 为什么不是“哈希破解”:CRC32 不是密码学哈希,没有抗原像性;32 位输入/32 位输出的线性映射可以被精确求逆,计算量只有一次 32×32 矩阵求逆(O(32^3) 位运算)。
- 原文场景:
pass*.zip每个条目只含 4 字节文件内容,ZIP 中央目录给出 CRC32;按上述方法逐条还原 4 字节,按文件名编号拼接得到隐藏消息/下一层密码。
触发条件
- 已知某个 ZIP 条目的 CRC32(ZIP 目录中直接可见),且该条目内容长度固定为 4 字节(或可枚举的分段长度)。
- 使用标准 CRC32(ZIP/PNG/zlib 常见多项式
0xEDB88320,初值/最终异或按实现);多项式或初值不同则需按实际参数重建矩阵。 - 内容不是必须为 ASCII;若是,可在解出后按可打印性验证。
- 有多个条目时,每个条目独立求逆,最后按文件名/编号排序拼接。
利用步骤
- 用
zipfile读取每个条目的CRC与file_size;筛出file_size == 4的条目。 - 计算
const = zlib.crc32(b"\x00" * 4) & 0xffffffff。 - 对
j=0..31构造只含第 j 位为 1 的 4 字节消息,计算col_j = crc32(msg) ^ const,得到 32 个列向量。 - 把列向量拼成 32×32 矩阵,用 GF(2) 高斯消元求逆(原文把矩阵行扩展为
row | (1<<(32+i)),消元后右半即逆矩阵)。 - 对每个条目计算
vec = crc ^ const,用逆矩阵左乘得到 32 位值x,plain = x.to_bytes(4, "little")。 - 拼接所有
plain,按 ASCII/文件头验证;若结果乱码,检查 CRC 参数(多项式、初值、最终异或)与字节序。
PoC
import glob, os, re, zipfile, zlib
files = sorted(glob.glob("pass*.zip"),
key=lambda p: int(re.search(r"(\d+)", os.path.basename(p)).group(1)))
const = zlib.crc32(b"\x00" * 4) & 0xffffffff
# 构造 CRC32 的 32x32 GF(2) 矩阵并求逆
cols = []
for j in range(32):
x = bytearray(4)
x[j // 8] = 1 << (j % 8)
cols.append((zlib.crc32(bytes(x)) & 0xffffffff) ^ const)
rows = [0] * 32
for j, col in enumerate(cols):
for i in range(32):
if (col >> i) & 1:
rows[i] |= 1 << j
aug = [rows[i] | (1 << (32 + i)) for i in range(32)]
r = 0
for c in range(32):
pivot = next(i for i in range(r, 32) if (aug[i] >> c) & 1)
aug[r], aug[pivot] = aug[pivot], aug[r]
for i in range(32):
if i != r and ((aug[i] >> c) & 1):
aug[i] ^= aug[r]
r += 1
inv_rows = [(aug[i] >> 32) & 0xffffffff for i in range(32)]
parts = []
for f in files:
with zipfile.ZipFile(f) as zf:
info = zf.infolist()[0]
if info.file_size != 4:
continue
vec = info.CRC ^ const
x = 0
for i, row in enumerate(inv_rows):
x |= ((row & vec).bit_count() & 1) << i
parts.append(x.to_bytes(4, "little"))
print(b"".join(parts))
变体与关联
- 变体:8 字节内容需要 64×64 矩阵;更长内容无法仅凭 32 位 CRC 唯一还原,需结合已知前缀/可打印约束或更多校验。
- 变体:CRC16/CRC64 或其他多项式,按实际参数重建矩阵;初值/最终异或只需并入
const。 - 变体:若内容限定 ASCII,可把 32 位解再按每字节 0x20–0x7e 过滤/枚举多个解。
- 关联:[[ctf-misc-nested-zipcrypto-base32-crc32-overlap-chain]](用 CRC32 作修复 oracle 的暴力版本);[[ctf-forensics-png-ihdr-width-height-crc32-brute-force]](PNG 头字段的 CRC 校验);[[ctf-misc-zip-local-header-repair-pseudo-encryption]](ZIP 结构修复)。
- 关联:CRC32 只用于检错,不应作为完整性/认证机制;需要抗篡改时用密码学 MAC/签名。
检测与防御
- 检测(分析侧):ZIP/PNG 等格式中已知 CRC 且内容长度很短(4/8 字节)时,优先尝试线性代数求逆,而不是 2^32 爆破。
- 检测(防御侧):不要把 CRC32 当作隐藏数据或身份校验的安全边界;攻击者可利用其线性性直接构造/还原内容。
- 防御:需要完整性时使用 HMAC-SHA256、数字签名或 AEAD;不要用 CRC32 保护敏感配置。
- 响应:若发现业务用 CRC32 校验短密钥/令牌,视为可伪造,立即更换为密码学校验并轮换相关凭据。