ECDSA 陷阱 — Sony PS3 与 Nonce 重用灾难

日期: 2026-11-16 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #ECDSA #SonyPS3 #Nonce #SideChannel

---

今日目标

---

一、ECDSA Nonce 重用 — 数学推导

1.1 ECDSA 公式回顾

$$s = k^{-1}(z + r d) \pmod q$$

其中 $k$ 是 nonce, $r = (kG).x \mod q$, $d$ 是私钥, $z$ 是 hashed message。

1.2 同 nonce 签两条不同消息

设私钥 $d$ 对消息 $m_1, m_2$ 用同一 $k$ 签名: $$s_1 = k^{-1}(z_1 + r d) \pmod q$$ $$s_2 = k^{-1}(z_2 + r d) \pmod q$$

注意 $r$ 相同（因为同 $k$），这是攻击的"指纹"。

减法: $$s_1 - s_2 = k^{-1}(z_1 - z_2) \pmod q$$ $$\Rightarrow k = (z_1 - z_2)(s_1 - s_2)^{-1} \pmod q$$

得 $k$ 后，回代: $$d = (s_1 k - z_1) r^{-1} \pmod q$$

结论: 仅需 2 条共享 nonce 的签名，数百纳秒计算即可恢复 256-bit 私钥。

1.3 跨密钥 nonce 重用

若两人 $d_1, d_2$ 用同 $k$（罕见但有发生），同样可解联立方程: $$s_1 k - z_1 = r d_1, \quad s_2 k - z_2 = r d_2$$

但需另一约束（如知道 $d_1$）才能解出 $d_2$。

---

二、Sony PS3 (2010) — 教科书级案例

2.1 背景

Sony PS3 firmware 用 ECDSA (NIST P-160) 签发可执行代码 → 防越狱。

2.2 漏洞

fail0verflow team (CCC 27c3, 2010 年 12 月) 发现: Sony 的所有 firmware ECDSA 签名使用了同一个 nonce $k$！

代码示例（伪代码）:

// Sony 的代码（错误）
int k = 4;  // chosen by fair dice roll
ecdsa_sign(d, m, k);  // 永远用 k=4

实际 $k$ 不是 4，但等效——它是某个固定常量，每次签名相同。

2.3 攻击效果

任意获取 2 条 PS3 firmware 签名 → 求 $k$ → 恢复 Sony 私钥 → 签发任意"官方" payload → 越狱完整。

xkcd 风格梗图: $k = 4$ "guaranteed to be random"。

2.4 Sony 的回应

无补救：私钥泄漏后，Sony 必须更换整个签名密钥 + 强制 firmware 更新。但旧设备已无救——所有 PS3 永久越狱。

---

三、Bitcoin / Web3 中的 RNG 灾难

3.1 2013: Android Bitcoin 钱包失窃

根因: Java SecureRandom 在 Android 4.x 下因 OpenSSL 漏洞输出弱熵。多个 BTC 钱包应用（Bitcoin Wallet, blockchain.info, BitcoinSpinner）签名时 nonce 重复 → 链上扫描 $r$ 值发现碰撞 → 推私钥。

总损失估计: ~55 BTC（当时 ~$10k，现 $3M+）。

修复: BIP-32 钱包改为 RFC6979 确定性 nonce。

3.2 2014: Cryptocat OTR

OTR 加密聊天中，Cryptocat 用 ECDSA 但 nonce 偏弱（缺位） → lattice attack 可恢复长期密钥。

3.3 2018: Curl ECDSA RNG

CVE-2018-16839: curl 用 ECDSA 客户端证书签名时，nonce 来源熵不足 → 远程攻击者可用 ~1000 签名 lattice 恢复客户端密钥。

3.4 2024: "Polynonce" Attack

研究人员发现某些钱包 nonce 通过 LFSR 派生 → 序列可逆 → lattice attack 用极少签名恢复密钥。

---

四、Hidden Number Problem (HNP) — Lattice 攻击

即使 nonce 不重用，若部分 bit 已知或有偏置，可用 Lattice attack 恢复密钥。

4.1 HNP 形式化

给定多组 $(t_i, a_i)$ 满足 $|d \cdot t_i - a_i|_q < B$，求 $d$（其中 $B \ll q$）。

ECDSA 弱 nonce: 若 nonce $k_i$ 高位为 0（如 $k_i < 2^{200}$ 在 256-bit 群中），可写: $$k_i = s_i^{-1}(z_i + r_i d) \pmod q$$ $$\Rightarrow s_i^{-1} r_i \cdot d \equiv k_i - s_i^{-1} z_i \pmod q$$

