NTRU 样本模 x+1 投影 LLL 区分:恢复 coin 位后预测 MT19937 解 AES
ctf/crypto · verified
一句话结论
在 Z_q[x]/(x^n+1) 中 x+1 是 x^n+1 的因子;把 NTRU 样本 f*h_i = g_i 模 x+1 后得到一个小整数方程 f(-1)*h_i(-1) = g_i(-1)。用 [[1,h1,h2],[0,q,0],[0,0,q]] 做 LLL,短向量范数小于阈值即判定该 hint 是真实样本,从而恢复每轮的 coin 位;收集足够位后用 MT19937 线性系统预测后续随机数,SHA-256 派生 AES key 解密。
原理
- 本题
n=1031为奇数,x=-1时(-1)^n+1=0,所以x+1 | x^n+1。在商环Z_q[x]/(x+1)中x等价于-1,一个多项式模x+1就是“系数正负交替求和”,得到一个标量。 - NTRU 关系
f*h_i ≡ g_i (mod x^n+1)模x+1后仍成立:f(-1)*h_i(-1) ≡ g_i(-1) (mod q)。由于f、g_i的系数都很小,f(-1)与g_i(-1)也是小整数。 - 服务器每轮给出两个 hint
h1,h2,其中一个是真实 NTRU 公钥样本、另一个是随机值;真实样本存在小向量(f(-1), g_1(-1), g_2(-1)),随机 hint 没有。构造格[[1,h1,h2],[0,q,0],[0,0,q]],LLL 后第一行就是该小向量(或它的短组合);真实样本范数远小于随机样本,用阈值(本题<100)即可判定 coin 位。 - coin 位序列就是 MT19937 的
getrandbits(1)输出。位是状态的线性函数,用gf2bv的LinearSystem建立 624×32 个状态位的方程,解出状态后克隆 RNG。 - 后续密钥为
SHA256(str(rng.getrandbits(256))),AES-ECB 解密即可。
触发条件
- 题目使用
x^n+1且n为奇数,因此x+1是公开的线性因子;攻击者可以把高维 NTRU 样本降到一维小整数方程。 f、g的系数足够小,使f(-1)、g(-1)落在 LLL 能区分的范围内;q足够大。- 可反复查询,每轮泄漏 1 bit(哪个 hint 为真),且该 bit 来自 MT19937。
- 后续随机数直接用于密钥派生,攻击者知道派生格式。
利用步骤
- 反复向服务查询,每轮拿到两个 hint
h1,h2。 - 分别计算
h1 % (x+1)、h2 % (x+1)(即系数交替和),构造 3×3 格并 LLL。 - 看 LLL 第一行范数:小于阈值记为 bit 0,否则 bit 1(具体 0/1 方向按题目对应关系标定)。
- 收集约 20000 个 bit,用
gf2bv.crypto.mt.MT19937建线性系统解出 624 个状态字。 - 克隆 RNG,按题目顺序取
getrandbits(256),SHA256(str(...))得到 AES key。 - AES-ECB 解密密文,得到 flag。
PoC
from sage.all import *
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
q, n = 1342261, 1031
PR = PolynomialRing(GF(q), "x")
x = PR.gen()
BITS = []
for _ in range(20000):
h1, h2 = get_hints() # 服务端返回的两个 hint 多项式
h1_ = GF(q)(h1 % (x + 1))
h2_ = GF(q)(h2 % (x + 1))
L = Matrix(ZZ, [[1, h1_, h2_], [0, q, 0], [0, 0, q]]).LLL()
BITS.append(0 if L[0].norm() < 100 else 1)
# MT19937 状态恢复:每个 bit 一条 GF(2) 方程
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = [rng.getrandbits(1) ^ b for b in BITS] + [mt[0] ^ 0]
sol = lin.solve_one(zeros)
rng = MT19937(sol)
key = SHA256.new(str(rng.getrandbits(256)).encode()).digest()
print(AES.new(key, AES.MODE_ECB).decrypt(enc))
说明:get_hints 与 enc 为题目接口/附件,LLL 的 0/1 方向需按实际返回标定;未在本机复跑原题服务。
变体与关联
- 其他因子投影:若
x^n+1有其他小次数因子(如x^2+1),可降到二维/四维格,判别信号更强。 - NTRU 参数:
q、n、系数分布变化会改变阈值;阈值应先用已知样本标定。 - MT19937 相关恢复:完整输出用 untemper,截断输出用线性系统;见 [[ctf-crypto-mt19937-bitstream-chinese-alignment-state-recovery]]、[[ctf-crypto-mt19937-truncated-output-gf2-linear-recovery]]。
- LWE/NTRU 格攻击:同属“把高维小秘密投影到低维后用 LLL 找短向量”的思路。
检测与防御
- 不要用 MT19937 生成密钥;使用 CSPRNG,并对随机数输出做密码学哈希。
- NTRU 类协议的采样应避免暴露大量“真/假样本”标签;对查询次数做限制。
- 检测:服务端每轮返回两个 hint 且可用公开因子区分,通常意味着可被投影降维攻击。