ECDSA Signatures Can Be Cracked With One Good Signature and One Bad One

I have been reading an excellent paper [1] and it outlines the usage of the fault attack on ECDSA signatures. With this we just need one…
Photo by Colynary Media on Unsplash

ECDSA Signatures Can Be Cracked With One Good Signature and One Bad One

I have been reading an excellent paper [1] and it outlines the usage of the fault attack on ECDSA signatures. With this we just need one good signature and a bad one, and where a signer has signed the same message, with the same nonce, and with the same private key. It is another worrying attack on ECDSA [2]:

If ECDSA, we generate a signature with:

and where k is a random nonce value, h is the hash of the message, and d is the private key. Now, let’s say we have two signatures. One has a fault and the other one is valid [2]. We then have (r,s) for the valid one, and (r_f,s_f) for the fault. These will be:

and where h is the hash of the message. Now if we subtract the two s values we get:

Then:

This can then be substituted in :

This gives:

We can then rearrange this to derive the private key (d) from:

Coding

As a demonstration, I have coded the method here:

https://asecuritysite.com/ecdsa/ecd7

In the code I have basically generated a good signature, and then a bad one by incrementing the r value of the signature:

# Now generate a fault
rf = sig.r+1
sf=(libnum.invmod(k,order)*(h+priv1*rf)) % order

The code is:

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)
d = ecdsa.ecdsa.Private_key(Public_key, priv1)
k = random.randrange(1, 2**127)
msg="Hello"
if (len(sys.argv)>1):
	msg=(sys.argv[1])
h = int(hashlib.sha256(msg.encode()).hexdigest(),base=16)
sig = d.sign(h, k)

r,s = sig.r,sig.s
# Now generate a fault
rf = sig.r+1
sf=(libnum.invmod(k,order)*(h+priv1*rf)) % order
k = h*(s-sf) * libnum.invmod(sf*r-s*rf,order)

valinv = libnum.invmod( (sf*r-s*rf),order)
dx =(h*(s-sf)* valinv) % order
print(f"Message: {msg}")
print(f"k: {k}")
print(f"Sig 1 (Good): r={r}, s={s}")
print(f"Sig 2 (Faulty): r={rf}, s={sf}")
print (f"\nGenerated private key: {priv1}")
print (f"\nRecovered private key: {dx}")

A sample run is [here]:

Message: hello
k: 15613459045461464441268016329920647751876410646419944753875923461028663912505625338208127533545920850138128660754322530221814353295370007218638086487275174473446354362246611811506735710487039390917643920660108528521515014507889120
Sig 1 (Good): r=84456595696494933440514821180730426741490222897895228578549018195243892414625, s=68818602365739991134541263302679449117335025608295087929401907013433000993001
Sig 2 (Faulty): r=84456595696494933440514821180730426741490222897895228578549018195243892414626, s=58598513613070973829759520121438538694005185742306423466103492198584643742545
Generated private key: 15195234419506006831576867959209365250058907799872905479943949602323611654898
Recovered private key: 15195234419506006831576867959209365250058907799872905479943949602323611654898

Conclusions

ECDSA — as used in Bitcoin and Ethereum — should be handled with care. If possible, use EdDSA, and which does not have the same risks as ECDSA. If you are interested, here are some of the issues with ECDSA:

  • Crack ECDSA from leak of nonce (NIST256p). ECDSA with nonce. This outlines ECDSA how the private key can be recovered with a leak of the nonce value for NIST256p.
  • Crack ECDSA from leak of nonce (SECP256k1). ECDSA with nonce. This outlines ECDSA how the private key can be recovered with a leak of the nonce value for SECP256k1.
  • Crack ECDSA from leak of nonce (NIST521p). ECDSA with nonce. This outlines ECDSA how the private key can be recovered with a leak of the nonce value for NIST521p.
  • Crack ECDSA with weak nonces. ECDSA with weak nonces. This outlines ECDSA how the private key can be recovered with weak nonce values.
  • Crack ECDSA with weak nonces (sepc256k1). ECDSA: Revealing the private key from same nonce. This outlines ECDSA how the private key can be recovered with weak nonce values.
  • ECDSA: Revealing the private key, from two keys and shared nonces (SECP256k1). ECDSA: Revealing the private key, from two keys and shared nonces (SECP256k1). This outlines ECDSA how we can reveal two private keys from four signed messages.
  • ECDSA: Fault Attack. ECDSA: Fault Attack. In the fault attack in ECDSA, we only require two signatures. One is produced without a fault (r,s), and the other has a fault (rf,sf). From these, we can generate the private key.

References

[1] Sullivan, G. A., Sippe, J., Heninger, N., & Wustrow, E. (2022). Open to a fault: On the passive compromise of {TLS} keys via transient errors. In 31st USENIX Security Symposium (USENIX Security 22) (pp. 233–250). [here]

[2] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M., & Rösler, P. (2018, April). Attacking deterministic signature schemes using fault attacks. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (pp. 338–352). IEEE.