MuSig: Ein neuer Multisignatur Standard

Bitcoin, sowie auch andere Blockchains wie Blockstream’s Liquid, verwenden den ECDSA Signatur Algorithmus (Elliptic Curve Digital Signature Algorithm), um den Besitz und Transfer von Coins im System zu verifizieren. Diese technische Entscheidung wurde angeblich 2008 getroffen, basierend auf einem weit verbreitetem und nicht patentiertem digitalen Signatursystem das damals zur Verfügung stand. Allerdings leidet ECDSA unter vielen technischen Einschränkungen. Im Besonderen gibt es multisignatures und threshold signatures - Signaturen, die von einem Quorum von unabhängigen Parteien stammen anstelle einer Einzelperson - was mit ECDSA sehr schwierig zu produzieren ist.  ECDSA Signaturen haben eine komplexe algebraische Struktur, die Arbeit mit ihnen inflexibel undschwierig macht. Entwickler sind gezwungen, Bitcoin Script für Anwendungen wie cross-chain atomic swaps oder Lightning zu verwenden, die eigentlich mehr kompakt und privat implementiert werden können durch die Verwendung eines flexibleren Signatursystems.

Seit 2008 hat sich der Stand der digitalen Signaturen dramatisch geändert. Die Technologie ist fortgeschrittener, jedoch wurden praktische Anforderungen für den realen Gebrauch übersehen. Öfters wird behauptet, dass Unterzeichner die komplette Kontrolle über ihre eigenen generierten Schlüssel haben. Es wird auch behauptet, dass Unterzeichner Zugriff auf nahezu perfekte Zufälligkeit haben ebenso wie auf persistente, sichere und zuverlässige Speicher. In der Realität haben Bitcoin Nutzer meistens begrenzten Zugriff zu ihren Schlüsseln mit wenig Kontrolle über den genauen Schlüsselgenerierungsmechanismus und keine Kontrolle darüber, wie externe Parteien die generierten Adressen verwenden. Um dieser Bedenken Rechnung zu tragen, haben wir eine Initiative begonnen ein neues Signatursystem zu entwickeln, mit dem Schwerpunkt auf praktischem Ingenieurwissen; die Implementierung sollte robust und antifragil werden.

Einführung

Im ersten Halbjahr des Vorjahres, in Zusammenarbeit mit Yannick Seurin und Gregory Maxwell, haben Blockstreams Kryptograph Pieter Wuille und ich MuSig veröffentlicht, ein neues Multisignatur Schema. Das Multisignatur Schema bietet nachweisbare Sicherheit, sogar gegen konspirierende böswillige Unterzeichner, und produziert Signaturen, die ununterscheidbar im Vergleich zu ordinären, Einzelunterzeichner Schnorr Signaturen sind.

Seitdem wandeln wir MuSig vom akademischen Papier zu nutzbarem Code um. Diese Woche haben wir den Code ins secp256k1-zkp eingefügt, ein Fork von secp256k1 - eine hohe sicherheits-kryptographische Bibliothek, die von Bitcoin Core verwendet wird. Die kryptographische Bibliothek wurde von uns erweitert um Unterstützung fuerConfidential Transaction  inElements und Liquid zu ermöglichen.

Während die Bitcoin Community die Anwendung von Schnorr Signaturen in Bitcoin untersucht, hoffen wir, dass unser Code irgendwann in die upstream secp256k1 Bibliothek eingefügt wird, und eines Tages von Bitcoin Core und vielen anderen Projekten verwendet wird. Unser Code produziert Signaturen, die mit BIP-schnorr konform sind und können auch “adaptor signatures” produzieren die dann Lightning in scriptless script ermöglicht.

Warum MuSig?

Wie letztes Jahr besprochen, existiert gerade breite kryptographische Literatur mit Multisignatur Schemen, und es macht Sinn sich zu fragen, warum wir unsere eigene entwickeln sollten. Die Antwort ist relativ einfach; wir haben zwei Anforderungen die derzeit nicht erfüllt werden:

1. Kurz, einheitlich lange Signaturen, die gleich aussehen trotz “signer set”. In Blockchain Systemen ist die Effizienzüberprüfung die wichtigste Überlegung, und es macht wenig Sinn, Verifizierer mit Einzelheiten von “signer composition” unnötig zu belasten um Diebstahl zu vermeiden. Als weiterer Vorteil bietet MuSig Signaturen eine bessere Privatsphäre, weil die genaue “signer policy” verborgen wird.
2. Nachweisbare Sicherheit in der Public Key Infrastruktur. Das bedeutet, dass Unterzeichner sehr flexibel zum Multisignaturverfahrungen beitragen können und einfache Schlüsselpaare verwenden können, ohne Zusatzinformationen darüber freizugeben, wie die Schlüssel generiert oder kontrolliert werden. Informationen zur Schlüsselgenerierung sind im Bitcoin Zusammenhang wahrscheinlich schwierig festzustellen, da einzelne Unterzeichner unterschiedliche Key Management Policies haben. Zudem kann eine Abhängigkeit vom Detail der Schlüsselgenerierung schlecht mit Taproot, einer vorgeschlagene Bitcoin Erweiterung mittels der Public Signature Keys zusätzliche, nicht erkennbare Semantik in Schlüsseln enkodiert werden, interagieren.

