Hidden Number Problem(HNP)MSB 泄露:pI 与 t 行构造格,Babai 最近平面恢复 α
ctf/crypto · verified
一句话结论
当神谕对任意 t 返回 MSB_k(α·t mod p)(即知道 αt mod p 落在长度 p/2^k 的区间内)时,可写成 αt_i ≡ u_i + e_i (mod p),|e_i|≤p/2^{k+1};用 pI_n 与最后一行 (t_1,…,t_n, 1/2^{l+1}) 构造格,目标点 u=(u_1,…,u_n,0),用 Babai 最近平面找到最近格向量 v=(αt_i mod p, α/2^{l+1}),最后一维即恢复 α。
原理
- MSB 泄露转成近似线性方程:
u_i = MSB_k(α t_i mod p)意味着α t_i mod p与u_i的差e_i很小(|e_i| ≤ p/2^{k+1})。于是α t_i ≡ u_i + e_i (mod p),未知量是α,误差是e_i。 - 格构造:取
n组样本,构造(n+1)×(n+1)格,基为text [ p 0 ... 0 0 0 p ... 0 0 ... ... ... ... ... 0 0 ... p 0 t_1 t_2 ... t_n 1/2^{l+1} ]其中l是泄露的高位数(与k对应,缩放因子1/2^{l+1}用于把最后一维压小)。 - 目标向量:
u=(u_1,…,u_n,0)。格中存在向量v=(αt_1 mod p,…,αt_n mod p, α/2^{l+1}),它与u的差为(e_1,…,e_n, α/2^{l+1}),各分量都很小,因此v是格中离u最近的向量(CVP)。 - Babai 最近平面:对格基做 LLL 约减后,用 Babai 的 nearest plane 算法求
u的近似最近向量;最后一维v_{n+1}=α/2^{l+1},乘以2^{l+1}即得α。 - 参数条件:
l ≈ log^{1/2}(p)量级的泄露位数、足够多的样本、误差界足够小;样本太少或噪声太大时 CVP 不唯一/最近向量错误。 - 为什么成立:HNP 把“高位已知、低位未知”的乘法关系转成“格中带小误差的最近向量”;LLL + Babai 在维数/误差合适时能有效求解。
- CVP→SVP:也可把目标点嵌入格中(Kannan embedding)转成 SVP,用 LLL/BKZ 求短向量;Babai 是最直接的 CVP 近似算法。
触发条件
- 有 MSB/高位泄露神谕:已知
α t_i mod p的高k位,误差|e_i| ≤ p/2^{k+1}。 - 样本数
n足够,泄露位数l与p的关系满足l ≈ log^{1/2}(p)或更宽松;误差足够小。 - 能运行 Sage/LLL;需要构造
pI与t行、选择缩放因子1/2^{l+1}。 - 常见于 ECDSA nonce 高位泄露、截断 LCG、乘法掩码/侧信道等场景。
利用步骤
- 收集
(t_i, u_i)样本,估计泄露位数l/误差界;确认α t_i ≡ u_i + e_i (mod p)。 - 构造
n+1维格:前n行p在对角,最后一行前n列为t_i、最后一列为1/2^{l+1}。 - 对格基做 LLL 约减;用 Babai nearest plane 求目标
u=(u_1,…,u_n,0)的最近向量。 - 取最近向量最后一维
v_last,α = v_last * 2^{l+1}(或按缩放因子调整);验证α t_i mod p的高位与u_i一致。 - 若失败,增加样本数、调整
l/缩放因子、改用 BKZ 或 Kannan embedding。
PoC
# Sage
n = len(t)
l = ... # 泄露位数
M = matrix(ZZ, n + 1, n + 1)
for i in range(n):
M[i, i] = p
for j in range(n):
M[n, j] = t[j]
M[n, n] = 1 / (2 ** (l + 1))
# LLL 约减后 Babai nearest plane
L = M.LLL()
target = vector(ZZ, list(u) + [0])
# Sage 可用 L.babai(target) 或 fpylll 的 CVP.closest_vector
v = L.babai(target)
alpha = v[-1] * (2 ** (l + 1))
print(alpha)
原文用该构造 + Babai 最近平面恢复 α;未在本库复跑。
变体与关联
- CVP→SVP:Kannan embedding 把目标点嵌入格,转成短向量问题;LLL/BKZ 求短向量。
- 泄露类型:MSB、LSB、中间位、带错误的高位;不同泄露对应不同的缩放/嵌入方式。
- 应用场景:ECDSA nonce 高位泄露(
crypto-prng-truncated-lcg-coppersmith-lattice-cvp类)、截断 LCG、乘法掩码侧信道。 - 关联卡片:[[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]](截断 LCG 的 Coppersmith/lattice)、[[ctf-crypto-coppersmith-msb-lcg-truncated-cvp]](MSB 截断 LCG 的 CVP)、[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](LLL/Kannan embedding)。
检测与防御
- 不要泄露高位:ECDSA/签名 nonce 的 MSB/LSB 不能暴露;使用 RFC 6979 确定性 nonce 或强随机。
- 参数评估:对 HNP 类场景,用格攻击脚本评估泄露位数/样本数是否足以恢复密钥;
l ≈ log^{1/2}(p)是危险阈值。 - 检测:签名/随机数接口是否存在高位截断、侧信道泄露、可重复的
t采样;对异常签名做格攻击可行性评估。