Quatre règles de base des signatures ECDSA…

May 10 2023

En 1999, Don Johnson Alfred Menezes (1999) a publié un article classique sur "The Elliptic Curve Digital Signature Algorithm (ECDSA)" : en gros, il a pris le DSA (Digital Signature Algorithm) - créé par David W. Kravitz - et l'a converti en une représentation par courbe elliptique.

Photo par Signature Pro sur Unsplash

En 1999, Don Johnson Alfred Menezes (1999) a publié un article classique sur "The Elliptic Curve Digital Signature Algorithm (ECDSA)":

Fondamentalement, il a pris le DSA (Digital Signature Algorithm) - créé par David W. Kravitz - et l'a converti en une représentation de courbe elliptique. Et donc, à mesure que les journaux discrets devenaient plus grands, les méthodes de courbes elliptiques étaient tellement plus efficaces.

Puis, en 2007, Satoshi Nakamoto a commencé à écrire du code pour son implémentation Bitcoin, et a sélectionné ECDSA comme méthode de signature principale, et a utilisé la courbe secp256k1. Pour Ethereum également, l'approche naturelle à utiliser était la méthode de signature ECDSA. Mais, les signatures ECDSA ont été sujettes aux attaques si elles ne sont pas correctement implémentées, alors examinons quatre règles de base.

La vraie magie d'ECDSA était que nous n'avions pas à stocker la clé publique, mais que la signature pouvait être vérifiée à partir d'une version hachée de la clé privée. De cette façon, la blockchain n'avait pas besoin de stocker les clés publiques de ceux qui l'utilisaient, et c'était l'une des premières fois que nous créions une infrastructure d'information véritablement décentralisée.

Si vous voulez comprendre le fonctionnement des signatures ECDSA, essayez ici .

Ne jamais fuir le nonce

Exemple : Crack ECDSA à partir d'une fuite de nonce (SECP256k1) . ECDSA avec nonce . Cela décrit ECDSA comment la clé privée peut être récupérée avec une fuite de la valeur nonce pour SECP256k1.

