So sollen quantensichere Bitcoin-Signaturen alltagstauglich werden

Kaum ein Zukunftsszenario sorgt bei Bitcoin für so viel Angst wie Quantencomputer, die heutige Signaturen angreifen könnten. Denn dann wäre es möglich, aus einem sichtbaren öffentlichen Schlüssel den privaten Schlüssel zu berechnen und fremde Bitcoin auszugeben. Noch gibt es keinen Quantencomputer, der dazu in der Lage wäre. Das mögliche Schadensausmaß ist dennoch zu groß, um es heute noch zu ignorieren.

Das zentrale Problem quantenresistenter Signaturen ist ihre Größe und damit ihr zusätzlicher Platzbedarf in Transaktionen. Heutige Schnorr-Signaturen, die auf elliptischen Kurven basieren, benötigen lediglich 64 Byte. Viele Post-Quantum-Verfahren erzeugen dagegen Signaturen von mehreren Kilobyte (KB). Bei Signaturen dieser Größenordnung passen weniger Transaktionen in einen Block, was die Netzwerkgebühren anfachen dürfte. Eine Bitcoin-Lösung muss deshalb nicht nur gegen Quantenangriffe ausgelegt, sondern auch möglichst kompakt sein.

Bislang wirkte die Debatte oft abstrakt: Einerseits standen Warnungen vor einer Technologie, die es so noch nicht gibt, andererseits Ansätze ohne einen fertigen Weg ins Bitcoin-Netzwerk. Unser ausführlicher Überblick zur Quantensicherheit zeigt, welche Konzepte derzeit entstehen und warum eine Umstellung anspruchsvoll wäre.

Nun liegt für SHRINCS aber ein konkreter BIP-Entwurf vor. Mitautor Jonas Nick bezeichnet ihn als ersten konkreten Entwurf eines Post-Quantum-Signaturverfahrens, das speziell für Bitcoin entwickelt wurde. Der Draft beschreibt die kryptografischen Algorithmen und enthält eine ausführbare Referenzimplementierung. Diese dient allerdings nur zur Überprüfung der Spezifikation und ist noch nicht für den produktiven Einsatz vorgesehen.

SHRINCS soll eine praktische Frage beantworten: Wie lassen sich Post-Quantum-Signaturen für Bitcoin kompakt halten, ohne grundlegende Anforderungen an Selbstverwahrung und Wallet-Wiederherstellung zu vernachlässigen?

Die schwarzen Punkte markieren die Zwischenwerte, welche die Wallet veröffentlicht. Die Werte links davon bleiben geheim. Ab jedem schwarzen Punkt berechnet der Verifizierer entlang der durchgezogenen Pfeile weitere SHA-256-Operationen.

Die Endwerte aller 32 Ketten werden zu einem WOTS-Public-Key zusammengefasst. Zusätzlich enthält die Signatur einen Merkle-Pfad. Mit ihm rekonstruiert der Verifizierer die Stateful-Wurzel und vergleicht sie mit dem entsprechenden Bestandteil des 48 Byte großen SHRINCS-Public-Keys. Stimmen Wurzel und Bindung an die Nachricht, besteht die Signatur die im Draft beschriebene kryptografische Prüfung.

Wie bei Bitcoin der konkrete Transaktions-Sighash gebildet und SHRINCS in Script und Konsensregeln eingebunden würde, ist noch nicht konkret festgelegt. Erst nach einer entsprechenden Aktivierung würden validierende Bitcoin-Nodes diese Signaturen prüfen.

Der Größenvorteil entsteht im Stateful-Pfad: SHRINCS-Signaturen können je nach Merkle-Pfad zwischen 548 und 4.619 Byte groß sein. Zum Vergleich erzeugt das standardisierte hashbasierte Post-Quantum-Verfahren Signaturen mit 7.856 Byte.

Dadurch wären die Signaturen quantensicher und zugleich ziemlich klein. Jedoch kommt ein Problem auf: Beim Signieren werden Zwischenwerte aus den Hashketten offengelegt. Wird derselbe Einmalschlüssel für zwei verschiedene Nachrichten verwendet, erhält ein Beobachter zusätzliche Teile dieser Ketten.

