Image for post
Image for post

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:

Image for post
Image for post

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:

Image for post
Image for post

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]:

Image for post
Image for post

We can also recover the nonce with:

Image for post
Image for post

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)) % orderprint ("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) % orderprint ("\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 2002471738384943086816141256024093586033631594556271393291305112022408440671Private recovered 2002471738384943086816141256024093586033631594556271393291305112022408440671K: 88075867541468469079894038746062981782K 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.

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store