布兹 CTF「你的眼睛好吗？」完整解题思路 Sage 攻击代码

一、题目原理梳理1. 参数与生成逻辑题目基于ML-DSA Level5Dilithium5参数环\(R_q \mathbb{F}_q[X]/(X^{256}-1)\)\(q83804172^{23}-2^{13}1\)矩阵维度\(A \in R_q^{k\times l},\ k8,l7\)小系数分布\(\eta2\)即 \(s,e\) 每个多项式系数取自 \(\{-2,-1,0,1,2\}\)两种样本MLWE 样本返回 1\(t A\cdot s e\)\(s\leftarrow\chi_\eta^l,\ e\leftarrow\chi_\eta^k\)\(s/e\) 所有多项式系数范围 \([-2,2]\)随机样本返回 0$r \xleftarrow {\$} R_q^k$每个多项式系数均匀取自 $[0,q-1]$几乎全是大数2. 核心区分漏洞MLWE 向量 \(tAse\) 中每个多项式的所有系数都是 7 个小系数s线性组合再加 1 个小系数e取值范围远小于均匀随机向量 均匀随机向量 r 的系数遍布整个模空间 \([0,q-1]\)几乎没有小数值。最简区分特征 对向量 \(t/r\) 内每一个多项式展开全部 256 个系数统计绝对值≤2 的系数数量MLWE 向量大量系数绝对值≤2数百个均匀随机向量几乎没有绝对值≤2 的系数0~ 几个仅靠这个统计特征就能 100% 区分两种分布答对 128 轮即可输出 flag。二、完整 SageMath 攻击代码1. 解码辅助函数sageimport gzip, base64 from ast import literal_eval RING_RANK 256 q 8380417 Fq GF(q) base_ring.x Fq[] Rq.X base_ring.quotient_ring(x^RING_RANK - 1) def isanitize_mat(s): s base64.b64decode(s) s gzip.decompress(s) data literal_eval(s.decode()) return Matrix(Rq, [[Rq(sss) for sss in ss] for ss in data]) def isanitize_vec(s): s base64.b64decode(s) s gzip.decompress(s) data literal_eval(s.decode()) return vector(Rq, [Rq(ss) for ss in data]) def count_small_coeffs(vec, bound2): 统计向量所有多项式中绝对值≤bound的系数总数 total 0 for poly in vec: coeffs poly.list() # 展开多项式256个系数 for c in coeffs: c_abs min(c, q - c) # 模q下的最小绝对值 if c_abs bound: total 1 return total def distinguish(A_str, t_str): # 解码A和t A isanitize_mat(A_str) t isanitize_vec(t_str) cnt count_small_coeffs(t, 2) # 阈值经验MLWE样本cnt 100随机样本cnt 10 if cnt 50: return 1 # MLWE else: return 0 # 随机2. 交互自动化逻辑netcat 对接python运行from pwn import * # 连接题目服务替换为题目Connect地址 io remote(archive.cryptohack.org, 43607) for round in range(130): # 读取sanitize_mat(A)行 io.recvuntil(bsanitize_mat(A) ) A_b64 io.recvline().strip().decode() # 读取sanitize_vec(t)行 io.recvuntil(bsanitize_vec(t) ) t_b64 io.recvline().strip().decode() # 读取提示符 io.recvuntil(b ) # 执行区分 res distinguish(A_b64, t_b64) io.sendline(str(res).encode()) # 打印轮次日志 resp io.recvline().decode() print(f第{round1}轮 | 判定{res} | 服务返回{resp}) if flag in resp: print([] 获取flag, resp) break三、原理细节解释多项式系数绝对值计算模 q 下系数 c 的真实最小绝对值为 \(\min(c,\ q-c)\)例如 \(q-1\) 等价于 \(-1\)绝对值为 1。阈值选择MLWE 输出 \(tAse\)每一项是 7 个\([-2,2]\)数相乘求和再加 1 个\([-2,2]\)误差系数分布高度集中在 0 附近一轮统计数百个小系数均匀随机向量 r每个系数均匀分布在 \([0,q-1]\)恰好落在 \([-2,2]\) 的概率仅 \(5/q \approx 6\times10^{-7}\)8 个多项式 ×256 系数总共期望仅 1 个以内小系数。 设置阈值50完全可以无错区分。