Dadurch wird nicht zwangsläufig der gesamte private Hauptschlüssel offengelegt. Die zusätzlichen Informationen können aber ausreichen, um eine gültige Signatur für eine andere Nachricht zu konstruieren und damit die betroffenen Bitcoin auszugeben. Jeder stateful WOTS+C-Einmalschlüssel darf deshalb nur einmal verwendet werden.

Damit kein Einmalschlüssel doppelt verwendet wird, führt die Wallet einen persistenten Counter, also einen Zähler. Dieser beginnt bei 0 und wird für jede erzeugte Stateful-Signatur erhöht. Aus Counter und Baumstruktur bestimmt der Algorithmus den jeweils noch unbenutzten WOTS+C-Slot.

Entscheidend ist, dass die Wallet den neuen Counter-Wert dauerhaft speichern muss, bevor sie die Signatur an die aufrufende Software zurückgibt. Der Zähler darf nicht aus einem Backup zurückgesetzt werden. Auch paralleles Signieren mit demselben Schlüssel auf mehreren Geräten wäre gefährlich. Der Draft verlangt deshalb geschützten, dauerhaften und möglichst gegen Rollbacks abgesicherten Speicher.

Damit entsteht ein Backup-Problem. Ein Seed kann wiederhergestellt werden, der zuletzt verwendete Counter ist darin aber nicht enthalten. Verwendet die Wallet nach einer Wiederherstellung einen alten Zählerstand, könnte sie einen Einmalschlüssel erneut einsetzen. Angreifer könnten dann unter Umständen Signaturen fälschen und die betroffenen Bitcoin ausgeben.

SHRINCS kombiniert zwei alternative, miteinander gebundene Signaturpfade unter einem 48 Byte großen öffentlichen Schlüssel. Eine gültige Signatur aus einem der beiden Pfade genügt:

• Stateful: Der normale Pfad erzeugt je nach Merkle-Pfad Signaturen zwischen 548 und 4.619 Byte. Er benötigt einen zuverlässig gespeicherten Counter.
• Stateless: Der Rückfallpfad benötigt keinen persistenten Counter und erzeugt stets 5.777 Byte große Signaturen.

Solange der Wallet-Zustand intakt ist, verwendet die Wallet den kompakteren Stateful-Pfad. Ist der Counter verloren, beschädigt oder unsicher, muss sie Stateful-Signaturen verweigern und auf den größeren Stateless-Pfad wechseln.

Nach der Wiederherstellung mit einem Seed kann die Wallet damit weiterhin eine gültige Signatur erzeugen. Wie SHRINCS-Schlüssel konkret aus einer Wallet-Mnemonic abgeleitet werden, ist allerdings nicht Teil des Entwurfs. In der Praxis könnte die wiederhergestellte Wallet die Bitcoin über den Stateless-Pfad auf ein neu erzeugtes Schlüsselpaar übertragen. Für dieses neue Schlüsselpaar steht bei korrekt verwaltetem Counter anschließend wieder der kompakte Stateful-Pfad zur Verfügung.

Dem Entwurf wurde noch keine BIP-Nummer zugewiesen. Der Status lautet noch „Draft“. SHRINCS ist auf ein bestimmtes Post-Quantum-Sicherheitsniveau ausgelegt. Der formale Sicherheitsbeweis für die konkrete Konstruktion und ihre Parameter steht jedoch noch aus.

Das Dokument spezifiziert bislang die kryptografischen Algorithmen für Schlüsselerzeugung, Signieren und Verifizieren. Bitcoin-Sighash-, Script-, Konsens- und Aktivierungsregeln sind darin nicht enthalten. Sie müssten in diesem oder einem ergänzenden Vorschlag festgelegt werden.

Durch den Draft wird im Bitcoin-Netzwerk nichts aktiviert und Schnorr wird nicht ersetzt. SHRINCS ist noch keine fertige Lösung für Bitcoins mögliches Quantenproblem, aber ein erster konkreter Vorschlag, den Kryptografen und Bitcoin-Entwickler nun testen, analysieren und kritisieren können.