一、题目原理梳理
1. 参数与生成逻辑
题目基于ML-DSA Level5（Dilithium5）参数：
- 环：\(R_q = \mathbb{F}_q[X]/(X^{256}-1)\)，\(q=8380417=2^{23}-2^{13}+1\)
- 矩阵维度：\(A \in R_q^{k\times l},\ k=8,l=7\)
- 小系数分布：\(\eta=2\)，即 \(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 向量 \(t=As+e\) 中每个多项式的所有系数，都是 7 个小系数（s）线性组合再加 1 个小系数（e），取值范围远小于均匀随机向量； 均匀随机向量 r 的系数遍布整个模空间 \([0,q-1]\)，几乎没有小数值。
最简区分特征： 对向量 \(t/r\) 内每一个多项式展开全部 256 个系数，统计绝对值≤2 的系数数量：
- MLWE 向量：大量系数绝对值≤2（数百个）
- 均匀随机向量：几乎没有绝对值≤2 的系数（0~ 几个）
仅靠这个统计特征就能 100% 区分两种分布，答对 128 轮即可输出 flag。
二、完整 SageMath 攻击代码
1. 解码辅助函数
sage
import 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, bound=2): """统计向量所有多项式中绝对值≤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(b"sanitize_mat(A) = ") A_b64 = io.recvline().strip().decode() # 读取sanitize_vec(t)行 io.recvuntil(b"sanitize_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"第{round+1}轮 | 判定{res} | 服务返回：{resp}") if "flag" in resp: print("[+] 获取flag：", resp) break三、原理细节解释
- 多项式系数绝对值计算模 q 下系数 c 的真实最小绝对值为 \(\min(c,\ q-c)\)，例如 \(q-1\) 等价于 \(-1\)，绝对值为 1。
- 阈值选择
- MLWE 输出 \(t=As+e\)：每一项是 7 个\([-2,2]\)数相乘求和再加 1 个\([-2,2]\)误差，系数分布高度集中在 0 附近，一轮统计数百个小系数；
- 均匀随机向量 r：每个系数均匀分布在 \([0,q-1]\)，恰好落在 \([-2,2]\) 的概率仅 \(5/q \approx 6\times10^{-7}\)，8 个多项式 ×256 系数总共期望仅 1 个以内小系数。 设置阈值
50完全可以无错区分。
