区块链安全

利用重复r值的ECDSA签名恢复以太坊私钥

by Snowming

题目分析

题目很简短：https://capturetheether.com/challenges/accounts/account-takeover/

要求调用 authenticate() 方法的地址等于 owner，等于说给出了地址求私钥。

发现问题

在测试网区块链浏览器 ropsten.etherscan.io 上面查看此地址相关的交易，View Outgoing Txns 可以看到有这样两笔同 from 地址且同 to 地址的交易。

查询数据库①，三笔交易中有两笔的 r 值相同：

若两笔交易的 ECDSA 签名信息中 r 值相同的，则意味着这两笔交易使用了相同的随机数 k，通过这我们就能利用这两笔交易的信息来还原出私钥。

知识背景

参考：

https://xz.aliyun.com/t/6295
https://xz.aliyun.com/t/2718

破解过程

目前我们已经有两笔交易的签名值 s1 和 s2：

s1-s2 = k ^ -1（z1 + dA * r）-k ^ -1（z2+ dA * r）
= k^-1(z1-z2)
k = (z1-z2)/(s1-s2)

如果知道了 k，那么私钥 dA = (s*k-z)/r
所以目前未知的参数就是 z，是对要签名的消息取的 hash 值。

使用 nodejs 的 ethereumjs-tx 库来模拟对交易的签名过程，将前面得到的交易信息②进行 hash：

const EthereumTx = require('ethereumjs-tx').Transaction
var rawTx1 ={
  nonce: 0,
  gasPrice: '0x3b9aca00',
  gasLimit: '0x5208',
  to: '0x92b28647ae1f3264661f72fb2eb9625a89d88a31',
  value: '0x1111d67bb1bb0000',
  data: '0x',
  v: '0x29',
  r: '0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166',
  s: '0x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8'
}
var rawTx2 ={
  nonce: 1,
  gasPrice: '0x3b9aca00',
  gasLimit: '0x5208',
  to: '0x92b28647ae1f3264661f72fb2eb9625a89d88a31',
  value: '0x1922e95bca330e00',
  data: '0x',
  v: '0x29',
  r: '0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166',
  s: '0x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de'
}
const tx1 = new EthereumTx(rawTx1, { chain: 'ropsten', hardfork: 'petersburg' })
const tx2 = new EthereumTx(rawTx2, { chain: 'ropsten', hardfork: 'petersburg' })


const z1 = tx1.hash(false).toString("hex");
const z2 = tx2.hash(false).toString("hex");
console.log(z1);
console.log(z2);

这里要注意：

  1. 见 line1，新版本的 ethereumjs-tx 跟旧版本此行写法不同
  2. line 24-25 指明 chain，跟旧版本写法不同
  3. line 27-28，这个库中的 hash 函数此时要选择参数 false，因为参数为 false 时进行 hash 的对象是不加入签名信息的，也就是我们需要的 z 值，否则默认的参数为 true 得到的就是添加了签名信息的 hash 值，得到的其实就是我们的交易 hash

运行 node script.js 计算得到两个 z 值：

350f3ee8007d817fbd7349c477507f923c4682b3e69bd1df5fbb93b39beb1e04
4f6a8370a435a27724bbc163419042d71b6dcbeb61c060cc6816cda93f57860c

下面继续来计算私钥：

「目前我们已经有两笔交易的签名值 s1 和 s2：
s1-s2 = k ^ -1（z1 + dA * r）-k ^ -1（z2+ dA * r）
= k^-1(z1-z2)
k = (z1-z2)/(s1-s2)
如果知道了 k，那么私钥 dA = (s*k-z)/r」

要注意这里的计算是基于有限域Fp的：

「实数域上的椭圆曲线是连续的，并不适用于加密，考虑到加密算法的可实现性，要把椭圆曲线定义在有限域上，使之变成离散的点。
给定一个有限域Fp：
– Fp只有p（p为素数）个元素0,1,2…p-2,p-1；
– Fp的加法（a+b）法则是a+b≡c(mod p)；
– Fp的乘法（a×b）法则是a×b≡c(mod p)；
– Fp的除法（a÷b）法则是a÷b≡c(mod p)，即a×b^-1≡c(mod p)，b^-1为b的逆元；
Fp的单位元是1，零元是0；
Fp域内运算满足交换律、结合律、分配律。参考：https://xz.aliyun.com/t/6295」

