ECDSA 时间侧信道:两种 k 位长 + HNP 格 CVP 恢复私钥并伪造 token
crypto/ecc · verified
一句话结论
服务端签名时以两种方式生成 k(256 位安全值,或 240–256 位的短值),短 k 的签名耗时明显更短;攻击者收集大量签名并按耗时筛选短 k 样本,把 k_i = A_i + d*T_i mod q 视为隐藏数问题,构造 diag(q) + T 行 + B/q 的格并解 CVP,即可恢复私钥 d,再伪造 admin token。
原理
- ECDSA:
s_i = k_i^{-1}(z + r_i*d) mod q,其中z=Hash(msg)、q为曲线阶。 - 若服务端有两种
k生成路径:256 位随机(安全)与 240–256 位随机(较短),后者的标量乘法/签名的耗时通常更短;时间侧信道可把短k样本筛出来。 - 对短
k样本,k_i < B = 2^240(或更小的界)。由签名式: k_i = z*s_i^{-1} + d*r_i*s_i^{-1} mod q- 记
A_i = z*s_i^{-1} mod q、T_i = r_i*s_i^{-1} mod q,则k_i = A_i + d*T_i mod q,且0 <= k_i < B。 - 构造
(m+1)x(m+1)格:前m行diag(q),最后一行前m列为T_i,最后一列为B/q。 - 目标向量
u = (A_1,...,A_m,0);格点v = (y_i*q - d*T_i, -d*B/q);v - u的前m位为k_i(短),最后一位为d*B/q。用 LLL/BKZ 约减后做 CVP/Babai,取最近向量。 - 从
v[m]反推d = round(±v[m]*q/B) mod q,验证所有k_i = (A_i + d*T_i) mod q都< B;噪声/误差可能导致一次失败,可多组样本重试。
触发条件
- 服务端签名接口使用两种
k位长/两种随机数路径,且短k的耗时统计上明显更低。 - 攻击者能获取大量
(r,s)与足够精确的耗时;能重算消息哈希z。 - 短
k的上界B已知(如 2^240),且样本数m足够(案例 24 个/组,多组重试)。 - 有 LLL/BKZ/CVP 工具(Sage)。
利用步骤
- 调用签名接口,记录每条的
(r,s)、耗时cost与消息哈希z。 - 按耗时排序,取最短的一批样本(案例每组 24 个,尝试多组);必要时用统计/聚类区分两种分布。
- 计算
A_i = z*s_i^{-1} mod q、T_i = r_i*s_i^{-1} mod q。 - 构造格
diag(q)+T行 +B/q,做 LLL/BKZ。 - 以
u=(A_i,0)为目标做 CVP/Babai,得到v;从v[m]反推d候选(正负号都试)。 - 验证
k_i=(A_i+d*T_i) mod q全部< B;成功后用d伪造 admin token/签名。 - 若失败,换样本子集/增加样本/调整
B,重复。
PoC
# Sage
q = Integer(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
B = Integer(2) ** 240
z = Integer(int.from_bytes(hashlib.sha256(MSG).digest(), "big"))
samples = [(r1, s1), (r2, s2), ...] # 按耗时筛出的短 k 样本
T, A = [], []
for r, s in samples:
sinv = inverse_mod(Integer(s), q)
T.append(QQ((Integer(r) * sinv) % q))
A.append(QQ((z * sinv) % q))
m = len(T)
M = Matrix(QQ, m + 1, m + 1)
for i in range(m):
M[i, i] = q
for j in range(m):
M[m, j] = T[j]
M[m, m] = QQ(B) / QQ(q)
u = vector(QQ, A + [0])
Bred = M.LLL()
try:
Bred = Bred.BKZ(block_size=20)
except Exception:
pass
def babai_row(Bmat, target):
rows = [vector(QQ, Bmat.row(i)) for i in range(Bmat.nrows())]
Gs = Bmat.gram_schmidt()[0]
y = vector(QQ, target)
for i in reversed(range(Bmat.nrows())):
den = Gs[i].dot_product(Gs[i])
if den == 0: continue
mu = y.dot_product(Gs[i]) / den
y -= ZZ(round(mu)) * rows[i]
return vector(QQ, target) - y
v = babai_row(Bred, u)
for sign in (1, -1):
d = ZZ(round(sign * v[m] * q / B)) % q
ks = [ZZ((A[i] + T[i] * d) % q) for i in range(m)]
if all(0 <= kk < B for kk in ks):
print("d =", int(d))
break
案例用 80 轮、每轮取 3 个最短耗时样本,最终恢复 d 并伪造 admin token 访问 /welcome。
变体与关联
- 变体:侧信道可能是功耗/电磁/缓存而非时间;同样把“短 k/部分位泄露”转成 HNP。
- 变体:短
k的位长不同(如 240/248/252)时,分别设B并尝试。 - 变体:噪声导致 CVP 失败时,增加样本、剔除异常值、用 BKZ 更强约减或多组投票。
- 关联:[[crypto-ecc-ecdsa-partial-nonce-leak-lattice]](部分 nonce 格攻击)、[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]](完全复用)、[[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]](CVP 格方法)。
检测与防御
- 防御:所有
k必须使用同一安全位长与 CSPRNG/RFC6979,禁止“短 k”路径;签名实现应常量时间。 - 防御:对签名接口做速率限制,避免攻击者收集大量样本;使用 HSM/远程签名服务隔离时序。
- 检测:签名耗时分布出现双峰/短尾;同一接口大量签名请求;异常 token 伪造尝试。
- 响应:发现侧信道后轮换私钥/证书,统一 nonce 生成路径,审计历史签名是否可恢复。