Warum ist es wichtig, dass Nonces beim Signieren nicht in Beziehung stehen?

Ich werde hier die Schnorr-Gleichung verwenden ( s = k + H(R||P||m)*dfür Signatur (R,s), Pubkey P = d*G, Nachricht m), aber alles gilt gleichermaßen für ECDSA (das verwendet s = (H(m) + R.x*d) / k) oder sogar für Mischungen zwischen den beiden. Alle Gleichungen sind modulo n, die Gruppenordnung.

Die gleiche Nonce

Stellen Sie sich vor, Sie haben zwei Signaturen mit demselben privaten Schlüssel und derselben Nonce auf zwei verschiedenen Nachrichten. Das bedeutet, Sie haben:

• s1 = k + H(R||P||m1)*d
• s2 = k + H(R||P||m2)*d

Subtrahiert man diese beiden Gleichungen voneinander, erhält man:

• s2 - s1 = (H(R||P||m2) - H(R||P||m1))*d

Was gelöst werden kann für d:

• d = (s2 - s1) / (H(R||P||m2) - H(R||P||m1)

Nonces mit bekanntem Offset

Wir wissen also, dass Sie nicht dieselbe Nonce für mehrere Signaturen verwenden sollten. Aber was ist, wenn Sie Nonces verwenden k1und k2wo k1zufällig ist, aber k2 = k1 + f, für den Angreifer bekannter Offset f.

Jetzt erhalten Sie:

• s1 = k1 + H(R||P||m1)*d
• s2 = k2 + H(R||P||m2)*d = k1 + f + H(R||P||m2)*d

Wieder subtrahieren ergibt:

• s2 - s1 = f + (H(R||P||m2) - H(R||P||m1)*d

Mit anderen Worten:

• d = (s2 - s1 - f) / (H(R||P||m2) - H(R||P||m1)

Nonces mit bekanntem Faktor

Ok, der Angreifer kann also den Unterschied zwischen den beiden Nonces nicht kennen. Was, wenn sie nur einen Faktor zwischen ihnen kennen? k2 = k1*u.

• s1 = k1 + H(R||P||m1)*d
• s2 = k2 + H(R||P||m2)*d = k1*u + H(R||P||m2)*d

Rechnen s2 - u*s1ergibt nun:

• s2 - u*s1 = H(R||P||m2)*d - H(R||P||m1)*d*u

Und somit:

• d = (s2 - u*s1) / (H(R||P||m2) - H(R||P||m1)*u)

Also auch das ist ein Problem.

Willkürliche bekannte Beziehung zwischen den Nonces

Wenn die Beziehung zwischen den Nonces komplexer ist als eine lineare Beziehung der Form k2 = u*k1 + f, gibt es im Allgemeinen keine einfache Formel, mit der Sie den privaten Schlüssel aus den Signaturen leicht berechnen können. Das Fehlen einer bekannten Formel bedeutet jedoch nicht, dass keine existiert, und stellt keinen Sicherheitsbeweis dar.

Die Frage, mit der wir uns beschäftigen, ist, unter welchen Umständen die Beziehung zwischen den Nonces so komplex ist, dass Angreifer sie nicht ausnutzen können. Es stellt sich heraus, dass es einige Möglichkeiten gibt, die einen Beweis haben:

• Alle Nonces werden einheitlich zufällig generiert
• Nonces werden als Ausgabe einer PRF (Pseudozufallsfunktion) berechnet; was ungefähr dem entspricht, was RFC6979 tut (das Seeding der PRF mit dem Unterzeichnerschlüssel).
• Die deterministische Nonce-Funktion von MuSig-DN

Andererseits kennen wir eine Reihe von Wegen, die aktiv gebrochen werden:

• Nonces, die eine bekannte lineare Beziehung zueinander haben (wie oben gezeigt)
• Nonces, die aus einem kleinen Zahlenbereich gezogen werden.

Aber zwischen diesen beiden gibt es eine riesige Lücke an Techniken, von denen weder bekannt ist, dass sie kaputt gehen, noch sich als sicher erwiesen haben. Viele von ihnen könnten durchaus sicher sein, aber wir wissen es nicht. Das bedeutet leider, dass es eigentlich keine Antwort auf die Frage "welche Eigenschaft wird benötigt" gibt; Wir kennen nur einige Techniken, die funktionieren.