ECDH 双值高位泄露构造 HNP:sb 与 B_pri_r 各泄露 28bit,LLL 恢复 128bit 私钥后用 BSGS 补齐低 36bit
crypto/ecc · verified
一句话结论
一个类 X25519 的 ECDH 交换中 sb = B_pri_r + retbar(B_pub_R)·B_pri_w mod n;题目给出 10 组 sb 与 B_pri_r 的高 28bit(低 100bit 未知)。把两式相减消去已知部分,得到 A_i·w + h_i + l_i ≡ 0 (mod n)(A_i=retbar(B_pub_R_i)、l_i 为小于 2^100 的未知低位),以第一组为基准消元构造 HNP 格,LLL 恢复 128bit 私钥 B_pri_w 的高位(低 36bit 未知),再用 2^18 步 BSGS 补齐低 36bit;最后以 md5(long_to_bytes(w)) 为 AES-ECB 密钥解密 flag。
原理
- retbar 可公开计算:
retbar(P) = (int(P.x) mod 2^65 + 2^65) mod n,只依赖公开点B_pub_R的 x 坐标,因此每组的系数A_i = retbar(B_pub_R_i)已知。 - 泄漏关系:
sb = B_pri_r + A·B_pri_w mod n,移项得sb - B_pri_r ≡ A·w (mod n)。sb与B_pri_r各只泄露高 28bit(LS[i]=sb>>100、LR[i]=B_pri_r>>100),所以h_i = (LS[i]-LR[i])<<100是A_i·w的高位近似,误差为两者未知低位之差l_i(|l_i| < 2^100),即A_i·w ≡ h_i + l_i (mod n)。 - 消元构造 HNP:以第 0 组为基准,
l_i = (A_i·A_0^{-1})·l_0 + (A_i·A_0^{-1}·h_0 - h_i) (mod n)。记A'_i = A_i A_0^{-1}、B'_i = A'_i h_0 - h_i,则l_i = A'_i l_0 + B'_i (mod n),其中l_0是小于2^100的小未知数。 - 格构造:取
(m+1)×(m+1)格(m为样本数,本例 10;模数为q=n),前m-1行是(-q, A'_i, B'_i),倒数第二行放(0,...,0,1,0),最后一行放(0,...,0,0,2^128)。短向量对应l_0的组合;LLL 后找最后一维为2^128的向量,其倒数第二维b0给出l_0的近似,w ≈ (h_0 + b0)·A_0^{-1} mod n。 - 为何只到高位:格中误差项
l_i < 2^100、目标w约 128bit,10 组泄漏共 280bit 信息(28×10 > 128),LLL 能恢复w但低 36bit 仍不确定;把结果x0截断为x0 >> 36 << 36。 - BSGS 补齐:剩下的搜索空间为
w = x0 + r、0 ≤ r < 2^36。以G做 baby-step 表(2^18个点),再以B_pub_W - x0·G为起点、每次减2^18·G做 giant-step(2^18次),命中即得r = i·2^18 + j,总复杂度约2^19次点运算。 - 密钥派生:
key = md5(long_to_bytes(w)).hexdigest().encode(),AES-ECB 解密题目密文得 flag。
触发条件
- ECDH/自定义密钥交换中,攻击者能获得同一私钥参与的两个线性组合的高位(本例
sb与B_pri_r各高 28bit),且低位范围有界(100bit)。 - 样本数足够:泄漏总位数明显超过私钥位长(本例 28×10=280 > 128)。
- 系数
retbar(B_pub_R)可由公开点计算;模数n为素数(点阶)。 - 私钥剩余未知位数可承受 BSGS(本例 36bit,约 2^18+2^18 步)。
利用步骤
- 解析
B_pub_W、LS、LR、BR,计算每组的A_i = retbar(BR[i])与h_i = (LS[i]-LR[i])<<100。 - 以第 0 组为基准,对
i=1..m-1计算A'_i = A_i·A_0^{-1} mod n、B'_i = A'_i·h_0 - h_i mod n。 - 构造
(m+1)×(m+1)格:对角线-n、倒数第二列A'_i、最后一列B'_i,最后两行分别为1和2^128;LLL 约减。 - 遍历约减基,取最后一维等于
2^128的向量,b0=|倒数第二维|,x0=(h_0+b0)·A_0^{-1} mod n,并截断低 36bit。 - BSGS:枚举
0..2^18的jG建表,再对h=B_pub_W - x0·G每次减2^18·G查表,得到w。 - 用
w派生 MD5 密钥,AES-ECB 解密。
PoC
# Sage
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import hashlib
p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G = E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n = G.order()
def retbar(P):
return (int(P[0]) % (2**65) + 2**65) % n
B_pub_W = E(56142839234500040174315077324489019612,
143186177525574678948140963663687495447)
LS = [12160779, 70634852, 136488679, 93279448, 51769705, 99408367, 94011238, 46255543, 136054320, 126842658]
LR = [117789932, 85602320, 136131278, 85538539, 33115646, 15821127, 122073977, 40205177, 40509142, 121833940]
BR = [(43128875586771925869851532015581155657, 108714366549720544283054523544596695631),
# ... 其余 9 组
]
q = n
A = [retbar(BR[i]) for i in range(len(LS))]
h = [((LS[i] << 100) - (LR[i] << 100)) for i in range(len(LS))]
D, Ee = [], []
for i in range(len(A) - 1):
D.append((inverse(A[0], q) * (A[i+1] * h[0] - A[0] * h[i+1])) % q)
Ee.append((inverse(A[0], q) * A[i+1]) % q)
m = len(A)
L = Matrix(ZZ, m + 1, m + 1)
for i in range(m - 1):
L[i, i] = -q
L[-2, i] = Ee[i]
L[-1, i] = D[i]
L[-2, -2] = 1
L[-1, -1] = 2**128
M = L.LLL()
x0 = None
for row in M:
if row[-1] == 2**128:
b = vector(row)
x0 = ((h[0] + abs(b[-2])) * inverse(A[0], q)) % q
x0 = x0 >> 36 << 36 # 低 36bit 未知
# BSGS 补 36bit
baby = {}
tmp = 0
for i in range(2**18):
tmp += G
baby[tmp] = i + 1
target = B_pub_W - x0 * G
step = 2**18 * G
for i in range(2**18):
if target in baby:
w = x0 + i * 2**18 + baby[target]
break
target -= step
key = hashlib.md5(long_to_bytes(w)).hexdigest().encode()
print(AES.new(key, AES.MODE_ECB).decrypt(c))
变体与关联
- 若只泄露一个值的高位,可用 ECDSA 部分 nonce 的 HNP 直接构造;本卡的特殊点是把同一私钥的两个线性组合相减后,误差仍受控,从而得到系数不同的多组同余式。
- 样本更多或泄漏位数更多时,格维度可减小、BSGS 可省略;泄漏更少时需增大格维或改用 CVP/Babai。
- 相关:[[crypto-ecc-ecdsa-partial-nonce-leak-lattice]](ECDSA 部分 k 泄露)、[[ctf-crypto-hnp-msb-oracle-babai-nearest-plane]](HNP 通用构造)、[[crypto-ecc-ecdh-small-nonce-brute-shared-point-key]](小 nonce 暴力)。
检测与防御
- 不要把私钥参与值的任何高位写入日志、响应或侧信道;泄漏高位会显著降低私钥熵。
- ECDH 实现使用常数时间点乘与固定格式输出,避免高位/低位相关泄露。
- 若必须公开统计值,应加噪声或只公开不可逆的哈希,而不是原始点坐标/组合值的高位。