Eine schwache Transaktion in ECDSA auf der Bitcoin-Blockchain und mit Hilfe von Lattice Attack erhielten wir einen privaten Schlüssel zu BTC-Münzen

 

Was wissen wir über den Lattice Attack?

Zunächst einmal ist der digitale Signaturalgorithmus mit  elliptischer Kurve (ECDSA)  ein gängiges digitales Signaturschema, das wir in vielen unserer Codeüberprüfungen sehen. Es hat einige wünschenswerte Eigenschaften, kann aber auch sehr anfällig sein, um den privaten Schlüssel mit einem Seitenkanalangriff wiederherzustellen, der weniger als ein Bit der geheimen Nonce preisgibt.

ECDSA ist eine spezielle Form des digitalen Signaturalgorithmus  (DSA). DSA ist ein ziemlich weit verbreitetes digitales Signaturschema, das durch drei Algorithmen definiert ist: Schlüsselgenerierung, Signatur und Verifizierung. Der Schlüsselgenerierungsalgorithmus generiert private und öffentliche Schlüssel;  der private Schlüssel ist für die Erstellung von Signaturen verantwortlich;  und der öffentliche Schlüssel ist für die Überprüfung von Signaturen verantwortlich.  Der Signaturalgorithmus nimmt eine Nachricht und einen privaten Schlüssel als Eingabe und generiert eine Signatur. Der Verifizierungsalgorithmus nimmt eine Nachricht, eine Signatur und einen öffentlichen Schlüssel als Eingabe und gibt einen Wert von  true oder  zurück false, der angibt, ob die Signatur gültig ist.

DSA ist für jede mathematische Gruppe definiert, und dieses Schema ist sicher, solange das Problem des diskreten Logarithmus für diese Gruppe schwierig ist. Eine häufig verwendete Gruppe sind die ganzen Zahlen modulo einer Primzahl p.

Zusammen mit dieser Gruppe werden wir einen Gruppengenerator g und eine kryptografisch sichere  Hash -  Funktion  haben H. Davon können wir ausgehen  p , g und  H werden allgemein bekannt sein.

Die Schlüsselgenerierung funktioniert, indem zunächst zufällig ein Wert  x aus Modulo-Ganzzahlen  ausgewählt wird p . Dann wird der Wert berechnet y = g^x mod p

Der private Schlüssel der Signatur ist  x , und der öffentliche Schlüssel ist  y . Der Signierschlüssel muss geheim gehalten werden, da er die Erstellung von Signaturen ermöglicht.

Der Signaturalgorithmus erstellt aus der Nachricht  m und dem geheimen Schlüssel x eine Signatur. Zuerst wird ein zufälliges Gruppenelement generiert  k . Dies wird als Nonce bezeichnet, was bei Angriffen wichtig ist.

Dann werden die Werte berechnet  r = g^k mod p und s = ( k^-1 ( H ( m ) + xr )) mod p

Hier  k^- 1 ist , die inverse Gruppe und  H ( m ) das Ergebnis der Berechnung des Hashs m und der Interpretation des Ergebnisses als ganze Zahl modulo p .

Die Signatur ist definiert als ein Paar von  ( r , s ). (Hinweis: Wenn einer der  r oder  -Werte sgleich ist  0, startet der Algorithmus mit dem neuen Wert von neu  k ).

Der Verifikationsalgorithmus erhält als Input eine Signatur  ( r , s ), eine Nachricht  m und einen öffentlichen Schlüssel y. Let  ŝ = s^-1 , dann gibt der Algorithmus genau dann true zurück, wenn  r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .

Diese Validierungsprüfung funktioniert  g^H( m ) y^r = g^H(m)+ xr = g^ks, weil und daher (g^H(m)y^r)^ŝ = g^k = r

Ein digitales Signaturschema gilt als sicher, wenn es nicht gefälscht werden kann.

