Probleme mit deterministischem ECDSA basierend auf RFC6979 in Bitcoin

Das Generieren einer Zufallszahl kin einer elliptischen Kurve ist von entscheidender Bedeutung, und bei jeder Transaktionssignatur in Bitcoin ist eine Zufallszahl kerforderlich, um einen Punkt zu berechnen k*G. Wenn dies knicht zufällig gewählt wird, verliert es sofort den privaten Schlüssel.
Daher entwickelten sie eine Idee zur deterministischen Generierung von ECDSA, die in RFC6979 beschrieben wird . Im Grunde verketten sie den privaten Schlüssel mit der gehashten Nachricht und verwenden eine HMAC-Funktion und erzeugen einen Pseudozufallswert k.
Diese Methode scheint einfach und leicht.

  • Führt es zu Overhead?
  • Wenn ja, ist dieser Overhead vernachlässigbar?

Oder gibt es generell Ineffizienzen oder Probleme mit dieser Methode und warum sehen wir immer noch eine nicht-deterministische Implementierung von ECDSA?

Antworten (1)

Keine ernsthaften Effizienzbedenken. Das Signieren wird für einen bestimmten Kunden ziemlich selten durchgeführt (normalerweise nur wenige Signaturen pro Transaktion). Obwohl es möglich ist, dass die Signierung etwas länger dauert, um den kWert zu generieren, würde dies nicht auffallen, insbesondere wenn man bedenkt, wie selten sie von einem bestimmten Client verwendet wird. Die Überprüfung aller Signaturen ist der CPU-Engpass für die Blocküberprüfung in Bitcoin, da alle vollständigen Knoten die Signaturen aller Transaktionen im Netzwerk überprüfen müssen, und dies dauert unabhängig davon, wie der kParameter gewählt wurde, dieselbe Zeit.

Gregory Maxwell hat hier einen Kommentar zur Verwendung deterministischer kWerte abgegeben :

Die Hauptargumente in den meisten Bereichen gegen die Derandomisierung von DSA sind die FIPS-Konformität (für uns irrelevant) und berechtigte Bedenken hinsichtlich der Risiken der Verwendung eines (weniger) überprüften kryptografischen Konstrukts. Mit der weit verbreiteten Bewegung in Richtung derandomisierter DSA ist diese letztere Sorge weniger ein Problem.

Die neue libsecp256k1- Bibliothek von Pieter Wuille verwendet tatsächlich die deterministische Generierung von k.

Beachten Sie auch, dass einer der Hauptvorteile der Verwendung dieser Konstruktion darin besteht, dass Sie sich keine Sorgen machen müssen, dass eine Schwachstelle in Ihrem PRNG im Signierprozess ausgenutzt wird. Wenn Sie beispielsweise verschiedene Daten mit demselben kWert signieren, wird Ihr privater Schlüssel sofort preisgegeben . Ein ähnlicher Angriff kann auch ausgenutzt werden, wenn der PRNG schwach genug ist, um die Beziehung zwischen verschiedenen kWerten zu bestimmen, die beim Signieren derselben Daten verwendet werden. Da das kdeterministisch aus den von Ihnen signierten Daten (und dem privaten Schlüssel) generiert wird, sind diese Bedenken bezüglich des PRNG nicht mehr so ​​relevant, da Sie immer dieselbe Signatur für dieselben Daten erstellen. Dies erleichtert auch das Schreiben von ECDSA-Einheitentests.

Wie Sie bereits erwähnt haben, ist der Überprüfungsprozess derselbe, und das Hinzufügen einiger zusätzlicher HMAC-Berechnungen auf der Clientseite wirkt sich nicht wirklich auf den Signaturprozess aus.
Das zweimalige Signieren derselben Daten mit unterschiedlichen 'k'-Werten ist sicher.
@adaclin Nur wenn ein Angreifer die Beziehung zwischen den beiden verwendeten k-Werten nicht bestimmen kann. Wenn zum Beispiel bekannt ist, dass ein k gleich dem anderen plus eins ist, verliert es sofort Ihren privaten Schlüssel.
@PieterWuille Danke, ich habe meine Antwort aktualisiert. Ich hatte den different-ks-same-data-Angriff mit dem hier erwähnten different-data-same-ks-Angriff verwechselt .
@abeikverdi Tatsächlich erfordert das Generieren einer Nonce mit RFC6979 mit SHA256 22 Aufrufe der SHA256-Komprimierungsfunktion, was in der Größenordnung von 10 % der gesamten Signierzeit liegt.
@PieterWuille Kannst du mich erleuchten? Verketten wir nicht einfach den privaten Schlüssel und die gehashte Nachricht als HMAC-Nonce?
@abeikverdi Lesen Sie RFC6979 und versuchen Sie es zu implementieren, Sie werden sehen.
@PieterWuille Ich habe RFC6979 bereits gelesen. Habe aber nie versucht das umzusetzen. Sind diese 10 % Overhead-Zeit, auf die Sie sich beziehen, Ihre persönliche Erfahrung? oder seine wissenschaftliche?
Ich habe es verglichen. Wissenschaftlicher geht es nicht.
@ StephenM347 Würde dieser RFC 6979 nicht zweimal dasselbe k erzeugen? HMAC_DBGA(privater Schlüssel d || H(m)) generiert dasselbe k für dieselbe gehashte Nachricht, da der private Schlüssel konstant ist. Nicht wahr? Ist das kein Problem?
@abeikverdi, nicht wirklich, genau deshalb ist es nützlich, weil es dieselbe Signatur für dieselben Daten erzeugt. Es verwendet dasselbe k nur zweimal für dieselbe Nachricht. Nur wenn Sie verschiedene Daten mit demselben k-Wert signieren, wird Ihr privater Schlüssel preisgegeben. Die Verwendung des gleichen k für die gleichen Daten gibt keine neuen Informationen.
@ StephenM347 sind die Daten, auf die Sie sich beziehen, die gehashte Nachricht, der Hash der Transaktion?
@abeikverdi, im Wesentlichen ja, die zu signierenden Daten sind ein Hash der Transaktion, die von allen Eingaben gelöscht wurde (Sie signieren keine anderen Signaturen). Es gibt noch eine kleine Nuance, dass der vorherige scriptPubKey der ausgegebenen Ausgabe vor dem doppelten SHA256-Hashing in die scriptSig eingefügt wird.
@StephenM347 Vielen Dank! Ich habe es jetzt total verstanden!
Probleme mit deterministischem ECDSA basierend auf RFC6979 in Bitcoin
AntwortenHierDatenschutz-Bestimmungen1y, 0v