Vier Grundregeln der ECDSA-Signaturen …

May 10 2023

Im Jahr 1999 veröffentlichte Don Johnson Alfred Menezes (1999) einen klassischen Artikel über „The Elliptic Curve Digital Signature Algorithm (ECDSA)“: Im Wesentlichen wurde der DSA (Digital Signature Algorithm) – erstellt von David W. Kravitz – verwendet und in ihn umgewandelt eine elliptische Kurvendarstellung.

Foto von Signature Pro auf Unsplash

Im Jahr 1999 veröffentlichte Don Johnson Alfred Menezes (1999) einen klassischen Artikel über „The Elliptic Curve Digital Signature Algorithm (ECDSA)“:

Im Wesentlichen wurde der von David W. Kravitz entwickelte DSA (Digital Signature Algorithm) in eine elliptische Kurvendarstellung umgewandelt. Und da diskrete Protokolle immer größer wurden, waren Methoden mit elliptischen Kurven viel effizienter.

Dann, im Jahr 2007, begann Satoshi Nakamoto, Code für seine/ihre Bitcoin-Implementierung zu schreiben, wählte ECDSA als Hauptsignaturmethode und verwendete die Kurve secp256k1. Auch für Ethereum war die ECDSA-Signaturmethode der natürliche Ansatz. Allerdings sind ECDSA-Signaturen anfällig für Angriffe, wenn sie nicht korrekt implementiert werden. Schauen wir uns also vier Grundregeln an.

Der wahre Zauber von ECDSA bestand darin, dass wir nicht den öffentlichen Schlüssel speichern mussten, sondern dass die Signatur anhand einer gehashten Version des privaten Schlüssels überprüft werden konnte. Auf diese Weise musste die Blockchain nicht die öffentlichen Schlüssel derjenigen speichern, die sie nutzten, und es war eines der ersten Mal, dass wir eine wirklich dezentrale Informationsinfrastruktur geschaffen haben.

Wenn Sie verstehen möchten, wie ECDSA-Signaturen funktionieren, versuchen Sie es hier .

Lassen Sie niemals die Nonce durchsickern

Beispiel: ECDSA aus einem Nonce-Leck knacken (SECP256k1) . ECDSA mit Nonce . Darin wird ECDSA dargelegt, wie der private Schlüssel bei einem Leck des Nonce-Werts für SECP256k1 wiederhergestellt werden kann.

Bei einer ECDSA-Signatur signieren wir eine Nachricht mit einem privaten Schlüssel ( priv ) und beweisen die Signatur mit dem öffentlichen Schlüssel ( pub ). Anschließend wird ein Zufallswert (eine Nonce) verwendet, um die Signatur zu randomisieren. Jedes Mal, wenn wir signieren, erstellen wir einen zufälligen Nonce-Wert, der eine andere (aber überprüfbare) Signatur erzeugt. Insgesamt muss der Unterzeichner nur die Elemente der Signatur und seinen öffentlichen Schlüssel preisgeben, nicht jedoch den Nonce-Wert. Wenn der Unterzeichner versehentlich nur einen Nonce-Wert preisgibt, kann ein Eindringling den privaten Schlüssel herausfinden. In diesem Fall werden wir den Nonce-Wert offenlegen, den privaten Schlüssel bestimmen und die Kurve secp256k1 verwenden (wie sie bei Bitcoin verwendet wird).

In ECDSA erstellt Bob einen zufälligen privaten Schlüssel ( priv ) und dann einen öffentlichen Schlüssel aus:

pub = priv × G

Um als Nächstes eine Signatur für eine Nachricht von M zu erstellen , erstellt er eine Zufallszahl ( k ) und generiert die Signatur von:

r = k ⋅ G

s = k ^{−1}( H ( M )+ r ⋅ priv )

Die Signatur ist dann ( r , s ) und wobei r die x-Koordinate des Punktes kG ist . H ( M ) ist der SHA-256-Hash der Nachricht ( M ) und wird in einen ganzzahligen Wert umgewandelt. Wenn der k- Wert für eine der Signaturen offengelegt wird, kann ein Eindringling den privaten Schlüssel ermitteln, indem er Folgendes verwendet:

priv = r ^{−1}×(( k ⋅ s )− H ( M ))

Das funktioniert, weil:

s ⋅ k = H ( M )+ r ⋅ priv

und so:

r ⋅ priv = s ⋅ k − H ( M )

und für priv :

priv = r −1( s ⋅ k − H ( M ))

Hier ist ein Code, der eine Entdeckung des privaten Schlüssels durchführt, wenn die Nonce ( k ) enthüllt wird [ hier ]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()
print ("Curve detail")
print (G.curve())
print ("Order:",order)
print ("Gx:",G.x())
print ("Gy:",G.y())

priv = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv)
Private_key = ecdsa.ecdsa.Private_key(Public_key, priv)
 
k1 = random.randrange(1, 2**127)
msg1="Hello"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
m1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
 
sig1 = Private_key.sign(m1, k1)

print ("\nMessage 1: ",msg1)
print ("Sig 1 r,s: ",sig1.r,sig1.s)
r1_inv = libnum.invmod(sig1.r, order)
s1 = sig1.s
 
try_private_key = (r1_inv * ((k1 * s1) - m1)) % order
print ()
print ("Found Key: ",try_private_key)
print ()
print ("Key: ",priv)
if (ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key):
 print("\nThe private key has been found")
 print (try_private_key)

Curve detail
CurveFp(p=115792089237316195423570985008687907853269984665640564039457584007908834671663, a=0, b=7, h=1)
Order: 115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424

Message 1:  hello
Sig 1 r,s:  31110256322898237264490243973699731757547476866639597679936653478826981616940 39826373609221276498318363598911660764943881869513002749160966300292770474312
Found Key:  95525957745036960168874600860927089941985475618074755510253043724286299804190
Key:  95525957745036960168874600860927089941985475618074755510253043724286299804190
The private key has been found
95525957745036960168874600860927089941985475618074755510253043724286299804190

Beispiel: ECDSA mit schwachen Nonces knacken (sepc256k1) . ECDSA: Offenlegung des privaten Schlüssels aus derselben Nonce . Dies beschreibt ECDSA, wie der private Schlüssel mit schwachen Nonce-Werten wiederhergestellt werden kann.

In ECDSA erstellt Bob einen zufälligen privaten Schlüssel ( priv ) und dann einen öffentlichen Schlüssel aus:

pub = priv × G

Um als Nächstes eine Signatur für eine Nachricht von M zu erstellen , erstellt er eine Zufallszahl ( k ) und generiert die Signatur von:

r = k ⋅ G

s = k ^{−1}( H ( M )+ r ⋅ priv )

Die Signatur ist dann ( r , s ) und wobei r die x-Koordinate des Punktes kG ist . H ( M ) ist der SHA-256-Hash der Nachricht ( M ) und wird in einen ganzzahligen Wert umgewandelt.

Nehmen wir nun an, wir haben zwei Nachrichten ( m 1 und m 2) und Hashes von:

h 1= H ( m 1)

h 2= H ( m 2)

Nehmen wir nun an, dass Alice die Nachrichten mit demselben privaten Schlüssel ( priv) und derselben Nonce ( k) signiert . Dann können wir den privaten Schlüssel wiederherstellen mit:

Wir können die Nonce auch wiederherstellen mit:

Hier ist ein Code, der den privaten Schlüssel und die Nonce ( k ) ermittelt, wenn wir [ hier ] denselben Nonce-Wert verwenden :

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)

Message 1:  hello
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=78942102071383249892109282228339664393041099900407940222266026023142592864884
Message 2:  hello1
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=83502523167965149244641473202679268630845178075816922294718909855670078364206
Private key 6542179820561127199468453109220159836323733777364616770035873205004743487369
Private recovered  6542179820561127199468453109220159836323733777364616770035873205004743487369
K:  109308891778201478280270581205739604663
K recovered  109308891778201478280270581205739604663

Beispiel: Offenlegung des privaten Schlüssels aus zwei Schlüsseln und gemeinsamen Nonces (SECP256k1) . ECDSA: Offenlegung des privaten Schlüssels aus zwei Schlüsseln und gemeinsamen Nonces (SECP256k1) . Dies beschreibt ECDSA, wie wir zwei private Schlüssel aus vier signierten Nachrichten enthüllen können.

Bei einer ECDSA-Signatur signieren wir eine Nachricht mit einem privaten Schlüssel ( priv ) und beweisen die Signatur mit dem öffentlichen Schlüssel ( pub ). Anschließend wird ein Zufallswert (eine Nonce) verwendet, um die Signatur zu randomisieren. Jedes Mal, wenn wir signieren, erstellen wir einen zufälligen Nonce-Wert, der eine andere (aber überprüfbare) Signatur erzeugt. Der private Schlüssel kann jedoch entdeckt werden, wenn Alice vier Nachrichten mit zwei Schlüsseln und zwei Nonces signiert [2]. In diesem Fall signiert sie Nachricht 1 mit dem ersten privaten Schlüssel ( x 1), signiert Nachricht 2 mit einem zweiten privaten Schlüssel ( x 2), signiert Nachricht 3 mit dem ersten privaten Schlüssel ( x 1) und signiert Nachricht 4 mit dem zweiter privater Schlüssel ( x 2) Die gleiche Nonce ( k1) wird beim Signieren der Nachrichten 1 und 2 verwendet, und eine weitere Nonce ( k 2) wird beim Signieren der Nachrichten 3 und 4 verwendet.

In ECDSA erstellt Bob einen zufälligen privaten Schlüssel ( priv ) und dann einen öffentlichen Schlüssel aus:

pub = priv × G

Um als Nächstes eine Signatur für eine Nachricht von M zu erstellen , erstellt er eine Zufallszahl ( k ) und generiert die Signatur von:

r = k ⋅ G

s = k −1( H ( M )+ r ⋅ priv )

Die Signatur ist dann ( r , s ) und wobei r die x-Koordinate des Punktes kG ist . H ( M ) ist der SHA-256-Hash der Nachricht ( M ) und wird in einen ganzzahligen Wert umgewandelt.

In diesem Fall verfügt Alice über zwei Schlüsselpaare und zwei private Schlüssel ( x 1 und x 2). Sie signiert Nachricht 1 ( m 1) mit dem ersten privaten Schlüssel ( x 1), signiert Nachricht 2 ( m 2) mit einem zweiten privaten Schlüssel ( x 2) und signiert Nachricht 3 ( m 3) mit dem ersten privaten Schlüssel ( x) . 1) und signieren Sie Nachricht 4 ( m 4) mit dem zweiten privaten Schlüssel ( x 2). Dieselbe Nonce ( k 1) wird beim Signieren der Nachrichten 1 und 2 verwendet, und eine andere Nonce ( k 2) wird beim Signieren der Nachrichten 3 und 4 verwendet. Nehmen wir nun an, wir haben vier Nachrichten ( m 1 .. m4) und haben Hashes von:

h 1= H ( m 1)

h 2= H ( m 2)

h 3= H ( m 3)

h 4= H ( m 4)

Die Signaturen für die Nachrichten lauten dann ( s 1, r 1), ( s 2, r 1), ( s 3, r 2) und ( s 4, r 2):

s 1= k 1−1( h 1+ r 1⋅ x 1)(mod p )

s 2= k 1−1( h 2+ r 1⋅ x 2)(mod p )

s 3= k 2−1( h 3+ r 2⋅ x 1)(mod p )

s 4= k 2−1( h 4+ r 2⋅ x 2)(mod p )

Mithilfe der Gaußschen Eliminierung können wir die privaten Schlüssel auch wiederherstellen mit:

Und:

Hier ist ein Code, der die privaten Schlüssel erkennt [ hier ]:

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)
priv2 = random.randrange(1,order)
Public_key2 = ecdsa.ecdsa.Public_key(G, G * priv2)
x2 = ecdsa.ecdsa.Private_key(Public_key2, priv2)
k1 = random.randrange(1, 2**127)
k2 = random.randrange(1, 2**127)
msg1="Hello"
msg2="Hello1"
msg3="Hello3"
msg4="Hello4"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
if (len(sys.argv)>2):
 msg2=(sys.argv[2]) 
if (len(sys.argv)>3):
 msg3=(sys.argv[3]) 
if (len(sys.argv)>4):
 msg4=(sys.argv[4]) 

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
h3 = int(hashlib.sha256(msg3.encode()).hexdigest(),base=16)
h4 = int(hashlib.sha256(msg4.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k1)
sig2 = x2.sign(h2, k1)
sig3 = x1.sign(h3, k2)
sig4 = x2.sign(h4, k2)
r1,s1 = sig1.r,sig1.s
r1_1,s2 = sig2.r,sig2.s
r2,s3 = sig3.r,sig3.s
r2_1,s4 = sig4.r,sig4.s
valinv = libnum.invmod( r1*r2*(s1*s4-s2*s3),order)
x1rec = ((h1*r2*s2*s3-h2*r2*s1*s3-h3*r1*s1*s4+h4*r1*s1*s3    ) * valinv)  % order
x2rec = ((h1*r2*s2*s4-h2*r2*s1*s4-h3*r1*s2*s4+h4*r1*s2*s3    ) * valinv)  % order

print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r1_1}, s={s2}")
print ("\nMessage 3: ",msg3)
print (f"Signature r={r2}, s={s3}")
print ("\nMessage 4: ",msg4)
print (f"Signature r={r2_1}, s={s4}")
print ("\nPrivate key (x1):",priv1)
print ("\nPrivate recovered (x1): ",x1rec)
print ("\nPrivate key (x2):",priv2)
print ("\nPrivate recovered (x2):",x2rec)

Message 1:  hello
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=11930786632149881397940019723063699895405239832076777367931993614016265847425
Message 2:  hello1
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=86716405197525298580208026914311340731533780839926210284720464080897845438167
Message 3:  hello2
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=42453302255950972549884862083375617752595228510622859389343928824741407916152
Message 4:  hello3
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=64279036158699242111613174757286438038132181593159757823380636958768174455517
Private key (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858
Private recovered (x1):  82160419381684073393977402015108188969157550419795710258656483526045067388858
Private key (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942
Private recovered (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942

Beispiel: Fehlerangriff . ECDSA: Fehlerangriff . Beim Fault-Angriff in ECDSA benötigen wir nur zwei Signaturen . Einer wird ohne Fehler hergestellt ( r , s ), der andere weist einen Fehler auf ( rf , sf ). Aus diesen können wir den privaten Schlüssel generieren.

Beim Fault-Angriff in ECDSA benötigen wir nur zwei Signaturen . Einer wird ohne Fehler hergestellt ( r , s ), der andere weist einen Fehler auf ( rf , sf ). Daraus können wir den privaten Schlüssel [3,4] generieren.

In ECDSA erstellt Bob einen zufälligen privaten Schlüssel ( priv ) und dann einen öffentlichen Schlüssel aus:

pub = priv × G

Um als Nächstes eine Signatur für eine Nachricht von M zu erstellen , erstellt er eine Zufallszahl ( k ) und generiert die Signatur von:

r = k ⋅ G

s = k ^{−1}( h + r ⋅ d )

und wobei d der private Schlüssel und h = H ( M ) ist. Die Signatur ist dann ( r , s ) und wobei r die x-Koordinate des Punktes kG ist . h ist der SHA-256-Hash der Nachricht ( M ) und wird in einen ganzzahligen Wert umgewandelt.

Nehmen wir an, wir haben zwei Unterschriften. Einer hat einen Fehler und der andere ist gültig. Wir haben dann ( r , s ) für den gültigen und ( rf , sf ) für den Fehler. Dies werden sein:

sf = k^{ −1}.( h + d . rf )(mod p )

s = k ^{−1}.( h + d . r )(mod p )

und wo h

ist der Hash der Nachricht. Wenn wir nun die beiden s subtrahieren

Werte erhalten wir:

s − sf = k ^{−1}.( h + d . r )− k^{ −1}.( h + d . rf )

Dann:

Dies kann dann ersetzt werden durch:

s = k^{ −1}( h + r . d )(mod p )

Das gibt:

Wir können dies dann neu anordnen, um den privaten Schlüssel ( d ) abzuleiten von:

Hier ist der Code, um dies zu implementieren [ hier ]:

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}")

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

ECDSA ist großartig, muss aber mit Vorsicht behandelt werden!

Verweise

[1] Brengel, M. & Rossow, C. (2018, September). Identifizieren von Schlüssellecks von Bitcoin-Benutzern. Im International Symposium on Research in Attacks, Intrusions, and Defenses (S. 623–643). Springer, Cham [ hier ].

[2] Brengel, M. & Rossow, C. (2018, September). Identifizieren von Schlüssellecks von Bitcoin-Benutzern. Im International Symposium on Research in Attacks, Intrusions, and Defenses (S. 623–643). Springer, Cham [ hier ].

[3] Sullivan, GA, Sippe, J., Heninger, N. und Wustrow, E. (2022). Offen für einen Fehler: Zur passiven Kompromittierung von {TLS}-Schlüsseln durch vorübergehende Fehler. Im 31. USENIX-Sicherheitssymposium (USENIX Security 22) (S. 233–250).

[4] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M. & Rösler, P. (2018, April). Angriff auf deterministische Signaturschemata mithilfe von Fehlerangriffen. Im Jahr 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (S. 338–352). IEEE.