MD5 三碰撞构造:identical-prefix 二碰撞嵌套两次 + 三层嵌套协议
crypto/hash · verified
一句话结论
题目要求三层 MD5 校验中每组三个不同输入哈希相同,可把每层归约为“固定前缀 + 三个不同后缀、MD5 相同”的子问题;用 fastcoll 在 m0 前缀上做一次 identical-prefix 二碰撞得到 n0/n1,再把 n0 去掉共同前缀的后缀拼回 m1,即可用两次二碰撞构造出三条 MD5 相同的消息。
原理
- MD5 迭代结构:MD5 按 Merkle-Damgård 结构迭代压缩;两条消息若在某个前缀后内部状态相同,则后续拼接相同后缀仍保持哈希相同。identical-prefix collision 工具(fastcoll)正是构造两条共享指定前缀、哈希相同的消息
m0,m1。 - 三碰撞构造:
1. 在
base+tag1上跑 fastcoll,得到m0,m1,MD5(m0)=MD5(m1)。 2. 以m0+tag2为前缀再跑 fastcoll,得到n0,n1,MD5(n0)=MD5(n1)。 3. 令ext0 = n0[len(m0+tag2):],构造c0=n0、c1=n1、c2=m1+tag2+ext0。 - 因为
MD5(m0)=MD5(m1),所以MD5(m1+tag2+ext0)=MD5(m0+tag2+ext0)=MD5(n0);于是c0,c1,c2三条不同消息哈希相同。 - 三层归约:第一层要求
md5(A)=md5(B)=md5(C),第二层要求md5(ha+D)=md5(hb+E)=md5(hc+F),第三层同理。第一层通过后ha=hb=hc,第二层就变成同一前缀ha后接三个后缀;第三层同理。每层只需对共同前缀做一次三碰撞。 - 去重约束:题目要求同一轮 9 段两两不同、十轮之间不复用。构造时把轮次和层编号放进 tag(如
L1|ROUND|i|),让每层前缀不同,从而打散碰撞上下文;生成后先检查本轮 9 段互异,再整体检查跨轮集合。 - 提交后缀:碰撞工具输出的是带前缀的完整消息;远程只接收后缀,需统一裁掉共同前缀
base。 - 为什么成立:MD5 的碰撞可被高效构造(fastcoll 秒级),而题目的校验只比较哈希、不校验长度/内容结构;三层嵌套没有引入新的密码学难度,只是重复同一子问题。
触发条件
- 目标使用 MD5 做多组输入的相等性校验,且允许多轮/多组提交。
- 攻击者能运行 fastcoll(或等价 identical-prefix MD5 碰撞工具),并能为每层选择共同前缀。
- 题目对输入长度/字符集没有严格限制,或允许二进制后缀。
- 有去重逻辑时,需要能控制前缀/后缀使各组消息互异。
利用步骤
- 分析校验逻辑:确认每层都是“三组输入的 MD5 相等”,且上一层输出会作为下一层前缀的一部分。
- 实现
triple_collision(base, tag):m0,m1 = fastcoll(base+tag1);n0,n1 = fastcoll(m0+tag2);ext0 = n0[len(m0+tag2):];返回n0, n1, m1+tag2+ext0。 - 第一层用空前缀生成
A,B,C;第二层用ha生成D,E,F;第三层用hd生成G,H,I。 - 每层 tag 带轮次/层号;生成后检查 9 段互异,并检查跨轮不复用。
- 把每条消息裁掉共同前缀,得到远程需要的后缀;按提示符逐条提交。
- 若 fastcoll 输出不满足前缀/碰撞校验,重跑或换工具版本;缓存已生成的碰撞对以加速多轮。
PoC
import hashlib, subprocess, tempfile, os
def H(m): return hashlib.md5(m).digest()
def fastcoll(prefix: bytes):
with tempfile.TemporaryDirectory() as td:
open(os.path.join(td, "prefix.bin"), "wb").write(prefix)
subprocess.run(["fastcoll", "--prefixfile", "prefix.bin",
"-o", "m1.bin", "m2.bin"], cwd=td, check=True)
m1 = open(os.path.join(td, "m1.bin"), "rb").read()
m2 = open(os.path.join(td, "m2.bin"), "rb").read()
assert m1 != m2 and H(m1) == H(m2)
assert m1.startswith(prefix) and m2.startswith(prefix)
return m1, m2
def triple(base: bytes, tag: bytes):
m0, m1 = fastcoll(base + b"L1|" + tag + b"|")
n0, n1 = fastcoll(m0 + b"L2|" + tag + b"|")
ext0 = n0[len(m0 + b"L2|" + tag + b"|"):]
c0, c1, c2 = n0, n1, m1 + b"L2|" + tag + b"|" + ext0
assert len({H(c0), H(c1), H(c2)}) == 1
assert len({c0, c1, c2}) == 3
return c0, c1, c2
# 每层:A,B,C = triple(b"", tag1); D,E,F = triple(H(A), tag2); G,H,I = triple(H(H(A)+D), tag3)
变体与关联
- 碰撞工具变体:fastcoll、hashclash、Marc Stevens 的 chosen-prefix 工具;chosen-prefix 更强但更慢,identical-prefix 足够本题。
- 层数变体:两层/四层同理,每层对共同前缀做三碰撞;更多层只是重复。
- 去重变体:tag 里加入随机 nonce/轮次/层号;若题目限制后缀长度,需要压缩 tag 或使用更短的碰撞块。
- 关联:[[ctf-crypto-linear-hash-collision-lll]](线性哈希碰撞的格方法)、[[crypto-hash-md5-digest-strcmp-nullbyte-truncation]](MD5 摘要比较缺陷)。
检测与防御
- 检测:提交数据中出现大量二进制/高熵块、重复的碰撞块特征、每轮 9 段长度异常;同一前缀反复出现;MD5 校验通过但内容不可读。
- 防御:不要用 MD5 做安全相等性校验;改用 SHA-256/SHA-3 或 HMAC;对输入做长度/字符集/结构限制;对多轮提交做去重与速率限制。
- 加固:若必须兼容旧哈希,使用带密钥的 HMAC 或对哈希结果再做一次签名;禁止把 MD5 用作完整性/身份凭据。