小参数 LWE 暴力枚举:n=6、s∈{0..3}、噪声±1 直接搜 secret 并派生 AES key
crypto/implementation · verified
一句话结论
当 LWE 参数极小(n=6、q=97、s_i∈{0,1,2,3}、噪声 e_i∈{-1,0,1})时,不需要格约减:直接枚举 4^6=4096 个 secret,对 30 组样本检查 (a_i·s - b_i) mod q 的居中表示是否都在 {-1,0,1},唯一命中的 secret 即解;再把 SHA256(str(secret))[:16] 作为 AES-CBC key 解密即可。
原理
- LWE 样本:
b_i = <a_i, s> + e_i mod q,a_i公开、s为 secret、e_i为小噪声。 - 一般 LWE 需要格约减(LLL/BKZ/CVP);但当 secret 空间很小(每个分量只有 4 种取值,总空间 4096)时,穷举比格攻击更简单。
- 对每个候选
s,计算diff_i = centered_mod(<a_i,s> - b_i, q),其中centered_mod把[0,q)映射到(-q/2, q/2];若所有diff_i ∈ {-1,0,1},候选极可能是真实 secret。 - 30 组样本提供足够约束,随机候选全部命中的概率极低;因此第一个满足的候选通常唯一。
- 题目用
SHA256(str(solution).encode()).digest()[:16]作为 AES-128-CBC key,iv/enc在data.txt中;解密后去 PKCS#7 padding 即 flag。 - 这个场景的教训是:LWE 安全性依赖参数(n、q、噪声分布、secret 空间);参数过小会退化为暴力搜索。
触发条件
- 题目给出多组
(a_i,b_i)、模数q、维度n,且 secret 分量取值空间很小(如{0..3})。 - 噪声范围很小(如
{-1,0,1}),可用居中模差验证候选。 - secret 总空间
k^n在可枚举范围内(案例 4096)。 - 有 AES-CBC 密文/iv,key 由 secret 的字符串形式派生。
利用步骤
- 从
data.txt读取n,q,A,b,iv,enc。 - 枚举
itertools.product(range(4), repeat=n)的所有候选 secret。 - 对每个候选,计算每组样本的
diff = centered_mod(sum(a*s)-b, q);若任一diff不在{-1,0,1}则淘汰。 - 第一个全部通过的候选即 secret;记录
errors验证噪声范围。 - 计算
key = sha256(str(solution).encode()).digest()[:16]。 - 用
AES.new(key, AES.MODE_CBC, iv).decrypt(enc)解密,去 PKCS#7 padding,输出 flag。
PoC
import hashlib, itertools, json
from pathlib import Path
from Crypto.Cipher import AES
def centered_mod(value, q):
value %= q
return value - q if value > q // 2 else value
def unpad(data):
pad = data[-1]
if pad < 1 or pad > 16 or data[-pad:] != bytes([pad]) * pad:
raise ValueError("invalid PKCS#7 padding")
return data[:-pad]
data = json.loads(Path("data.txt").read_text())
n, q, A, b = data["n"], data["q"], data["A"], data["b"]
iv, enc = bytes.fromhex(data["iv"]), bytes.fromhex(data["enc"])
solution = None
for s in itertools.product(range(4), repeat=n):
errors = []
for row, target in zip(A, b):
diff = centered_mod(sum(x * y for x, y in zip(row, s)) - target, q)
if diff not in (-1, 0, 1):
break
errors.append(diff)
else:
solution = list(s)
print("secret =", solution, "errors =", errors)
break
assert solution is not None
key = hashlib.sha256(str(solution).encode()).digest()[:16]
print(unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(enc)).decode())
案例输出:secret = [0, 0, 2, 1, 1, 1],flag 为 DASCTF{LWE_l4tt1c3_r3duct10n_i5_p0w3rful!}。
变体与关联
- 变体:secret 空间稍大时改用 meet-in-the-middle、z3 约束求解或格约减(LLL/BKZ/CVP)。
- 变体:噪声范围更大时,候选验证阈值放宽或改用最大似然/最小二乘。
- 变体:key 派生可能是
SHA256(secret bytes)、str(list)、JSON 序列化等;按题目代码复现。 - 关联:[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](LLL/Kannan embedding 解 LWE)、[[crypto-implementation-mldsa-nonce-leak-least-squares-key-recovery]](最小二乘)、[[ctf-crypto-z3-short-input-128bit-state-constraint]](Z3 约束求解)。
检测与防御
- 防御:使用标准 LWE 参数(足够大的 n、q、噪声分布),不要用可枚举的小 secret 空间。
- 防御:密钥派生使用 CSPRNG/标准 KDF,不要用低熵 secret 的字符串哈希作为 AES key。
- 检测:代码中出现
random.randint(0,3)生成 secret、q=97等小参数、itertools.product(range(4))枚举。 - 响应:发现参数过小后更换密钥/参数,审计历史密文是否可被暴力恢复。