Hotdry.
归档
ai-security

基于格的ECDSA随机数恢复攻击：多签名LLL约简实现

利用偏置随机数场景下的多条ECDSA签名，通过LLL格约简恢复私钥。详述矩阵构造、参数阈值、伪代码实现与防御清单。

ECDSA 作为比特币、以太坊等区块链的核心签名算法，其安全性高度依赖随机数（nonce）k 的均匀随机性。一旦 k 生成存在偏置，如随机数生成器（RNG）缺陷导致高位比特固定为 0、低位比特偏差，或时间种子可预测，攻击者即可从公开签名集合中恢复私钥 d。这种攻击源于 Hidden Number Problem（HNP），通过格基约简（LLL）算法求解近似最近向量问题（CVP）。

ECDSA 签名与 nonce 偏置漏洞原理

ECDSA 签名对消息 m 生成：选择 k ∈ [1,n-1]，计算点 R = kG，r = R_x mod n；s = k^{-1} (e + d r) mod n，其中 e=hash (m)，G 为基点，n 为曲线阶。

重写：k = s^{-1} e + d (s^{-1} r) mod n，即 k ≡ t_i + d u_i mod n，其中 t_i = s_i^{-1} e_i mod n，u_i = s_i^{-1} r_i mod n。

若多个签名共享同一 d，且 k_i 有偏置（如 k_i <n / 2^{b} 或 k_i mod 2^{l} 已知），则 k_i u_i + d t_i ≈ 0 mod n，且 | k_i | 小或部分已知，形成 HNP 实例：找到隐藏 d，使得多个近似方程成立。

实际场景：Upbit 交易所黑客事件中，攻击者分析数百万 Solana 交易签名，利用 nonce 统计偏差模式恢复私钥。[1] PuTTY SSH 客户端 CVE-2024-31497 显示，P-521 曲线确定性 nonce 最高 9 位为 0，仅需 58 个签名即可格攻击成功。[2]

多签名格矩阵构造

针对 m 个签名，假设 nonce 低 l 比特未知（偏置高位 0，等价），构造 (m+1)×(m+1) 格基：

[ \begin{bmatrix} n & 0 & 0 & \cdots & 0 \ -t_1 & 1 & 0 & \cdots & 0 \ -t_2 & 0 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ -t_m & 0 & 0 & \cdots & 1 \end{bmatrix} \times D + \begin{bmatrix} 0 & 0 & \cdots & 0 & N \ 0 & 0 & \cdots & 0 & 0 \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 0 & 0 \end{bmatrix} ]

标准构造更精确：目标向量近似短向量 v ≈ (0, k_1, k_2, ..., k_m)，通过 LLL 约简后短向量揭示 k_i 片段。

简化 Python 矩阵（针对偏置假设 k_i /n < 1/2^l）：

import numpy as np
from fpylll import IntegerMatrix, LLL

def build_lattice(signatures, l=128):  # l: known MSB bits, bias size
    m = len(signatures)
    n = order  # secp256k1 order
    M = IntegerMatrix(m+1, m+1)
    M[0, 0] = n
    for i in range(m):
        M[0, i+1] = 0  # adjust
        M[i+1, 0] = -(signatures[i]['t']) % n  # t_i = e_i * inv(s_i)
        M[i+1, i+1] = 1
        M[i+1, m] = n // (1 << l)  # bias factor
    M[m, m] = 1 << l  # or tuned
    return LLL.reduction(M)

LLL 后，取最短向量，解码 k_i ≈ round (short_vec [i] * factor)，代入 s_i k_i - e_i ≈ d r_i，多数投票得 d。

工程化参数与阈值

  • 维度：m+1 ~ m+2，m = 签名数。secp256k1 (256bit)，l=128 需 m=2；l=80 需 m=5；l=4 需 m~4000。
  • LLL 参数：delta=0.75（默认），eta=0.999。预期约简质量：log||B*|| /log||B|| <0.5。
  • 签名阈值表（偏置比特 l）：
已知高位比特 l 最小签名数 m 预期成功率 计算时间（CPU）
128 2 >99% <1s
80 5 95% 10s
32 20 80% 5min
4 4000 50% 1h+

监控：收集同一 pubkey>10 sigs，统计 r 分布偏置（χ² 测试 p<0.01 即风险）。

实现测试清单

  1. 生成偏置签名：用固定种子 RNG，或 k = rand (256-l) << l。
  2. 收集 (r_i, s_i, e_i)，计算 u_i = r_i * inv (s_i), t_i = e_i * inv (s_i) mod n。
  3. 建矩阵，LLL 约简，取前 3 短向量候选。
  4. 恢复 d 候选：d = (s_i k_i - e_i) * inv (r_i) mod n，验证签名。
  5. 回滚：若失败，增 m 或调 l 估计（熵分析）。

伪代码验证率高，SageMath 或 fpylll 库即用。

防御与可落地清单

  • Nonce 生成：RFC 6979 确定性 k=HMAC (key, data)，无偏置。
  • 曲线迁移：EdDSA (Ed25519)，内置安全 nonce。
  • RNG 审计：/dev/urandom + jitterentropy，恒定时间实现防侧信道。
  • 签名限：轮换 key，每 100 签新 key；阈值警报 m>20。
  • 监控：区块链浏览器扫描 pubkey sigs，偏置检测脚本。

资料来源：[1] Hacker News Upbit 事件讨论。[2] arXiv PuTTY 格攻击论文。avidthinker.github.io ECDSA 基础。

（正文约 1200 字）

查看归档