Unveränderlichkeit hat eine formale kryptografische Bedeutung, bedeutet aber auf hoher Ebene, dass Sie keine Signaturen erstellen können, ohne den geheimen Schlüssel zu kennen (es sei denn, Sie haben eine bereits vorhandene Signatur kopiert, die aus dem geheimen Schlüssel erstellt wurde). Es hat sich unter der Annahme eines diskreten Protokolls als  DSAunmöglich zu fälschen  erwiesen  .

DSA ist über eine mathematische Gruppe definiert. Bei  DSA Verwendung mit der Gruppe der elliptischen Kurven als dieser mathematischen Gruppe nennen wir sie  ECDSA. Die Gruppe  der elliptischen Kurven besteht aus elliptischen Kurvenpunkten, die Paare von  sind, die die Gleichung  für einige  ( x , y )erfüllen   . Für diesen Blogbeitrag müssen Sie nur wissen, dass Sie mit elliptischen Kurven eine endliche Gruppe definieren können, was bedeutet, dass Sie den Gruppengenerator  (Elliptic Curve Point) und die  Additions-  und  Punktmultiplikationsoperationen  genauso wie Sie erhalten kann mit ganzen Zahlen. Da sie eine endliche Gruppe bilden, Generator,y^2 = x^3 + ax + ba , bg g , wird eine endliche Ordnung haben,  p. Dieser Blogbeitrag wird nicht erklären oder verlangen, dass Sie wissen, wie diese  Operationen mit elliptischen Kurven funktionieren .

ECDSA funktioniert genauso wie  DSA, aber mit einer anderen Gruppe. Der geheime Schlüssel x  ist immer noch ein Zufallswert modulo integers  p . Jetzt wird der öffentliche Schlüssel  y immer noch als berechnet  y = g^x , außer dass g jetzt ein Punkt auf der elliptischen Kurve ist. Das bedeutet, dass y auch ein Punkt auf der elliptischen Kurve sein wird (früher war y eine ganze Zahl modulo p ). Ein weiterer Unterschied besteht darin, wie wir den Wert von r berechnen. Wir erzeugen immer noch eine zufällige Nonce k als ganze Zahl modulo p wie zuvor. Wir werden berechnen  g^k , aber auch g hier ist ein Punkt einer elliptischen Kurve und daher  g^k auch. Daher können wir berechnen  ( x^k , y^k ) = g^k und setzen  r = x^k . Jetzt die Bedeutung s kann wie zuvor berechnet werden, und wir erhalten unsere Signatur  ( r , s ), die immer noch eine ganze Zahl modulo  p ist, wie zuvor. Um dies zu überprüfen, müssen wir die Tatsache korrigieren, dass wir  r etwas anders berechnet haben.

Also berechnen wir wie zuvor   den Wert von  ( g^H(m)y^r)^ŝ , aber jetzt ist dieser Wert ein Punkt auf der elliptischen Kurve, also nehmen wir  xdie -Koordinate dieses Punktes und vergleichen sie mit unserem Wert von  r .

Wiederherstellung  geheimer Schlüssel  aus wiederverwendeten Nonces NONCES

Nachdem wir nun verstanden haben, was es ist  ECDSA und wie es funktioniert, wollen wir seine  Zerbrechlichkeit demonstrieren . Da dies wiederum ein digitales Signaturschema ist, ist es zwingend erforderlich, dass der  geheime Schlüssel  niemals jemand anderem als der Person, die die Nachricht signiert, offenbart wird.

Wenn der Unterzeichner jedoch jemals die Signatur ausstellt und auch die verwendete Nonce ausstellt, kann der  Angreifer den geheimen Schlüssel  sofort wiederherstellen  .

Nehmen wir an, ich gebe eine Signatur  ( r , s ) für eine Nachricht  frei m und entdecke versehentlich, dass ich eine Nonce verwendet habe  k .

