ECDSA 可预测 nonce:由公开种子确定性派生 k 后直接恢复私钥
crypto/ecc · verified
一句话结论
如果 ECDSA 签名实现把 nonce k 用公开可推导的方式生成(例如 k = Hash(固定字符串 || 消息序号) mod n,或 k = Hash(消息)),攻击者拿到任意一条签名后就能重算出 k,再用 d = (s*k - e) * r^{-1} mod n 直接恢复私钥。
原理
- ECDSA 签名方程:
r = (k*G).x mod n,s = k^{-1}(e + d*r) mod n,其中e = Hash(msg)、d为私钥、n为基点阶、k为一次性随机数。 - k 已知即可解 d:把方程乘以
k得s*k = e + d*r,移项即d = (s*k - e) * r^{-1} mod n。不需要两条签名,也不需要r相同。 - 可预测 nonce 的成因:实现者为了“确定性签名”用公开数据派生
k,例如k(i) = Hash("bias" || i)、k = Hash(msg)、k = Hash(timestamp)、k = Hash(username)。只要派生输入可被攻击者重算,k就不再是秘密。 - 与 RFC6979 的区别:RFC6979 的确定性 nonce 是
HMAC(私钥, 消息),输入包含私钥,攻击者不知道私钥就无法重算;而只用公开种子的“确定性”只是把随机数换成了可预测值,安全性归零。 - 示例参数:NIST P-521 的阶为 521 bit,签名的
r、s各占 66 字节;若实现把签名序列化为r||s,需按 66 字节切分。哈希函数必须与签名端一致(示例用 SHA-1,私钥派生用 SHA-512),否则e计算错误会导致恢复失败。 - 为什么能验证:恢复出的
d满足d*G = Q(公钥),可用来确认参数、哈希截断与字节序是否正确。
触发条件
- 目标使用 ECDSA,且 nonce 由公开数据确定性派生(固定种子、计数器、消息本身、时间戳等),或 nonce 被直接泄露。
- 攻击者能拿到至少一条
(msg, r, s)签名与对应公钥/曲线参数。 - 知道签名端使用的哈希算法与签名序列化格式(r/s 字节长度、大小端)。
r在模n下可逆(正常签名均满足)。
利用步骤
- 收集一条签名和对应消息,确认曲线阶
n、哈希算法、r/s编码长度。 - 按实现逻辑重算 nonce:如
k = int(Hash(seed || index)) mod n。 - 计算消息摘要
e = Hash(msg)(按签名端实际哈希,必要时截断到n的位长)。 - 计算
d = ((s*k - e) * pow(r, -1, n)) % n。 - 用
d*G == Q验证;若不等,检查哈希、字节序、r/s切分和k是否取模。 - 用恢复的私钥伪造签名、解密会话或登录目标系统。
PoC
from hashlib import sha1, sha512
from ecdsa import NIST521p
n = NIST521p.order
L = 66 # P-521 的 r/s 各 66 字节
# 一条签名:msg 为原始消息,sig 为 r||s
msg = bytes.fromhex("<message hex>")
sig = bytes.fromhex("<signature hex>")
i = msg[-1] # 示例中消息为 b"message-" + bytes([i])
k = int.from_bytes(sha512(b"bias" + bytes([i])).digest(), "big") % n
r = int.from_bytes(sig[:L], "big")
s = int.from_bytes(sig[L:], "big")
e = int.from_bytes(sha1(msg).digest(), "big")
d = ((s * k - e) * pow(r, -1, n)) % n
print(hex(d))
# 验证:ecdsa.SigningKey.from_string(long_to_bytes(d, 66), curve=NIST521p).verifying_key == 公钥
变体与关联
- 变体:
k = Hash(msg)(不含私钥)时,攻击者可对任意已截获消息重算k。 - 变体:
k由时间戳/递增计数器派生时,可在小范围枚举k并验证r是否匹配。 - 变体:
k只有部分泄露时,转为 partial nonce leak / HNP 格攻击。 - 关联卡片:[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]]、[[crypto-ecc-ecdsa-partial-nonce-leak-lattice]]、[[crypto-ecc-ecdsa-time-side-channel-hnp]]、[[crypto-ecc-ecdh-small-nonce-brute-shared-point-key]]。
检测与防御
- 检测:代码审计中搜索
k = hash(...)、k = random(...)的可预测派生;检查签名是否出现重复r或可重算的k。 - 检测:签名实现是否使用固定种子、消息序号、时间戳等公开输入生成 nonce。
- 防御:使用 RFC6979(HMAC-DRBG,输入包含私钥)或操作系统 CSPRNG 生成
k;优先使用 HSM/成熟库的签名接口。 - 防御:定期校验签名实现,禁止自研 ECDSA nonce 生成逻辑。