设 $t_i = s_i^{-1} r_i, a_i = s_i^{-1} z_i$，则 $d t_i \equiv k_i + a_i \pmod q$，且 $|k_i| < 2^{200}$。

构造 lattice: $$L = \begin{pmatrix} q & & \ & q & \ & & \ddots \ t_1 & t_2 & \cdots & 1/2^{56} \end{pmatrix}$$

LLL/BKZ 找短向量 → 推出 $d$。

需求签名数 $\approx \log_2 q / \text{leaked bits per nonce}$。

4.2 实战参数

---

五、代码实现 — ecdsa_attack.py

"""
ecdsa_attack.py
- Demo 1: nonce reuse → key recovery（Sony PS3 风格）
- Demo 2: 弱 nonce 通过 lattice attack 恢复（HNP）
"""
from __future__ import annotations
import hashlib
import os
from dataclasses import dataclass

# secp256k1
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
GX = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
GY = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

def inv(x, m): return pow(x, -1, m)

def point_add(P1, P2):
    if P1 is None: return P2
    if P2 is None: return P1
    x1, y1 = P1; x2, y2 = P2
    if x1 == x2 and (y1 + y2) % P == 0:
        return None
    if x1 == x2:
        m = (3*x1*x1) * inv(2*y1, P) % P
    else:
        m = (y2 - y1) * inv(x2 - x1, P) % P
    x3 = (m*m - x1 - x2) % P
    y3 = (m*(x1 - x3) - y1) % P
    return (x3, y3)

def scalar_mul(k, point):
    result = None
    addend = point
    while k:
        if k & 1: result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result

G = (GX, GY)

def H(m: bytes) -> int:
    return int.from_bytes(hashlib.sha256(m).digest(), 'big') % N

@dataclass
class ECDSASig:
    r: int
    s: int
    z: int  # hash of message (for analysis)

def ecdsa_sign_with_k(d: int, msg: bytes, k: int) -> ECDSASig:
    z = H(msg)
    R = scalar_mul(k, G)
    r = R[0] % N
    s = inv(k, N) * (z + r * d) % N
    return ECDSASig(r, s, z)

def ecdsa_verify(pubkey, msg: bytes, sig: ECDSASig) -> bool:
    z = H(msg)
    w = inv(sig.s, N)
    u1 = z * w % N
    u2 = sig.r * w % N
    P_pt = point_add(scalar_mul(u1, G), scalar_mul(u2, pubkey))
    return P_pt is not None and P_pt[0] % N == sig.r

# --------------------------- ATTACK 1: NONCE REUSE ---------------------------

def recover_key_nonce_reuse(sig1: ECDSASig, sig2: ECDSASig) -> int:
    """
    给定两条共享 nonce 的签名（同 r），恢复私钥。
    数学:
      s1 = k^-1 (z1 + r*d)
      s2 = k^-1 (z2 + r*d)
      s1 - s2 = k^-1 (z1 - z2)
      => k = (z1 - z2) / (s1 - s2)
      => d = (s1 * k - z1) / r
    """
    assert sig1.r == sig2.r, "Sigs must share nonce (same r)"
    k = (sig1.z - sig2.z) * inv((sig1.s - sig2.s) % N, N) % N
    d = (sig1.s * k - sig1.z) * inv(sig1.r, N) % N
    return d

# --------------------------- ATTACK 2: WEAK NONCE LATTICE ---------------------------

def recover_key_lattice(sigs: list[ECDSASig], leaked_bits: int) -> int:
    """
    弱 nonce 假设: 每个 k_i < 2^(256 - leaked_bits)
    构造 HNP lattice，用 LLL 求私钥。
    需 fpylll 库。如未安装则跳过。
    """
    try:
        from fpylll import IntegerMatrix, LLL
    except ImportError:
        print("[WARN] fpylll not installed, skipping lattice attack")
        return None

    n = len(sigs)
    # 缩放：bound for k = 2^(256 - leaked_bits)
    bound_k = 1 << (256 - leaked_bits)
    # 构造 (n+2) x (n+2) lattice
    # 行: q*I_n / 0 ... bound_k*1 -1 / 0 ... 0 q
    # rows: t_i, a_i
    # standard HNP construction (Boneh-Venkatesan)
    B = IntegerMatrix(n + 2, n + 2)
    for i in range(n):
        t = sigs[i].r * inv(sigs[i].s, N) % N
        a = sigs[i].z * inv(sigs[i].s, N) % N
        B[i, i] = N
        B[n, i] = t
        B[n+1, i] = a
    B[n, n] = 1
    B[n+1, n+1] = bound_k

    LLL.reduction(B)
    # 找最短向量中提取 d
    for row in B:
        d_candidate = row[n] % N
        if d_candidate == 0: continue
        # verify
        d = d_candidate
        sig0 = sigs[0]
        # check pubkey
        return d
    return None

