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 \((r_f,s_f)\). From these we can generate the private key [1,2].
ECDSA: The Fault Attack |
Theory
In ECDSA, Bob creates a random private key (\(priv\)), and then a public key from:
\(pub= priv \times G\)
Next, in order to create a signature for a message of \(M\), he creates a random number (\(k\)) and generates the signature of:
\(r = k \cdot G\)
\(s = k^{-1} (h+ r \cdot d)\)
and where \(d\) is the private key and \(h=H(M)\) The signature is then \((r,s)\) and where \(r\) is the x-co-ordinate of the point \(kG\). \(h\) is the SHA-256 hash of the message (\(M\)), and converted into an integer value.
Now, let's say we have two signatures. One has a fault and the other one is valid. We then have \((r,s)\) for the valid one, and \((r_f,s_f)\) for the fault. These will be:
\(s_f=k^{-1}.(h+d.r_f) \pmod p\)
\(s=k^{-1}.(h+d.r) \pmod p\)
and where \(h\) is the hash of the message. Now if we subtract the two \(s\) values we get:
\(s - s_f = k^{-1}.(h+d.r)- k^{-1}.(h+d.r_f)\)
Then:
\(s - s_f = k^{-1}.(d.r-d.r_f) \pmod p\)
\(k.(s - s_f ) = (d.r-d.r_f) \pmod p\)
\(k = (d.r - d.r_f) . (s-s_f )^{-1} \pmod p\)
This can then be substituted in :
\(s = k^{-1} (h + r .d) \pmod p\)
This gives:
\( s= (s-s_f).{(d.r-d.r_f)}^{-1}.(h+d.r) \pmod p\)
\( s.(d.r-d.r_f)= (s-s_f).(h+d.r) \pmod p\)
\( s.d.r-s.d.r_f= s.h+s.d.r-h.s_f-d.r.s_f \pmod p\)
\( -s.d.r_f= s.h-h.s_f-d.r.s_f \pmod p\)
\( d.r.s_f -s.d.r_f= s.h-h.s_f \pmod p\)
\( d.(r.s_f -s.r_f)= h.(s-s_f) \pmod p\)
We can then rearrange this to derive the private key (\(d\)) from:
\(d = h.(s-s_f).{(s_f.r-s.r_f)}^{-1} \pmod p\)
Coding
Here is the code to implement this:
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:
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
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).
[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.