ECDSA Signatures Are Great … But, Be Carefull of Nonce Reuse

ECDSA Signatures Are Great … But, Be Careful of Nonce Reuse

And, so, Satoshi Nakamoto came along and saw a way which allowed any citizen the opportunity to break away from PKI (Public Key Infrastructure), and create their own digital wallet — and without some trusted core signer having to prove their public key. It was the re-birth of the ECDSA (Elliptic Curve Digital Signature Algorithm) digital signature, and which has since built the core of trust for Bitcoin and Ethereum. Overall, ECDSA is now used as a replacement in many applications for the bloated RSA signature method.

It is a well-known secret that ECDSA needs to be set up properly, or else the private key could be revealed. In the worst case, Eve could reveal Alice’s Bitcoin private key from the ECDSA signatures. One of the weaknesses is that 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={s1}")
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: hello
k: 42697174952969771067920838522754768070293843446227278637024846558843325885985204999806924023865476689075859160206767221461424390901516846247395261243041915729772263174558136845078126543356323543436465917786639088513051105924751840
Sig 1 (Good): r=17792950205994430745794446294223915865229387957948780601476491076009949863160, s=64018639524698181013252286280206315087268312227186766880493279988843888424228
Sig 2 (Faulty): r=17792950205994430745794446294223915865229387957948780601476491076009949863161, s=18872482835376247544535980670899765380720144477442152012135320280503946530386

Generated private key: 24013964492218807721984741998141785569429137975731973337138275190248207359858

Recovered private key: 24013964492218807721984741998141785569429137975731973337138275190248207359858

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.