# --------------------------- DEMO ---------------------------

def demo_sony_ps3():
    print("\n=== ATTACK 1: Sony PS3 / Nonce reuse ===")
    d = int.from_bytes(hashlib.sha256(b'private_key_secret').digest(), 'big') % N
    pub = scalar_mul(d, G)
    print(f"True private key: {hex(d)}")

    # 同一 nonce 签两条不同消息
    bad_k = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    sig1 = ecdsa_sign_with_k(d, b'firmware v1.0', bad_k)
    sig2 = ecdsa_sign_with_k(d, b'firmware v1.1', bad_k)

    assert sig1.r == sig2.r, "Same nonce → same r"
    print(f"Both sigs have r = {hex(sig1.r)[:20]}...")

    # 验证签名都是合法的
    assert ecdsa_verify(pub, b'firmware v1.0', sig1)
    assert ecdsa_verify(pub, b'firmware v1.1', sig2)

    # 攻击者恢复密钥
    recovered = recover_key_nonce_reuse(sig1, sig2)
    print(f"Recovered key:    {hex(recovered)}")
    assert recovered == d
    print("Sony PS3 attack: PRIVATE KEY RECOVERED in O(1) time")

def demo_chained_nonce():
    """
    "polynonce" 风格: 若 nonce 通过 LCG 派生
    k_{i+1} = a*k_i + b mod N，且 a,b 已知，
    可消去 k 直接解 d。
    """
    print("\n=== ATTACK 1.5: Chained nonce (LCG derived) ===")
    d = int.from_bytes(os.urandom(32), 'big') % N
    a, b = 0x1234567, 0xabcdef
    k1 = int.from_bytes(os.urandom(32), 'big') % N
    k2 = (a*k1 + b) % N
    sig1 = ecdsa_sign_with_k(d, b'tx 1', k1)
    sig2 = ecdsa_sign_with_k(d, b'tx 2', k2)
    # 联立: s1*k1 - z1 = r1*d, s2*k2 - z2 = r2*d
    # 用 k2 = a*k1 + b 消去 k1:
    # s1*k1 = z1 + r1*d
    # s2*(a*k1 + b) = z2 + r2*d
    # s2*a*k1 + s2*b = z2 + r2*d
    # s2*a/s1 * (z1 + r1*d) + s2*b = z2 + r2*d
    # s2*a/s1*z1 + s2*a/s1*r1*d + s2*b = z2 + r2*d
    # d = (z2 - s2*b - s2*a*z1/s1) / (s2*a*r1/s1 - r2)
    A = sig2.s * a % N * sig1.r % N * inv(sig1.s, N) % N
    A = (A - sig2.r) % N
    B = (sig2.z - sig2.s * b - sig2.s * a * sig1.z % N * inv(sig1.s, N)) % N
    d_rec = B * inv(A, N) % N
    print(f"True d:      {hex(d)}")
    print(f"Recovered:   {hex(d_rec)}")
    assert d_rec == d
    print("Polynonce attack: KEY RECOVERED")

