Wagner 广义生日求 SHA3-512 模素数 k-sum:8 路合并构造哈希碰撞过服务端校验
ctf/crypto · verified
一句话结论
当服务端把 SHA3-512(r || suffix) mod N 当作哈希并要求提交一组 r 使这些哈希满足碰撞/求和条件时,可以把问题化成模 N 的 k-sum:用 Wagner 广义生日算法按 tree_height 分层合并候选,每层只保留低若干位相同的组合,最终在 2^tree_height 个叶子中找到一组哈希值之和 ≡ 0(或目标值)的 r;原文用 tree_height=3(8 个 r)在 73 位模数上快速命中。
原理
- 问题形式:哈希函数
H(r) = int(SHA3-512(r_bytes || suffix)) mod N,r_bytes长度按N.bit_length()向上取整。服务端给出固定的suffix,要求攻击者提交若干r,使Σ H(r_i) ≡ 0 (mod N)(或满足其碰撞条件)。 - 广义生日(Wagner):朴素生日攻击找两两碰撞需要
2^(n/2);Wagner 把 k-sum 组织成深度为tree_height的二叉树:叶子是随机候选(H(r), r),每层把两组列表按“哈希和在模2^b下相等”合并,逐步消去低位,最后剩下满足完整模N条件的组合。tree_height=3表示 8 个叶子(2³),每一层降低一部分模数位数,总候选量远小于暴力枚举。 - 为什么适用于本题:
N为 73 位素数(原文4722366482869645213711),直接把 8 个随机哈希求和命中 0 的概率是1/N,不可行;分层只匹配低位后,每层组合数可控,最终 8 路合并把搜索复杂度降到可接受范围。 - Lineage 结构:
wagner.Lineage(hash_value, r)保存当前节点的哈希值与原始r(以及合并历史);wagner.solve(N, tree_height, generator)返回一组r值,调用方再把每个r与suffix拼成消息提交。 - 成立前提:哈希对
r没有额外结构限制(随机预言机假设),且服务端确实按模N求和/比较;tree_height与所需消息条数要和协议匹配(原文为 8 条)。
触发条件
- 服务端提供一个固定后缀
suffix,对攻击者提交的r计算SHA3-512(r || suffix) mod N并要求一组值满足求和/碰撞条件。 N的位数使朴素生日攻击不可行,但足以让 Wagner 分层合并跑完。- 能使用
conduition/wagner等实现(或自行实现 Wagner 合并);能按协议连续提交多条消息。 - 原文靶场为动态 flag,脚本需在线连接。
利用步骤
- 连接服务端,先按协议发送初始
x/y/z(原文用带双空格的字符串影响后缀生成),读取服务端返回的suffix十六进制。 - 定义生成器:随机取
r,按N.bit_length()计算字节长度,计算SHA3-512(r_bytes || suffix) mod N,返回wagner.Lineage(hash, r)。 - 调用
wagner.solve(N, tree_height=3, generator=generator),得到 8 个r。 - 把每个
r转为固定长度十六进制,与suffix拼接,按协议逐条发送。 - 读取服务端响应;若校验通过则返回 flag(原文为动态 flag,给出了复现实例)。
PoC
import hashlib, random
import wagner # https://github.com/conduition/wagner
MODULUS = 4722366482869645213711
SUFFIX = bytes.fromhex("<服务端返回的 suffix>")
def make_generator(n, suffix):
rlen = (n.bit_length() + 7) // 8
def gen(modulus, index):
r = random.randrange(0, modulus)
h = int.from_bytes(
hashlib.sha3_512(r.to_bytes(rlen, "big") + suffix).digest(), "big"
) % modulus
return wagner.Lineage(h, r)
return gen
r_values = wagner.solve(MODULUS, tree_height=3, generator=make_generator(MODULUS, SUFFIX))
for r in r_values:
rlen = (MODULUS.bit_length() + 7) // 8
print(r.to_bytes(rlen, "big").hex() + SUFFIX.hex())
变体与关联
- 哈希/模数变体:SHA-256/SHA3/BLAKE 等只要输出可映射到模
N的整数即可;N越大需要越高的tree_height或更多候选。 - 条件变体:目标不是 0 而是固定
target,在合并时把目标减去即可;也可以要求两条消息同哈希(经典碰撞)。 - 实现变体:
conduition/wagner、k-sum库或自行写分层合并;注意每层保留的位数与内存/时间权衡。 - 关联:[[ctf-crypto-linear-hash-collision-lll]](线性模哈希用 LLL 求短向量,不是广义生日)、[[crypto-hash-md5-three-way-collision-nested-fastcoll]](MD5 多碰撞构造)。
检测与防御
- CTF 性质:这是对“模素数哈希 + 求和校验”设计的攻击,不是通用漏洞。
- 设计防御:不要用
H(r) mod N的求和作为唯一校验;使用带密钥的 MAC/签名、域分离与抗碰撞哈希,并限制提交条数与请求频率。 - 检测:服务端若看到同一
suffix下大量短时间提交的r且哈希和恰好为 0,应视为异常;对挑战协议加入服务端随机性与不可预测的绑定值。