ECDSA: Revealing the private key, from four signed message, two keys and shared nonces (SECP256k1)

ECDSA: Revealing the private key, from four signed messages, two keys and shared nonces (SECP256k1)

It’s well known that the ECDSA signature (as used in Bitcoin) needs to be carefully created, or the private key can be discovered. The nightmare would thus be to sign a few messages and for Eve to then discover the private key from these. In this case, we will look at the case where Alice has two key pairs and signs four messages with these, and for Eve to discover where private keys.

Alice will have two key pairs [1], and with two private keys (x_1 and x_2). She will sign message 1 (m_1) with the first private key (x_1), sign message 2 (m_2) with a second private key (x_2), sign message 3 (m_3) with the first private key (x_1) and sign message 4 (m_4) with the second private key (x_2) The same nonce (k_1 is used for messages 1 and 2, and another nonce (k_2) is used to sign messages 3 and 4. Now let’s say we have four messages (m_1 .. m)4) and have hashes of:

The signatures for the messages will then be (s1,r1), (s2,r1), (s3,r2), and (s4,r2):

Using Gaussian elimination, we can also recover the private keys with:

and:

Here is some code which discovers the private keys [here]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()

priv1 = random.randrange(1,order)
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
x1 = ecdsa.ecdsa.Private_key(Public_key, priv1)

priv2 = random.randrange(1,order)
Public_key2 = ecdsa.ecdsa.Public_key(G, G * priv2)
x2 = ecdsa.ecdsa.Private_key(Public_key2, priv2)

k1 = random.randrange(1, 2**127)
k2 = random.randrange(1, 2**127)

msg1="Hello"
msg2="Hello1"
msg3="Hello3"
msg4="Hello4"

if (len(sys.argv)>1):
	msg1=(sys.argv[1])
if (len(sys.argv)>2):
	msg2=(sys.argv[2]) 
if (len(sys.argv)>3):
	msg3=(sys.argv[3]) 
if (len(sys.argv)>4):
	msg4=(sys.argv[4]) 

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
h3 = int(hashlib.sha256(msg3.encode()).hexdigest(),base=16)
h4 = int(hashlib.sha256(msg4.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k1)
sig2 = x2.sign(h2, k1)
sig3 = x1.sign(h3, k2)
sig4 = x2.sign(h4, k2)

r1,s1 = sig1.r,sig1.s
r1_1,s2 = sig2.r,sig2.s
r2,s3 = sig3.r,sig3.s
r2_1,s4 = sig4.r,sig4.s

valinv = libnum.invmod( r1*r2*(s1*s4-s2*s3),order)

x1rec = ((h1*r2*s2*s3-h2*r2*s1*s3-h3*r1*s1*s4+h4*r1*s1*s3    ) * valinv)  % order

x2rec = ((h1*r2*s2*s4-h2*r2*s1*s4-h3*r1*s2*s4+h4*r1*s2*s3    ) * valinv)  % order

print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r1_1}, s={s2}")
print ("\nMessage 3: ",msg3)
print (f"Signature r={r2}, s={s3}")
print ("\nMessage 4: ",msg4)
print (f"Signature r={r2_1}, s={s4}")

print ("\nPrivate key (x1):",priv1)
print ("\nPrivate recovered (x1): ",x1rec)
print ("\nPrivate key (x2):",priv2)
print ("\nPrivate recovered (x2):",x2rec)

A sample run is [here]:

Message 1:  hello
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=11930786632149881397940019723063699895405239832076777367931993614016265847425

Message 2:  hello1
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=86716405197525298580208026914311340731533780839926210284720464080897845438167

Message 3:  hello2
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=42453302255950972549884862083375617752595228510622859389343928824741407916152

Message 4:  hello3
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=64279036158699242111613174757286438038132181593159757823380636958768174455517

Private key (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858

Private recovered (x1):  82160419381684073393977402015108188969157550419795710258656483526045067388858

Private key (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942

Private recovered (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942

And code:

References

[1] Brengel, M., & Rossow, C. (2018, September). Identifying key leakage of bitcoin users. In International Symposium on Research in Attacks, Intrusions, and Defenses (pp. 623–643). Springer, Cham [here].