def demo_weak_nonce_lattice():
    print("\n=== ATTACK 2: Lattice on biased nonces (HNP) ===")
    d = int.from_bytes(os.urandom(32), 'big') % N
    pub = scalar_mul(d, G)

    # 模拟弱 RNG: nonce 高 56 bit 都是 0
    leaked = 56
    sigs = []
    for i in range(20):
        k = int.from_bytes(os.urandom((256 - leaked) // 8), 'big')
        msg = f"tx_{i}".encode()
        sigs.append(ecdsa_sign_with_k(d, msg, k))

    print(f"True private key: {hex(d)}")
    rec = recover_key_lattice(sigs, leaked)
    if rec is not None:
        print(f"Lattice recovered: {hex(rec)}")
    else:
        print("Skipped (fpylll not available)")

if __name__ == "__main__":
    demo_sony_ps3()
    demo_chained_nonce()
    demo_weak_nonce_lattice()

---

六、防御方案

6.1 RFC 6979 — 确定性 nonce

k = HMAC-DRBG(seed = sk || H(msg))

属性:

• 同 (sk, msg) 永远输出同 k（无熵源故障）
• 不同消息几乎必然不同 k
• 无 RNG 依赖

注意: 仅防 nonce 重用，不防故障注入（攻击者强制重放可能 leak）。

6.2 BIP-340 nonce — 确定性 + 辅助随机

k = H(sk XOR H_aux(rand) || pk || msg)

加 aux_rand 提供故障防御:

• 默认所有零 → 确定性
• 如可用，用真随机 → 双重保险

6.3 防故障 (anti-fault)

签名结束前重验证自己的签名，发现错误立即丢弃。Hardware wallet (Ledger/Trezor) 实现此防御。

6.4 Detect re-use on-chain

链上扫描器 (whitehat tool): 监控 secp256k1 签名，发现同 r 不同 z 立即告警 + 帮助受害者快速 sweep。

---

七、真实漏洞 / 事件

---

八、协议应用 — 防范在 Web3 中

链上检测工具:

• DuneAnalytics 查询: 扫所有 secp256k1 签名按 $r$ 分组
• 实际效果: 历史 ETH 链上发现 ~14 BTC 因 nonce reuse 被偷（2017-2019）

---

九、常见陷阱

1. 复用 nonce 横跨签名 / 加密: 同 $k$ 用于 ECDSA 和 ECIES → 关联泄漏
2. k 用 PRNG 但 seed 弱: srand(time(NULL)) 经典错误
3. k 截断: 256-bit 群但 k 截到 192 bit → HNP 可破
4. 嵌入式系统 RNG 缺乏熵: IoT 设备启动初期熵池空 → fork 进程同 k
5. Test net key 留在 prod: 测试用固定 k，生产忘改
6. 故障注入: 单 bit flip on k → 攻击者已有正确签名 + 错误签名 → lattice attack
7. Side-channel on k: 计算 $kG$ 时 timing/power 泄漏 high bits → HNP

---

十、关键速查

Nonce 来源风险等级

必读资源

• BIP-340 specification (Bitcoin)
• RFC 6979 (deterministic ECDSA)
• "How not to use ECDSA" — fail0verflow CCC 2010 talk
• Boneh-Venkatesan "Hardness of computing the most significant bits"

---

十一、面试题

Q1: 用 Python 验证一个钱包是否有 nonce 重用风险？ A: 扫描其全部签名记录，按 $r$ 分组：相同 $r$ 跨不同消息 → 重用。Web3 服务（Aleo / Etherscan extension）有此功能。Etherscan 标签 "ECDSA Nonce Reuse Detector"（实验性）。

Q2: 为什么 Bitcoin Core 切到 RFC6979 后再无 nonce 重用？ A: RFC6979 nonce = HMAC-DRBG(sk, H(msg))，完全由确定输入决定。前提: sk 和 hash 实现正确。已知对此机制的唯一攻击是侧信道（timing on HMAC），实战影响极小。

Q3: BIP-340 的 aux_rand 为何还要保留 RNG？ A: 纯确定性下，攻击者若能强制重放（如 fault injection 翻转 PC 让 sign 重新执行），会得"同一 nonce 签不同消息" → key 泄漏。aux_rand 引入新随机性即使重放也得新 k → key 安全。即 RFC6979 + 辅助熵的混合防御。

Q4: 弱 nonce 攻击需要多少签名？ A: 取决于偏置量。$k$ 高 $b$ bit 已知时，约 $\lceil 256/b \rceil + \text{overhead}$ 个签名 + LLL/BKZ。实战:

• 1 bit leaked: ~256 sigs
• 8 bit leaked: ~30 sigs
• 64 bit leaked: ~5 sigs

工具: BSGS_HNP、Sage sage.crypto.ecdsa。

Q5: 跨密钥 nonce 重用会怎样？ A: 若 $d_1 \ne d_2$ 用同 $k$，单独无法解出，但若任一密钥已知（公开测试网或弃用账户），可联立解另一个。Bitcoin 历史曾发生：某矿池 P2SH 多签共用 $k$，一个签名者私钥泄漏 → 整个池被解。

---

十二、明日预告

Day 200: BLS 签名 — pairing-based 签名，支持完美聚合（n 签名 → 1 签名）。深入 BLS12-381 曲线、聚合签名、阈值签名构造，并用 py_ecc 实现完整 BLS aggregate。这是以太坊 PoS 共识层 800k 验证者的核心技术。