Avec une signature ECDSA, nous signons un message avec une clé privée ( priv ) et prouvons la signature avec la clé publique ( pub ). Une valeur aléatoire (un nonce) est ensuite utilisée pour randomiser la signature. Chaque fois que nous signons, nous créons une valeur nonce aléatoire et cela produira une signature différente (mais vérifiable). Globalement, le signataire n'a qu'à révéler les éléments de la signature et leur clé publique, et non la valeur nonce. Si le signataire révèle une seule valeur nonce par erreur, un intrus peut découvrir la clé privée. Dans ce cas, nous allons révéler la valeur nonce, déterminer la clé privée et utiliser la courbe secp256k1 (telle qu'utilisée avec Bitcoin).

Dans ECDSA, Bob crée une clé privée aléatoire ( priv ), puis une clé publique à partir de :

pub = privé × G

Ensuite, afin de créer une signature pour un message de M , il crée un nombre aléatoire ( k ) et génère la signature de :

r = k ⋅ G

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

La signature est alors ( r , s ) et où r est l'abscisse du point kG . H ( M ) est le hachage SHA-256 du message ( M ), et converti en une valeur entière. Si la valeur k est révélée pour l'une des signatures, un intrus peut déterminer la clé privée en utilisant :

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

Cela fonctionne parce que :

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

et ainsi:

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

et pour privé :

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

Voici un code qui fait une découverte de la clé privée, si le nonce ( k ) est révélé [ ici ] :

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

Exemple : Crack ECDSA avec des nonces faibles (sepc256k1) . ECDSA : Révéler la clé privée du même nonce . Cela décrit ECDSA comment la clé privée peut être récupérée avec des valeurs nonce faibles.

Dans ECDSA, Bob crée une clé privée aléatoire ( priv ), puis une clé publique à partir de :

pub = privé × G

Ensuite, afin de créer une signature pour un message de M , il crée un nombre aléatoire ( k ) et génère la signature de :

r = k ⋅ G

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

La signature est alors ( r , s ) et où r est l'abscisse du point kG . H ( M ) est le hachage SHA-256 du message ( M ), et converti en une valeur entière.

Supposons maintenant que nous ayons deux messages ( m 1 et m 2) et que nous ayons des hachages de :

h 1= H ( m 1)

h 2= H ( m 2)

Disons maintenant qu'Alice signe les messages avec la même clé privée ( priv) et le même nonce ( k) , on peut alors récupérer la clé privée avec :

On peut aussi récupérer le nonce avec :

Voici un code qui fait une découverte de la clé privée, et du nonce ( k ) si nous utilisons la même valeur de nonce [ ici ] :

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

Exemple : Révélation de la clé privée, à partir de deux clés et nonces partagés (SECP256k1) . ECDSA : Révélation de la clé privée, à partir de deux clés et des nonces partagés (SECP256k1) . Cela décrit ECDSA comment nous pouvons révéler deux clés privées à partir de quatre messages signés.

Avec une signature ECDSA, nous signons un message avec une clé privée ( priv ) et prouvons la signature avec la clé publique ( pub ). Une valeur aléatoire (un nonce) est ensuite utilisée pour randomiser la signature. Chaque fois que nous signons, nous créons une valeur nonce aléatoire et cela produira une signature différente (mais vérifiable). La clé privée, cependant, peut être découverte si Alice signe quatre messages avec deux clés et deux nonces [2]. Dans ce cas, elle signera le message 1 avec la première clé privée ( x 1), signera le message 2 avec une deuxième clé privée ( x 2), signera le message 3 avec la première clé privée ( x 1) et signera le message 4 avec le deuxième clé privée ( x 2) Le même nonce ( k1) est utilisé dans la signature des messages 1 et 2, et un autre nonce ( k 2) est utilisé dans la signature des messages 3 et 4.

Dans ECDSA, Bob crée une clé privée aléatoire ( priv ), puis une clé publique à partir de :

pub = privé × G

Ensuite, afin de créer une signature pour un message de M , il crée un nombre aléatoire ( k ) et génère la signature de :

r = k ⋅ G

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

La signature est alors ( r , s ) et où r est l'abscisse du point kG . H ( M ) est le hachage SHA-256 du message ( M ), et converti en une valeur entière.

Dans ce cas, Alice aura deux paires de clés, et avec deux clés privées ( x 1 et x 2). Elle signera le message 1 ( m 1) avec la première clé privée ( x 1), signera le message 2 ( m 2) avec une deuxième clé privée ( x 2), signera le message 3 ( m 3) avec la première clé privée ( x 1), et signer le message 4 ( m 4) avec la seconde clé privée ( x 2). Le même nonce ( k 1) est utilisé dans la signature des messages 1 et 2, et un autre nonce ( k 2) est utilisé dans la signature des messages 3 et 4. Supposons maintenant que nous ayons quatre messages ( m 1 .. m4) et ont des hachages de :

h 1= H ( m 1)

h 2= H ( m 2)

h 3= H ( m 3)

h 4= H ( m 4)

Les signatures des messages seront alors ( s 1, r 1), ( s 2, r 1), ( s 3, r 2) et ( 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 )

En utilisant l'élimination gaussienne, on peut aussi récupérer les clés privées avec :

et:

Voici un code qui découvre les clés privées [ ici ] :

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

Exemple : Attaque par faute . ECDSA : Attaque par défaut . Dans l'attaque par faute dans ECDSA, nous n'avons besoin que de deux signatures . L'un est produit sans défaut ( r , s ) et l'autre a un défaut ( rf , sf ). À partir de ceux-ci, nous pouvons générer la clé privée.

Dans l'attaque par faute dans ECDSA, nous n'avons besoin que de deux signatures . L'un est produit sans défaut ( r , s ) et l'autre a un défaut ( rf , sf ). A partir de ceux-ci, nous pouvons générer la clé privée [3,4].

Dans ECDSA, Bob crée une clé privée aléatoire ( priv ), puis une clé publique à partir de :

pub = privé × G

Ensuite, afin de créer une signature pour un message de M , il crée un nombre aléatoire ( k ) et génère la signature de :

r = k ⋅ G

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

et où d est la clé privée et h = H ( M ) La signature est alors ( r , s ) et où r est l'abscisse du point kG . h est le hachage SHA-256 du message ( M ), et converti en une valeur entière.

Maintenant, disons que nous avons deux signatures. L'un a un défaut et l'autre est valide. On a alors ( r , s ) pour celui valide, et ( rf , sf ) pour la faute. Ce seront :

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

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

et où h

est le hachage du message. Maintenant, si nous soustrayons les deux s

valeurs que nous obtenons :

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

Alors:

Celui-ci peut alors être remplacé par :

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

Cela donne:

Nous pouvons ensuite réorganiser cela pour dériver la clé privée ( d ) de :

Voici le code pour implémenter ceci [ ici ] :

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 est génial, mais doit être manipulé avec précaution !

Les références

[1] Brengel, M., & Rossow, C. (2018, septembre). Identifier les fuites de clés des utilisateurs de Bitcoin. Dans Symposium international sur la recherche sur les attaques, les intrusions et les défenses (pp. 623–643). Springer, Cham [ ici ].

[2] Brengel, M., & Rossow, C. (2018, septembre). Identifier les fuites de clés des utilisateurs de Bitcoin. Dans Symposium international sur la recherche sur les attaques, les intrusions et les défenses (pp. 623–643). Springer, Cham [ ici ].

[3] Sullivan, GA, Sippe, J., Heninger, N., & Wustrow, E. (2022). Ouvert à une panne : sur la compromission passive des clés {TLS} via des erreurs transitoires. Dans 31st USENIX Security Symposium (USENIX Security 22) (pp. 233–250).

[4] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M., & Rösler, P. (2018, avril). Attaquer des schémas de signature déterministes à l'aide d'attaques par faute. En 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (pp. 338–352). IEEE.