这里的 p 应该是多少呢？

为了生成一个随机的32字节、64 hex字符的数作为私钥，大小范围应该介于1~0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 之间，所以这里 ECDSA-secp256k 算法的 p 为定值 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141。

所以私钥 d = (s*k-z)/r
= (s*k-z) * inverse_mod(r, p) % p

k = (z1-z2)/(s1-s2)
= (z1 – z2)*inverse_mod(s1 – s2,p)%p

所以需要定义一个计算模逆元的函数，这里参考：https://github.com/gitzhou/threshold-signature-demo/blob/master/modular_inverse.py

  • inverse_mod(a, m) 计算 a^-1 mod m

然后得出私钥：

def extended_euclid_gcd(a:int, b:int) -> list:
    """
    Returns [gcd(a, b), x, y] where ax + by = gcd(a, b)
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return [old_r, old_s, old_t]

def inverse_mod(a: int, n: int) -> int:
    """
    Assumes that a and n are co-prime, returns modular multiplicative inverse of a under n
    """
    # Find gcd using Extended Euclid's Algorithm
    gcd, x, y = extended_euclid_gcd(a, n)
    # In case x is negative, we handle it by adding extra n
    # Because we know that modular multiplicative inverse of a in range n lies in the range [0, n-1]
    if x < 0:
        x += n
    return x

def derivate_privkey(p, r, s1, s2, z1, z2):
    z = z1 - z2
    s = s1 - s2
    r_inv = inverse_mod(r, p)
    s_inv = inverse_mod(s, p)
    k = (z * s_inv) % p
    d = (r_inv * (s1 * k - z1)) % p
    return d, k

z1 = 0x4f6a8370a435a27724bbc163419042d71b6dcbeb61c060cc6816cda93f57860c
s1 = 0x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de
r = 0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166
z2 = 0x350f3ee8007d817fbd7349c477507f923c4682b3e69bd1df5fbb93b39beb1e04
s2 = 0x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

print("privatekey:%x\n k:%x" % derivate_privkey(p,r,s1,s2,z1,z2))

私钥为：614f5e36cd55ddab0947d1723693fef5456e5bee24738ba90bd33c0c6e68e269

最后将私钥导入小狐狸连接到网站即会成功通过此关：

注解

①

select  tx.from,tx.to,
		v,r,s,public_key,
		nonce
from tx 
where tx.from = '0x6B477781b0e68031109f21887e6B5afEAaEB002b' 
and upper(tx.to) = '0X92B28647AE1F3264661F72FB2EB9625A89D88A31'

②

select  nonce,
		gas_price as gasPrice,
		gas as gasLimit,
		tx.to as to,
		value,
		input as data,
		v,
		r,
		s
from tx 
where tx.from = '0x6B477781b0e68031109f21887e6B5afEAaEB002b' 
and upper(tx.to) = '0X92B28647AE1F3264661F72FB2EB9625A89D88A31'
 noncegasPricegasLimittovaluedatavrs
113643000000000210000x92b28647Ae1F3264661f72fb2eB9625A89D88A3112300000000000000000x0x2a0xf0bc97b376138de15b1657b62a6433e06f013983b6db5ee5071f60083b575b780x2071470754cd4f9557f3ce79cbf57ff6a2a420018c40a34fa95dce972b6b51c1
211000000000210000x92b28647Ae1F3264661f72fb2eB9625A89D88A3118112665806000000000x0x290x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba3876061671660x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de
301000000000210000x92b28647Ae1F3264661f72fb2eB9625A89D88A3112300000000000000000x0x290x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba3876061671660x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8

参考：

https://xz.aliyun.com/t/6295

https://xz.aliyun.com/t/2718

https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc