Quattro regole di base delle firme ECDSA...

Nel 1999, Don Johnson Alfred Menezes (1999) ha pubblicato un articolo classico su "The Elliptic Curve Digital Signature Algorithm (ECDSA)":

Fondamentalmente, ha preso il DSA (Digital Signature Algorithm) - creato da David W. Kravitz - e lo ha convertito in una rappresentazione della curva ellittica. E, quindi, man mano che i logaritmi discreti stavano diventando più grandi, i metodi della curva ellittica erano molto più efficienti.

Quindi, nel 2007, Satoshi Nakamoto ha iniziato a scrivere il codice per la sua implementazione di Bitcoin, ha selezionato ECDSA come metodo di firma principale e ha utilizzato la curva secp256k1. Anche per Ethereum l'approccio naturale da utilizzare era il metodo di firma ECDSA. Ma le firme ECDSA sono state soggette ad attacchi se non implementate correttamente, quindi diamo un'occhiata a quattro regole di base.

La vera magia di ECDSA era che non dovevamo archiviare la chiave pubblica, ma dove la firma poteva essere verificata da una versione con hash della chiave privata. In questo modo la blockchain non aveva bisogno di immagazzinare le chiavi pubbliche di chi la utilizzava, ed è stata una delle prime volte in cui abbiamo creato un'infrastruttura informativa veramente decentralizzata.

Se vuoi capire come funzionano le firme ECDSA, prova qui .

Non far trapelare mai il nonce

Esempio: Crack ECDSA da perdita di nonce (SECP256k1) . ECDSA con nonce . Questo delinea ECDSA come la chiave privata può essere recuperata con una perdita del valore nonce per SECP256k1.

Con una firma ECDSA, firmiamo un messaggio con una chiave privata ( priv ) e dimostriamo la firma con la chiave pubblica ( pub ). Viene quindi utilizzato un valore casuale (un nonce) per rendere casuale la firma. Ogni volta che firmiamo, creiamo un valore nonce casuale che produrrà una firma diversa (ma verificabile). Nel complesso il firmatario deve solo rivelare gli elementi della firma e la loro chiave pubblica, e non il valore nonce. Se il firmatario rivela per errore un solo valore nonce, un intruso può scoprire la chiave privata. In questo caso riveleremo il valore nonce, determineremo la chiave privata e utilizzeremo la curva secp256k1 (come usata con Bitcoin).

In ECDSA, Bob crea una chiave privata casuale ( priv ) e quindi una chiave pubblica da:

pub = privato × G

Successivamente, per creare una firma per un messaggio di M , crea un numero casuale ( k ) e genera la firma di:

r = k⋅G _ _

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

La segnatura è quindi ( r , s ) e dove r è la coordinata x del punto kG . H ( M ) è l'hash SHA-256 del messaggio ( M ) e convertito in un valore intero. Se il valore k viene rivelato per una qualsiasi delle firme, un intruso può determinare la chiave privata utilizzando:

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

Funziona perché:

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

e così:

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

e per privato :

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

Ecco un codice che fa una scoperta della chiave privata, se il nonce ( k ) viene rivelato [ qui ]:

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

Esempio: Crack ECDSA con nonces deboli (sepc256k1) . ECDSA: Rivelare la chiave privata dallo stesso nonce . Questo delinea ECDSA come la chiave privata può essere recuperata con valori nonce deboli.

Con una firma ECDSA, firmiamo un messaggio con una chiave privata ( priv ) e dimostriamo la firma con la chiave pubblica ( pub ). Viene quindi utilizzato un valore casuale (un nonce) per rendere casuale la firma. Ogni volta che firmiamo, creiamo un valore nonce casuale che produrrà una firma diversa (ma verificabile). La chiave privata, invece, può essere scoperta se Alice firma due messaggi diversi con lo stesso nonce [1].

In ECDSA, Bob crea una chiave privata casuale ( priv ) e quindi una chiave pubblica da:

pub = privato × G

Successivamente, per creare una firma per un messaggio di M , crea un numero casuale ( k ) e genera la firma di:

r = k⋅G _ _

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

La segnatura è quindi ( r , s ) e dove r è la coordinata x del punto kG . H ( M ) è l'hash SHA-256 del messaggio ( M ) e convertito in un valore intero.

Ora supponiamo di avere due messaggi ( m 1 e m 2) e di avere hash di:

h 1= H ( m 1)

h 2= H ( m 2)

Ora diciamo che Alice firma i messaggi con la stessa chiave privata ( priv) e lo stesso nonce ( k) , possiamo quindi recuperare la chiave privata con:

Possiamo anche recuperare il nonce con:

Ecco un codice che fa una scoperta della chiave privata e del nonce ( k ) se usiamo lo stesso valore nonce [ qui ]:

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

Esempio: Rivelazione della chiave privata, da due chiavi e nonce condivisi (SECP256k1) . ECDSA: Rivelare la chiave privata, da due chiavi e nonce condivisi (SECP256k1) . Questo delinea ECDSA come possiamo rivelare due chiavi private da quattro messaggi firmati.

Con una firma ECDSA, firmiamo un messaggio con una chiave privata ( priv ) e dimostriamo la firma con la chiave pubblica ( pub ). Viene quindi utilizzato un valore casuale (un nonce) per rendere casuale la firma. Ogni volta che firmiamo, creiamo un valore nonce casuale che produrrà una firma diversa (ma verificabile). La chiave privata, invece, può essere scoperta se Alice firma quattro messaggi con due chiavi e due nonce [2]. In questo caso firmerà il messaggio 1 con la prima chiave privata ( x 1), firmerà il messaggio 2 con una seconda chiave privata ( x 2), firmerà il messaggio 3 con la prima chiave privata ( x 1) e firmerà il messaggio 4 con la seconda chiave privata ( x 2) Lo stesso nonce ( k1) viene utilizzato nella firma per i messaggi 1 e 2, e un altro nonce ( k 2) viene utilizzato nella firma dei messaggi 3 e 4.

In ECDSA, Bob crea una chiave privata casuale ( priv ) e quindi una chiave pubblica da:

pub = privato × G

Successivamente, per creare una firma per un messaggio di M , crea un numero casuale ( k ) e genera la firma di:

r = k⋅G _ _

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

La segnatura è quindi ( r , s ) e dove r è la coordinata x del punto kG . H ( M ) è l'hash SHA-256 del messaggio ( M ) e convertito in un valore intero.

In questo caso Alice avrà due coppie di chiavi e con due chiavi private ( x 1 e x 2). Firmerà il messaggio 1 ( m 1) con la prima chiave privata ( x 1), firmerà il messaggio 2 ( m 2) con una seconda chiave privata ( x 2), firmerà il messaggio 3 ( m 3) con la prima chiave privata ( x 1) e firmare il messaggio 4 ( m 4) con la seconda chiave privata ( x 2). Lo stesso nonce ( k 1) è usato nella firma dei messaggi 1 e 2, e un altro nonce ( k 2) è usato nella firma dei messaggi 3 e 4. Supponiamo ora di avere quattro messaggi ( m 1 .. m4) e hanno hash di:

h 1= H ( m 1)

h 2= H ( m 2)

h 3= H ( m 3)

h 4= H ( m 4)

Le firme per i messaggi saranno quindi ( s 1, r 1), ( s 2, r 1), ( s 3, r 2) e ( 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 )

Utilizzando l'eliminazione gaussiana, possiamo anche recuperare le chiavi private con:

E:

Ecco un codice che scopre le chiavi private [ qui ]:

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

Esempio: Fault Attack . ECDSA: Fault Attack . Nell'attacco di guasto in ECDSA richiediamo solo due firme . Uno è prodotto senza difetto ( r , s ) e l'altro ha un difetto ( rf , sf ). Da questi possiamo generare la chiave privata.

Nell'attacco di guasto in ECDSA richiediamo solo due firme . Uno è prodotto senza difetto ( r , s ) e l'altro ha un difetto ( rf , sf ). Da questi, possiamo generare la chiave privata [3,4].

In ECDSA, Bob crea una chiave privata casuale ( priv ) e quindi una chiave pubblica da:

pub = privato × G

Successivamente, per creare una firma per un messaggio di M , crea un numero casuale ( k ) e genera la firma di:

r = k⋅G _ _

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

e dove d è la chiave privata e h = H ( M ) La firma è quindi ( r , s ) e dove r è la coordinata x del punto kG . h è l'hash SHA-256 del messaggio ( M ) e convertito in un valore intero.

Ora, diciamo che abbiamo due firme. Uno ha un difetto e l'altro è valido. Abbiamo quindi ( r , s ) per quello valido, e ( rf , sf ) per l'errore. Questi saranno:

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

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

e dove h

è l'hash del messaggio. Ora se sottraiamo le due s

valori otteniamo:

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

Poi:

Questo può quindi essere sostituito in:

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

Questo da:

Possiamo quindi riorganizzare questo per derivare la chiave privata ( d ) da:

Ecco il codice per implementare questo [ qui ]:

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 è fantastico, ma deve essere maneggiato con cura!

Riferimenti

[1] Brengel, M., & Rossow, C. (2018, settembre). Identificazione della perdita chiave degli utenti di bitcoin. In Simposio internazionale sulla ricerca in attacchi, intrusioni e difese (pp. 623–643). Springer, Cham [ qui ].

[2] Brengel, M., & Rossow, C. (2018, settembre). Identificazione della perdita chiave degli utenti di bitcoin. In Simposio internazionale sulla ricerca in attacchi, intrusioni e difese (pp. 623–643). Springer, Cham [ qui ].

[3] Sullivan, GA, Sippe, J., Heninger, N., & Wustrow, E. (2022). Aperto a un errore: sulla compromissione passiva delle chiavi {TLS} tramite errori transitori. Nel 31° USENIX Security Symposium (USENIX Security 22) (pp. 233–250).

[4] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M., & Rösler, P. (2018, aprile). Attaccare schemi di firma deterministici utilizzando attacchi di errore. Nel 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (pp. 338–352). IEEE.