利用随机数冲突的ECDSA签名恢复以太坊私钥

前言

这篇文章应该算是capture the ether中Account Takeover那道题的题解，题目链接如下

https://capturetheether.com/challenges/accounts/account-takeover/

给出的意思很明确，就是要你找到指定的以太坊地址的私钥，这当时确实是把我难倒了，我们知道以太坊使用的密钥的生成算法是ECC椭圆曲线加密算法，只知道公钥你是没办法得到私钥的，同时私钥空间大小为2^256，爆破也是不可能的，跑一辈子也跑不出来，那么显然这里肯定是有其他的办法，首先肯定是从该地址下的交易入手,像下面这些

我看的时候该地址下已经有了五六十笔交易，有进有出，内容也是乱七八糟，只能说太菜了，当时确实没看出啥门道，还以为这是道社工题，也就没有再深究，搁置了下来

不过后来有师傅给我留言说这里要利用密码学知识来还原私钥，这就涉及到知识盲区了，赶紧去学习一波，该题目在reddit的讨论贴在此，传送门,我也是在这终于拿到了题目的思路

题目分析

现在我们重新来看这道题

突破口

按照在讨论贴里这一系列挑战的作者smarx大佬所言，这题是跟社工没有任何关系的，该地址下仅有一开始时的两个交易是来自于他，其他的都是玩家的交易，显然突破口就在于此，下面就是涉及的那两个交易

看起来没什么特别的，二者主要也就是发送的ether不同，data里也没有什么东西，不过没关系，我们再来看看它们两的签名信息

就如我所标注的，这两笔交易最特别的地方在于它们的签名信息中r值是相同的，如果你对ECDSA签名有够熟悉的话那么你就能意识到这里是存在大问题的，这意味着这两笔交易使用了相同的随机数k，而通过这我们就能利用这两笔交易的信息来还原出私钥

ECDSA签名

从名字上看ECDSA签名算法也就是ECC与DSA的组合，也就是椭圆曲线签名算法，因为椭圆曲线密码的单位比特强度要高于其他的公钥密码体系，所以在同样的短密钥条件下，基于ECC的系统的安全体系更高，因此它受到了区块链技术的青睐，这样的话密钥较短，运算速度也就更快，相应的也就能提高区块链的性能，比特币和以太坊都是使用ECDSA作为签名算法

我们知道ECC密码机制是基于如下的曲线

y ^ 2 =（x ^ 3 + a * x + b）mod p

而我们要进行签名就得知道我们所使用的曲线的参数，一般而言所需的参数组即(p, a, b, G, n, h）

参数组中p是一个非常大的质数，可以表示曲线上点的范围，a，b即曲线上的参数a与b，G 是该椭圆曲线上点倍积的基点，可以看作是一个参考点，n 是基点G的可倍积阶数，定义为能够使得点倍积n*G 不存在的最小的整数n，h是个常数，一般定义为1，有了这些我们就可以确定我们所使用的椭圆曲线算法了，也意味着我们能够用这些进行签名了

签名的过程就要用到我们的公钥与私钥了，当然，在以太坊中这也就代表着我们的账户，我们的账户地址正是截取了公钥hash的一部分得到的，假设我们的私钥为dA而公钥为QA，QA=dA*G，接下来就是签名的过程

假设要签名的消息为m

  1. 取 e = HASH(m)
  2. 取e的左边的Ln个bit长度的值为z，Ln即为前面提到的参数里n的比特长度
  3. 从 [1, n-1]范围内，随机选择一个整数k
  4. 利用k得到椭圆曲线上的一点 （x1，y1）=k * G
  5. 然后计算下面的式子的值，取其为r，如果如果r为0则返回步骤3重新选择k
    r = x1 mod n
  6. 计算下式的值，取其为s，如果s为0则返回步骤3重新选择k
    s = k^-1(z + r * dA) mod n
    注意此处的k^-1表示的是一个模反元素，它使得（k^-1 * k）mod p =1
  7. 得到的数字签名即为(r，s)

下面我们再简单说说验证签名
我们取点P（Xp,Yp)
P = s ^ -1 * z * G + s ^ -1 * r * QA
如果得到的Xp等于r，则签名有效，否则无效，下面是简单的证明

