ML-DSA/Dilithium 签名 nonce 泄露:z-r=c·s1-noise 最小二乘恢复私钥
crypto/implementation · verified
一句话结论
签名实现返回 c, z, r,其中 z = y + c*s1、r = y + noise,因此 z - r = c*s1 - noise;s1 的系数只有 [-2,2]、noise 只有 [-15,15],把每个 challenge 多项式 c 展开成卷积矩阵 M_c,收集约 100–160 个签名做最小二乘,噪声被平均掉后四舍五入即可恢复 s1,再按正常签名流程伪造目标消息签名。
原理
- Dilithium/ML-DSA 的签名中
z = y + c*s1,其中y是掩码向量,c是 challenge 多项式,s1是私钥向量。 - 题目额外返回
r = y + noise,于是z - r = c*s1 - noise。noise的系数范围[-15,15],s1的系数范围[-2,2],后者是稀疏小量。 - 环为
Z_q[x]/(x^64+1);多项式乘法c*s1_i可以写成卷积矩阵M_c * s1_i。每个签名给出 64 条方程,而s1_i只有 64 个未知系数。 - 单个签名被噪声污染,但多个签名的噪声独立;把
K个M_c纵向堆叠、K组(z_i - r_i)拼接,做最小二乘solve(M, y),噪声的均值趋近 0。 - 对解四舍五入并裁剪到
[-2,2],即可恢复s1(案例 160 个签名,残差约 0.36/0.40,仍能正确舍入)。 - 恢复
s1后,按正常签名流程对目标消息生成c, z,通过verify即可获取 flag;不需要破解 ML-DSA 的格难题。
触发条件
- 签名接口返回
z与r(或任何泄露y + noise的中间值),且r与z使用同一个y。 s1系数范围很小(如[-2,2]),噪声范围有界且独立。- 攻击者能收集足够多的签名(案例 100–160 个),且 challenge 多项式
c已知。 - 环维度
n=64、模数q已知;签名验证接口可用于最终验证。
利用步骤
- 请求大量非目标消息的签名,记录每个
(c, z, r)。 - 对每个 challenge 多项式
c构造n x n卷积矩阵M_c(注意x^n = -1的符号)。 - 对每个私钥分量
i,把所有M_c纵向堆叠,把所有(z_i - r_i)拼接为右端向量。 - 用
numpy.linalg.lstsq求解,得到带噪的s1_i估计;四舍五入并裁剪到[-eta, eta](案例 eta=2)。 - 用恢复的
s1对目标消息签名:采样y、计算w=A*y、c=H(msg,w1)、z=y+c*s1,检查z的范数约束后提交。 - 若验证失败,增加签名数量、检查卷积矩阵符号/系数顺序、确认
r的采样范围与z的编码。
PoC
import numpy as np
def conv_matrix(c_coeffs, n):
c = challenge.Poly(c_coeffs).centered_list()
mat = np.zeros((n, n), dtype=float)
for out_idx in range(n):
for secret_idx in range(n):
if secret_idx <= out_idx:
c_idx, sign = out_idx - secret_idx, 1
else:
c_idx, sign = out_idx + n - secret_idx, -1
mat[out_idx, secret_idx] = sign * c[c_idx]
return mat
def recover_s1(samples):
matrices = []
rhs = [[] for _ in range(challenge.l)]
for c_coeffs, z_lists, r_lists in samples:
matrices.append(conv_matrix(c_coeffs, challenge.n))
for i in range(challenge.l):
rhs[i].append(np.array(z_lists[i]) - np.array(r_lists[i]))
big = np.vstack(matrices)
recovered = []
for i in range(challenge.l):
y = np.concatenate(rhs[i])
sol, *_ = np.linalg.lstsq(big, y, rcond=None)
rounded = np.clip(np.rint(sol).astype(int), -challenge.eta, challenge.eta)
recovered.append(challenge.Poly(rounded.tolist()))
return recovered
案例收集 160 个签名后恢复 s1,并成功伪造目标签名,得到 NepCTF{ML_DSA_n0nse_l34k_4tt4ck}。
变体与关联
- 变体:只泄露
y的部分低位/高位时,可把已知部分代入,构造类似的线性系统或格。 - 变体:噪声更大时,最小二乘可能不足以舍入,需要把问题建模为 LWE/CVP 并做格约减。
- 变体:
s1系数范围更大或分布不均匀时,可用最大似然/整数规划替代简单舍入。 - 关联:[[ctf-crypto-dilithium-like-exact-t-as-linear-system-secret-recovery]](无噪声精确线性方程版本)、[[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]](格/CVP 方法)、[[crypto-implementation-mldsa-nonce-leak-least-squares-key-recovery]](本卡)。
检测与防御
- 防御:签名实现绝不能返回
y、r或任何y的线性函数;只返回标准(c, z)。 - 防御:使用标准库/经过审计的 ML-DSA 实现,严格遵循拒绝采样与范数检查;不要为了调试输出中间值。
- 防御:对签名接口做速率限制与鉴权,避免攻击者收集大量样本。
- 检测:签名响应中出现额外字段(
r、y、w等);同一私钥在短时间内产生大量签名;验证失败率异常。 - 响应:发现 nonce/中间值泄露后立即轮换密钥,审计历史签名是否可恢复私钥,修复接口字段并重新编译。