Seitdem wir MuSig angekündigt haben, haben wir erkannt, dass viele veröffentlichte Signatur Schemen unsicher sind, sogar unser noch nicht veröffentlichtes MuSig ist tatsächlich unsicher! In einem zukünftigen Blogpost werden wir das genauer unter die Lupe nehmen aber wir können jetzt mit Sicherheit sagen, dass wir viel zu tun haben bei der Entwicklung eines Multisignatur Schemas das ideal für Bitcoin und Liquid ist.

Fallstricke und sichere API-Entwicklung

Wie alle mathematischen Beschreibungen eines Multisignatur Protokolls geht MuSig auch davon aus, dass Teilnehmer während des Signaturprozesses Zugang zum Computerspeicher haben; der Speicher sollte persistent und einfach zum Updaten sein, ohne dass Angreifer die Möglichkeit haben, ein “Reset” auszuführen und somit auf einen früheren Speicherstatus zu gelangen. Wir gehen auch davon aus, dass Unterzeichner Zugriff auf Zufallselemente haben, die ununterscheidbar von uniform sind. Leider ist die reale Welt nicht so einfach, und wir haben uns sehr viel Mühe gegeben, eine API zu entwickeln, die in vielen Szenarien verwendet werden kann ohne dass limitierte Hardware eingesetzt werden muss oder dass ungeprüfte Annahmen dazu führen, dass Privatschlüsseldaten verloren gehen.

MuSig Signaturen, genau wie Schnorr Signaturen oder ECDSA, verwenden eine geheime Nonce in ihren Aufbau, die gleichmäßig und nach dem Zufallsprinzip produziert werden muss. Sollte es eine winzige Abweichung zur Gleichmäßigkeit geben, sogar nur einen Bit, können Privatschlüssel verloren gehen und Coins gestohlen werden. Unser erstes Entwurfsziel war es, eine API zu entwickeln, die gegen Missbrauch geschützt werden kann ohne damit die Anwendung gefährlicher Verwendungsmuster in begrenztem Umfeld zu bestärken.

Einheitliche Zufälligkeit

Mit einzelnen Signaturen gibt es einen Standardansatz um einheitliche Zufall Nonces zu generieren; geheime Daten und die zu signierende Nachricht werden zu einer kryptographischen Hash-Funktion weitergeleitet, um einen einheitlichen Zufallswert zu generieren welcher unabhängig für jede zu signierende Nachricht ist.

Mit Multisignaturen jedoch wird diese einfache robuste Lösung zur Belastung. Ein böswilliger Unterzeichner könnte zwei Multisignaturen auf die gleiche Nachricht anfordern und somit die eigene Signatur bei der zweiten Iteration justieren. Sollte der erste Unterzeichner seine Nonce auswählen, passiert folgendes: die gleiche Nonce wird in zwei sehr unterschiedlichen Signaturen verwendet, derselbe Fehler, der zum PS3 Hack geführt hat. Bedauerlicherweise (nicht wie beim Einzel-Unterzeichner) gibt es keine einfache Lösung, da individuelle Unterzeichner ihre Nonces auswählen müssen ohne die Einzelheiten der produzierten Signatur zu kennen.

Eine herkömmliche Lösung zum Problem, welche verwendet wurde bevor das Hashen beliebter wurde, ist einen Hardware Zufallszahlengenerator zu benutzen. Leider ist das eine kostspielige Lösung die zudem von äußeren Einflüssen beeinträchtigt werden kann. Die wichtigste Erkenntnis ist aber, dass es keine Möglichkeit gibt, eine korrekte Ausführung zu verifizieren.

Was den letzten Punkt angeht gibt es ein paar kreative Lösungen die wir aber in zukünftigen Blogposts erkunden werden. Inzwischen haben wir die Entscheidung getroffen, bei welcher der Nutzer eine eindeutige Session-ID für jede Signatur Session an die API zur Verfügung stellt. Noncen werden durch das Hashen folgender Parameter produziert: signer’s secret, set of signers, die zu unterzeichnende Nachricht und das eindeutige Session Input. Nutzer, die Zugriff auf einem Zufallszahlengenerator haben, können dies verwenden um Session-IDs zu produzieren; Nutzer, die Zugriff zum persistenten Computerspeicher haben, können einfach einen Zähler verwenden.

Wir sind nicht gerade begeistert, Zufallszahlen oder persistenten Computerspeicher anzufordern, aber wir sind uns sicher, dass unsere laufende Forschung sehr bald eine robuste Lösung produzieren wird.

Replay-Angriffe