P = s ^ -1 * z * G + s ^ -1 * r * QA
因为QA=dA*G，故有

P = s ^ -1 * z * G + s ^ -1 * R * dA * G = s ^ -1（z + dA * R）* G

因为Xp要等于r，而r其实是K*G得到的x1，此处可以转换为

k * G = s ^ -1（z + dA * R）* G.

简化得到 k = s ^ -1（z + dA * r）
将上式的k与s反转即可得到 s = k ^ -1（z + dA * r），其实也就是我们前面进行签名使用的式子，看起来还是挺奇妙的，生成签名时我们使用了私钥dA与随机数k，验证签名时我们使用的则是公钥QA与签名s

利用冲突的随机数恢复私钥

从上面的签名过程我们可以看到最关键的地方就在于随机数k，对于一个固定的椭圆曲线，一个确定的k就意味着一个确定的r，所以如果有两个相同的私钥签署的签名出现了相同的r就代表着在生成随机数时取到了相同的k，看到这里想必你也明白了我们题目的交易签名的问题出在哪了，这两笔交易的r值相同，代表在它们签名时使用的随机数k是相同的，而这就是我们恢复私钥的关键

我们不妨设这两个签名的z与s分别为z1，z2与s1，s2
则有
s1-s2= k ^ -1（z1 + dA * r）-k ^ -1（z2+ dA * r）
        = k ^ -1（z + dA * r-z2-dA * r）
        = k ^ -1（z1 - z2）

所以有 k = （z1-z2)/(s1-s2)

既然知道了k，那么私钥dA我们也能直接计算了
dA =（s * k-z）/ r

这也是ECDSA签名算法的一个特性，所以它的安全性一定程度上也依赖于一个安全的随机数生成器，历史上因为k的冲突也导致了不少的安全问题，在2010年索尼的ps3游戏机所采用的ECDSA签名算法就被爆出使用的一直是同样的k，这意味着你随便找到一个私钥签署的两个签名就能恢复出该私钥，可以说是非常可怕了，这一情况在此报告中也有介绍，传送门

另外影响比较大的就是13年时爆出java的一个随机数生成器存在问题可能产生冲突的k值，这在当时导致了一些比特币钱包的私钥被黑客所恢复，从而造成损失，这其实也就是我们今天所面临的挑战，这一情况在这篇文章中也有介绍，感觉很多人也是从这意识到了这种问题的危害性

动手操作

下面我们来完成这一挑战，首先我们要明确目标，从前面我们知道了要恢复私钥我们需要两笔交易的s与z值，s值直接就在签名里面，我们要取得的是z，从签名的过程我们可以看出z其实就是对要签名的消息取的hash值，这里我使用nodejs的ethereumjs-tx库来模拟对交易的签名过程，将我们前面得到的交易信息进行hash

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

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

这里要注意使用该库中的hash函数时要选择参数false，因为参数为false时进行hash的对象是不加入签名信息的，也就是我们需要的z值，否则默认的参数为true得到的就是添加了签名信息的hash值，得到的其实就是我们的交易hash

然后我们恢复私钥，这里的步骤也就是我们上面反推私钥的式子，要注意的是需要实现一个取模反的运算，这一部分来自于python-ecdsa

def inverse_mod( a, m ):
    """Inverse of a mod m."""
    if a < 0 or m <= a: a = a % m
    c, d = a, m
    uc, vc, ud, vd = 1, 0, 0, 1
    while c != 0:
        q, c, d = divmod( d, c ) + ( c, )
        uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc

    assert d == 1
    if ud > 0: return ud
    else: return ud + m


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

将其导入我们的钱包即可调用挑战合约完成该题目

写在最后

这次的学习过程让我收获了很多，ECC算法确实是挺有趣的，之前对它的了解不是很充分，我自己现在应该也只算是初学，文章中如有错误也希望师傅们能够指正
顺带一提感觉capture the ether的题目质量着实是很高，很多题目让我学到了新东西，如有兴趣可参考我写的write up，part1 and part2

参考

https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

源链接

Hacking more

...