区块链安全

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

题目分析

题目很简短: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