Auch mit einer zuverlässigen Grundlage für die Zufallserzeugung ist es immer noch möglich, die Privatschlüssel eines Teilnehmers beim Multisignaturverfahren zu extrahieren, wenn ein Replay auf ein “Signing Protocol” an einem Punkt während des Prozesses ausgeführt wird. Diese Art von Angriff ist als Replay-Angriff bekannt, und kann gegen einen Unterzeichner ausgeführt werden, der gerade in einer Virtuellen Maschine tätig ist oder einer der den Signaturprozess unterbrechen kann und dann irgendeinen persistenten Speicherstatus wiederherstellen kann.

Es könnte sogar ungewollt ohne einen aktiven Angreifer auftreten; z.B könnte man zwei Virtuelle Maschinen mit gleichem Speicherstatus ausführen, oder Code in einer verteilten Datenbank die nicht mehr synchronisiert ist, ausführen. Um genauer zu sein, sollte ein Unterzeichner zur Multisignatur beitragen und sollte der Signaturprozess neu gestartet werden nachdem der Unterzeichner seine Nonce ausgewählt haben, ist es möglich, die Beiträge zur Multisignatur des anderen Unterzeichners zu modifizieren. Damit kann der vorher erwähnte Angriff ausgeführt werden.

Diese Art von Angriffen erstehen nicht mit Einzel-Signaturen, weil sie in einem Schritt produziert werden ohne einen zwischenliegenden Speicherstatus zu haben von welchem aus sie neu gestartet werden können. Diese zusätzlichen Herausforderungen sind einzigartig für Mehr-Runden kryptographischer Protokolle.

Ohne neue Mechanismen, an denen wir gerade arbeiten, können wir nichts unternehmen um Nutzer, die in Virtuellen Maschinen signieren, zu schützen. Wir können aber beobachten, dass die Verwendung von Virtuellen Maschinen das Sicherheitsrisiko erhöht, weil eine Maschine die einen Angreifer zurücksetzen kann ist wahrscheinlich auch eine Maschine von der ein Angreifer Privatschlüssel extrahieren kann.

Unterzeichner, die von einem alten Speicherstatus starten, möchten wir schützen, und deshalb unterstützt unsere API keine Signatur Sessions die von einem alten Speicherstatus ausgeführt werden.

In der Praxis bedeutet dies folgendes: Nutzer die unseren Code verwenden wollen, um Signing Sessions auch im Falle von Stromausfällen oder Störungen (ein sinnvolles Ziel für ein Hardware Wallet) aufrecht zu halten, müssen einen sicheren, persistenten Speicher erhalten. Sollten solche Wallets mehrere Signing Sessions parallel unterstützen, benötigen sie zusätzlichen, persistenten Speicher für jede parallele Session.

Immerhin glauben wir daran, auch dieses Hindernis zu beheben und verwenden verschiedene Ansätze an denen wir zur Zeit forschen.

Fazit und mehr

Es ist durch Beobachtungen eindeutig zu sehen, dass “multi-party” Protokolle deutlich schwierigere Herausforderungen im Vergleich zu “single-party” Protokollen vorweisen. In puncto mathematischer Komplexität ist MuSig viel einfacher als z.B Bulletproofs. Aber in Bezug auf Ausführungskomplexität benötigt MuSig mehr Aufwand und müsste Kompromisse zwischen Antifragilität und API Flexibilität eingehen.

Dieser Blogpost hat nur Multisignaturen beschrieben - Signaturen wo n _Unterzeichner zusammenarbeiten um eine Einzel Signatur zu produzieren. In Zukunft werden wir “threshold signatures” unter die Lupe nehmen, ein verwandtes Konzept wo eine beliebige Teilmenge von _n Unterzeichnern (davon ausgegangen, dass die Zahl der Unterzeichner ausreichend ist), Signaturen produzieren können ohne dass die gesamte Gruppe beitragen muss.

In weiteren Posts werden wir auch einige Techniken besprechen wie Nonce Zufälligkeit sicher produziert werden kann und auch besser verifiziert werden kann.  Genauer gesagt, es wird ein Verfahren verwendet, bezeichnet als sign-to-contract, das es ermöglicht, einem Hostrechner jegliche Möglichkeit von Befangenheit zu eliminieren, die von einem nicht vertrauenswürdigen Hardware Wallets Zufallszahlengenerator stammen kann.

Wenn wir aber noch weiter gehen können wir die Leistung von zero knowledge proofs nutzen, und es sollte möglich sein, die Risiken die durch Replay-Angriffe entstehen, zu eliminieren. So kann auch die Abhängigkeit von persistentem Speicher genommen werden und das MuSig Protokoll kann von drei auf zwei Runden zu reduziert werden. Wir sind auf diese Möglichkeit gespannt und freuen uns schon, unsere Ergebnisse mit allen zu teilen.

Unser Code ist Open Source und auf GitHub zu finden und wir ermutigen Interessenten es auszuprobieren und damit zu spielen. Wir freuen uns auf jegliches Feedback!