ECDSA Weakness Where Nonces Are Reused

ECDSA Weakness Where Nonces Are Reused

It is a well-known secret that ECDSA needs to be set up properly, else the private key could be revealed. In the worse case, Eve could reveal Alice’s Bitcoin private key from the ECDSA signatures. One of the weaknesses is where the same nonce value is used for different messages. So let’s crack.

With an ECDSA signature, we sign a message with a private key (priv) and prove the signature with the public key (pub). A random value (a nonce) is then used to randomize the signature. Each time we sign, we create a random nonce value and it will produce a different (but verifiable) signature. The private key, though, can be discovered if Alice signs two different messages with the same nonce. In this case, we will use SECP256k1 (and which is used in Bitcoin).

In ECDSA, Bob creates a random private key (priv), and then a public key from:

Next, in order to create a signature for a message of M, he creates a random number (k) and generates the signature of:

The signature is then (r,s) and where r is the x-coordinate of the point kG. H(M) is the SHA-256 hash of the message (M), and converted into an integer value. Now let’s say we have two messages (m1 and m2) and have hashes of:

Now let’s say that Alice signs the messages with the same private key (priv) and the same nonce (k), we can then recover the private key with [1]:

We can also recover the nonce with:

Here is some code which does a discovery of the private key, and the nonce (k) if we use the same nonce value [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)

k = random.randrange(1, 2**127)

msg1="Hello"
msg2="Hello1"

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

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k)
sig2 = x1.sign(h2, k)

r1,s1 = sig1.r,sig1.s
r2,s2 = sig2.r,sig2.s

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

x1rec = (   (s2*h1-s1*h2) * (valinv)) % order

print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s2}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r2}, s={s2}")

print ("\nPrivate key",priv1)
print ("\nPrivate recovered ",x1rec)

valinv = libnum.invmod( (s1-s2),order)

k1rec = (   (h1-h2) * valinv) % order

print ("\nK: ",k)
print ("\nK recovered ",k1rec)

A sample run is [here]:

Message 1:  hello
Signature r=115750241653324917405156356036487436577003583891841226328966565092098577696014, s=967307463403244551367459885243432011877668751460551135495589243262430367112
Message 2:  hello123
Signature r=115750241653324917405156356036487436577003583891841226328966565092098577696014, s=967307463403244551367459885243432011877668751460551135495589243262430367112

Private key 2002471738384943086816141256024093586033631594556271393291305112022408440671

Private recovered  2002471738384943086816141256024093586033631594556271393291305112022408440671

K:  88075867541468469079894038746062981782

K recovered  88075867541468469079894038746062981782

Here is the 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.