线性模哈希碰撞:把 Σ(2g)^{i-k}g·e_k≡0 mod N 转成 [E|R;0|N] 格,LLL 求短差分向量
ctf/crypto · verified
一句话结论
哈希若按 n_{i+1} = g·(2n_i + m_i) mod N 迭代,展开后是消息字节的线性函数;两条消息 s、t 碰撞等价于 Σ_k (2g)^{i-k}g·(s_k−t_k) ≡ 0 (mod N)。把 R=[(2g)^i g,…,(2g)^0g]、单位阵 E 与 N 拼成格 M=[[E,R],[0,N]],LLL 找到短向量 (e_0,…,e_i,k),用 e_k 调整一条消息即可构造碰撞。
原理
- 展开迭代:
n_{i+1}=(2g)^{i+1}n_0+Σ_{k=0}^i (2g)^{i-k}g·m_k mod N;哈希输出再减去常量0xdeedbeef114514,不影响碰撞条件。 - 碰撞条件:两条消息
s、t的哈希差为Σ_k (2g)^{i-k}g·(s_k−t_k) mod N;要碰撞,需要这个和≡0 mod N。令e_k=s_k−t_k,就是找一个短向量e满足线性同余。 - 格构造:令
R为列向量[(2g)^i g, (2g)^{i-1} g, …, g]^T,E为msize×msize单位阵,构造text M = [ E R 0 N ]格中向量(e_0,…,e_i, k)(k为整数)满足e·R + k·N ≡ 0 mod N,即碰撞条件。LLL 会找到短向量e(消息差分)和对应的k。 - 构造碰撞:取一条消息
s(如全a),另一条t=s−e(逐字节减,注意字节范围/模 256);由于e小,t仍在合法字节范围内时即可得到碰撞对。 - 为什么成立:线性哈希没有非线性混淆,碰撞问题退化为“找短整数向量满足一个模线性方程”;LLL 能在多项式时间找到短向量,从而构造碰撞。
- 参数:消息长度
msize、g、N;R的指数按消息长度取(2g)^i到(2g)^0,方向不要反。
触发条件
- 哈希/校验函数是消息字节的线性/仿射函数(迭代式为
n = a·n + b·m + c mod N等)。 - 已知
g、N、消息长度;需要构造两条不同消息但相同哈希值。 - 能运行 Sage/LLL;短向量
e的每个分量落在可调整的字节范围内(或可通过多次尝试/加 Padding 调整)。 - 哈希没有强非线性/压缩函数(如 MD5/SHA 的 ARX/布尔混淆)。
利用步骤
- 逆出哈希迭代式与常量:确认
n_{i+1}=g(2n_i+m_i) mod N,并展开成线性形式。 - 取消息长度
msize,构造R=[(2g)^i g, …, (2g)^0 g](列向量,注意顺序),E=identity_matrix(msize)。 - 构造
M=block_matrix([[E,R],[0,matrix([N])]]),LLL 约减。 - 在约减基中找最后一维非零且向量分量较小的行
X;短向量给出e(前msize个分量)与k(最后一维)。 - 取
s(如b'a'*msize),令t=s−e(逐字节,必要时模 256/加偏移),计算hash(s)与hash(t)验证相等。 - 若
t字节越界,调整s、msize、R顺序或换 LLL 基向量重试。
PoC
# Sage
msize = ...
R = [(2 * g) ** i * g for i in range(msize)]
R = column_matrix(R[::-1]) % N
E = identity_matrix(msize)
M = block_matrix([[E, R], [0, matrix([N])]])
X = M.LLL()
sbytes = b'a' * msize
print(sbytes, hash(sbytes))
tbytes = list(b'a' * msize)
for i in range(msize):
tbytes[i] -= X[2][i] # 取 LLL 约减基中的短差分向量
tbytes = bytes(tbytes)
print(tbytes, hash(tbytes))
原文用该构造得到相同哈希的两条不同字节流;未在本库复跑。
变体与关联
- 线性变体:
n=a·n+b·m+c mod N、多字节/多轮、带 XOR 的线性化;先展开成消息字节的线性组合。 - 格变体:
[E|R;0|N]、[I|R;0|N]、Kannan embedding;LLL/BKZ 找短向量。 - 哈希变体:CRC/Adler32 等线性校验、多项式哈希、滚动哈希;非线性哈希(MD5/SHA)不适用。
- 关联卡片:[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](LLL 短向量)、[[ctf-crypto-noise-crt-lattice-recovery]](线性同余 + 格)。
检测与防御
- 哈希设计:不要用线性/仿射模哈希做安全校验;使用 SHA-2/SHA-3/BLAKE 等带非线性压缩的哈希,或 HMAC。
- 参数:若必须用滚动哈希,至少加入密钥化/非线性混淆,并限制消息长度/差分空间。
- 检测:检查哈希实现是否为
a*n+b*m+c mod N形式;对公开参数做 LLL 短向量探测,评估碰撞可行性。