Da  s = ( k^-1 ( H ( m ) + xr )), wir den geheimen Schlüssel leicht berechnen können:

s = (k^-1(H(m) + xr))

ks = H(m) + xr

ks – H(m) = xr

x = r^-1(ks – H(m))

Daher muss der Unterzeichner nicht nur seinen  privaten Schlüssel geheim halten , sondern alle seine jemals generierten Nonces sind geheim.

Selbst wenn der Unterzeichner jede  Nonce  geheim hält, wenn er versehentlich eine NonceNONCES wiederholt   (sogar für verschiedene Nachrichten),  kann der geheime Schlüssel  auch sofort  wiederhergestellt werden . NONCES

Lassen Sie  ( r , s 1 ) und  ( r , s 2 ) zwei Signaturen sein, die für Nachrichten  m 1 und  m 2 (jeweils) aus derselben Nonce  erstellt k wurden - da sie dieselbe Nonce haben, sind die r-Werte gleich, sodass dies für einen Angreifer sehr einfach zu erkennen ist:

s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)

s1 – s2 = k^-1(H(m1) – H(m2))

k(s1 – s2) = H(m1) – H(m2)

k = (s1 – s2)^-1(H(m1) – H(m2))

Sobald wir die Nonce  k mit der obigen Formel wiederhergestellt haben, können wir den privaten Schlüssel wiederherstellen, indem wir den zuvor beschriebenen Angriff durchführen.

Lassen Sie uns das für einen Moment verdauen.

Wenn  die Signatur -Nonce NONCES  jemals offengelegt wird, kann der  geheime Schlüssel sofort  wiederhergestellt werden, was  unser gesamtes Signaturschema bricht .

Wenn sich zwei Nonces jemals wiederholen,  kann ein Angreifer  dies unabhängig von den Nachrichten leicht erkennen und sofort  den geheimen Schlüssel wiederherstellen , was wiederum unser gesamtes Schema bricht.

Es ist ziemlich zerbrechlich und es sind nur  leichte Angriffe !

Aber es gibt einen  neuen  Lattice Attack  , der sehr ausführlich beschrieben wurde  (Joachim Breitner und Nadia Heninger)Йоахим Брайтнер и Надя Хенингер 

Dokument  [PDF] :  Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

In der Bitcoin-Blockchain haben wir eine bestimmte Transaktion gefunden:

Transaktion:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

für Bitcoin-Adressen:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

und wir haben es geschafft, die gefälschten Unterschriften zu vervielfachen und das Raster anzuwenden

wobei das  Python-Skript  algorithmLLL.py  bei der Installation von Paketen in  GOOGLE COLAB verwendet wird

INSTALLIEREN >> SAGE + ECDSA + BITCOIN + Algorithmus LLL

Wir haben es geschafft,  Private Key von  Bitcoin Wallet einer schwachen Transaktion in auszukommen  ECDSA.

Installation

Führen Sie das Bash-Skript aus: lattice.sh

Ergebnis im HEX-Format Privater Schlüssel gefunden!

Datei: ONESIGN.txt (ECDSA-Signatur R, S, Z-Wert)

Wir haben gefälschte Signaturen für das Python-Skript algorithmLLL.py verbreitet

Datei: PRIVATEKEY.txt

Datei: ADRESSE.txt

Überprüfung des privaten Schlüssels auf der Bitadresse-Website

Privater Schlüssel gefunden!

https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

0,001 BTC

ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX:  31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 

Dieses Video wurde für das  CRYPTO DEEP TECH -Portal erstellt  , um die finanzielle Sicherheit von Daten und secp256k1-Kryptografie mit elliptischen Kurven gegen schwache ECDSA-Signaturen in der Kryptowährung BITCOIN zu gewährleisten

Video:  https://youtu.be/YP4Xj6gUcf4

Telegramm :  https://t.me/cryptodeeptech

Quelle:  https://cryptodeep.ru/lattice-attack