前言

这篇文章应该算是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

点击收藏 | 1 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