1,7 Millionen alte Bitcoins, 9-minütiges Angriffsfenster: Quantencomputing löst eine Welle des „Schlüsselaustauschs“ aus
Was würde passieren, wenn eines Tages jemand nur Ihre Bankkartennummer kennt und daraus Ihr Zahlungspasswort zurückschließen kann?
Das Risiko, das Bitcoin durch Quantencomputing ausgesetzt ist, folgt ungefähr dieser Logik.
Dass Bitcoin heute sicher funktioniert, liegt daran, dass jede Wallet ein Paar „Schlüssel“ hat: Einer heißt öffentlicher Schlüssel und darf öffentlich bekannt gegeben werden; der andere heißt privater Schlüssel und darf nur von Ihnen selbst aufbewahrt werden. Normalerweise ist es selbst wenn jemand Ihren öffentlichen Schlüssel kennt, nahezu unmöglich, den privaten Schlüssel zu berechnen. Solange der private Schlüssel nicht preisgegeben wird, kann Ihr Geld kaum von anderen überwiesen werden.
Aber das Quantencomputing bringt ein Problem mit sich. Wenn Quantencomputer in der Zukunft leistungsstark genug sind, können sie mithilfe einer Methode namens Shor-Algorithmus aus dem öffentlichen öffentlichen Schlüssel den privaten Schlüssel zurückschließen. Mit anderen Worten: Eine Wallet, für die man früher erst den „Schlüssel stehlen“ musste, um sie zu öffnen, kann in Zukunft möglicherweise nur durch einen Blick auf das „Schloss“ neu mit einem Schlüssel berechnet werden.
Genau hier stellt das Quantencomputing eine echte Bedrohung für Bitcoin dar. Wenn andere Ihren privaten Schlüssel berechnen können, wie soll dann bewiesen werden, dass dieser Bitcoin Ihnen gehört?
In der Vergangenheit galt dieses Problem immer als weit von der Realität entfernt. Theoretisch kann Quantencomputing zwar das von Bitcoin verwendete Kryptographiesystem knacken, aber es wurde allgemein angenommen, dass der Bau eines solchen Geräts ein unglaublich großes Ausmaß erfordern würde.
Im März dieses Jahres stellte ein Papier von Forschern von Google Quantum AI, der Stanford-Universität, der Berkeley-Universität und der Ethereum Foundation diese Einschätzung in Frage. Das 57-seitige Papier berechnete neu, wie groß ein Quantencomputer in Zukunft tatsächlich sein muss, um Bitcoin angreifen zu können?
Die Autoren kamen zu dem Ergebnis, dass zum Knacken des von Bitcoin verwendeten secp256k1-Kryptographiesystems möglicherweise nur etwa 1200 bis 1450 logische Qubits erforderlich sind. Unter einer von ihnen angenommenen Architektur für supraleitendes Quantencomputing könnte die Anzahl der benötigten physischen Qubits sogar auf unter 500.000 sinken.
Noch auffälliger ist eine Zahl: 9 Minuten. Nach dem Modell des Papiers könnte ein in Zukunft leistungsstarker und schneller Quantencomputer in etwa 9 Minuten aus einem öffentlichen öffentlichen Schlüssel den privaten Schlüssel berechnen.
Das Problem ist noch komplizierter: Es gibt einige Coins, bei denen niemand aktiv das „Schloss austauschen“ kann. Beispielsweise die große Menge an Bitcoin, die aus der Zeit von Satoshi Nakamoto stammt und seit mehr als zehn Jahren nicht bewegt wurde, bei der der private Schlüssel möglicherweise längst verloren gegangen ist. Wenn zukünftige Quantencomputer diese privaten Schlüssel neu berechnen können, können diese seit Jahren schlafenden Bitcoin plötzlich wieder geöffnet werden.
Daher geht es in diesem Papier nicht nur um die Frage „Wird Quantencomputing Bitcoin knacken?“, sondern es stellt eine Reihe tiefergehender Fragen:
- Warum kann Quantencomputing Kryptowährungen bedrohen?
- Wie leistungsstark muss ein Gerät für einen echten Quantenangriff sein?
- Wie genau wird Bitcoin angegriffen?
- Warum ist das Risiko für Ethereum komplexer als für Bitcoin?
- Alle Probleme stammen aus dem ECDLP – warum wechselt man nicht direkt zu PQC?
- Was passiert am Ende, wenn Millionen von ruhenden BTC nicht migriert werden können?
Mit diesen Fragen schauen wir uns an, wie dieses Papier darauf antwortet.
01
Warum kann Quantencomputing Kryptowährungen bedrohen?
Dieses Papier konzentriert sich nicht darauf, worin die Rechenleistung von Quantencomputern gegenüber klassischen Computern überlegen ist, sondern untersucht ein spezifischeres kryptographisches Problem.
Die Sicherheit vieler moderner Blockchains hängt vom diskreten Logarithmusproblem auf elliptischen Kurven ab, dem sogenannten ECDLP (Elliptic Curve Discrete Logarithm Problem), das auf klassischen Computern schwer zu lösen ist.
Der kryptographisch relevante Quantencomputer CRQC (Cryptographically Relevant Quantum Computer) wird die bestehende Kryptographie mit öffentlichen Schlüsseln bedrohen. Das Problem bei RSA ergibt sich aus der effizienten Quantenlösung der ganzzahligen Faktorisierung durch den Shor-Algorithmus, während das Problem bei der Kryptographie auf elliptischen Kurven ECC daraus resultiert, dass der Shor-Algorithmus das ECDLP effizient lösen kann.
Das steht in direktem Zusammenhang mit Kryptowährungen. Blockchains wie Bitcoin und Ethereum verwenden in großem Umfang digitale Signaturen, die auf dem ECDLP basieren.
Und der Kern der Sicherheit der meisten Kryptowährungen basiert auf einer grundlegenden Annahme: Das ECDLP ist schwer zu lösen. Spezifische Blockchain-Funktionen, die diese Annahme der Schwierigkeit nutzen, umfassen die Transaktionsvalidierung von Bitcoin und Ethereum sowie den Proof-of-Stake(PoS)-Konsensmechanismus von Ethereum.
Auf Basis dieser Schätzungen diskutiert das Papier zwei mögliche Entwicklungsszenarien für CRQC, die als Grundlage für die spätere Diskussion über potenzielle Minderungsstrategien dienen. Insbesondere bestimmt, wie schnell frühe CRQC Angriffe durchführen können, direkt welche Blockchain-Schwachstellen praktisch ausgenutzt werden können – und damit auch, welche zwischengeschalteten Minderungsmaßnahmen vor der vollständigen Migration zu PQC vorrangig umgesetzt werden sollten.
Je nach erforderlicher Ausführungsgeschwindigkeit des Angriffs und der Frage, ob bei jedem Angriff auf das CRQC zugegriffen werden muss oder ob das CRQC nur einmal verwendet werden muss, um ein universell wiederverwendbares Angriffswerkzeug herzustellen, werden Quantenangriffe in drei Kategorien unterteilt:
1. Angriffe während der Transaktion (On-Spend Attacks): Zielen auf Transaktionen ab, die übertragen werden und noch nicht endgültig in die Blockchain eingetragen sind. Wenn ein Blockchain-Nutzer eine Transaktion aussendet, muss der Angreifer den privaten Schlüssel innerhalb des zulässigen Zeitfensters ableiten, bevor die Transaktion in der Blockchain aufgezeichnet wird. Dies erfordert, dass der Quantencomputer das ECDLP innerhalb der Transaktionsabwicklungszeit der Ziel-Blockchain lösen kann. Die Abwicklungszeiten verschiedener Blockchains reichen von einigen hundert Millisekunden bis zu mehreren Minuten: Beispielsweise beträgt sie bei Solana etwa 400 Millisekunden, bei Ethereum etwa 12 Sekunden und bei Bitcoin durchschnittlich etwa 10 Minuten. Angriffe während der Transaktion werden auch als „Kurzstreckenangriffe“ (short-range attacks) oder „Just-in-Time-Angriffe“ (just-in-time attacks) bezeichnet.
2. Angriffe auf ruhende Bestände (At-Rest Attacks): Zielen auf öffentliche Schlüssel ab, die lange Zeit auf der Kette oder außerhalb der Kette exponiert sind, beispielsweise ruhende Wallets mit wiederverwendeten Schlüsseln. In diesem Szenario hat der Angreifer mehrere Tage oder sogar länger Zeit, den privaten Schlüssel abzuleiten. Angriffe auf ruhende Bestände werden auch als „Langstreckenangriffe“ (long-range attacks) oder „Angriffe mit langer Expositionsdauer“ (long-exposure attacks) bezeichnet.
3. Angriffe während der Einrichtungsphase (On-Setup Attacks): Zielen auf feste öffentliche Protokollparameter ab, mit dem Ziel, eine universelle, wiederverwendbare Hintertür in einem kryptographischen Protokoll zu erzeugen. Der Angreifer muss nur einmal das CRQC für eine offline-Quantenberechnung verwenden, um die Hintertür zu konstruieren – danach kann er bei Angriffen über diese Hintertür nur noch klassische Computer verwenden. Beispielsweise könnte der Angreifer mithilfe des Shor-Algorithmus den sogenannten „giftigen Abfall“ (toxic waste) wiederherstellen, der während des vertrauenswürdigen Einrichtungsrituals von Powers-of-Tau (τ-Potenz) eigentlich vernichtet werden sollte. Die Bitcoin-Blockchain selbst ist immun gegen Angriffe während der Einrichtungsphase, aber einige Skalierungslösungen wie der Datenverfügbarkeits-Sampling-Mechanismus von Ethereum und einige Datenschutzprotokolle wie Tornado Cash sind von dieser besonders versteckten und gefährlichen Angriffsart betroffen.
Es ist darauf hinzuweisen, dass Quantenangriffe auf Kryptowährungen auch anders klassifiziert werden können. Beispielsweise lassen sie sich nach der verletzten Sicherheits-Eigenschaft weiter unterteilen:
• Angriffe auf das Eigentum an Vermögenswerten, beispielsweise das Fälschen von Transaktionen in Bitcoin;
• Konsensangriffe, beispielsweise die Durchführung einer tiefen Blockchain-Rekombination nach der Kompromittierung von mehr als der Hälfte der Ethereum-Validatoren;
• Angriffe auf die Vertraulichkeit, beispielsweise die Zerstörung der Unverknüpfbarkeit zwischen verschiedenen Adressen von Zcash;
• Angriffe auf die Integrität der Währung, beispielsweise die illegale Erschaffung neuer Coins in Mimblewimble oder in einer fehlerhaften Ethereum-zk-Rollup;
• Angriffe auf die Zahlungsfähigkeit, beispielsweise der Zusammenbruch des Ankers durch illegale Einlösung bei Rootstock oder Einlösung von Stablecoins, oder das geräuschlose Leeren der anonymen Pools von Tornado Cash;
• Angriffe auf die Datenverfügbarkeit, beispielsweise das Fälschen von Beweisen für das Datenverfügbarkeits-Sampling von Ethereum;
• Angriffe auf die Governance, beispielsweise das Fälschen von Abstimmungen in dezentralen autonomen Organisationen (DAO) von Cardano oder Ethereum, oder die Übernahme von Vermögenswerten von Kettenbrücken, die durch Multi-Signatur kontrolliert werden.
Die Transaktionsvalidierung von Bitcoin und Ethereum, der PoS-Konsens von Ethereum und andere Funktionen hängen in unterschiedlichem Maße von dieser Annahme ab.
Am Beispiel von Bitcoin ist seine grundlegende Vermögenseinheit das UTXO. Ob ein UTXO ausgegeben werden kann, erfordert, dass der Ausgeber eine gültige digitale Signatur vorlegt, die zum entsprechenden öffentlichen Schlüssel passt; die Erzeugung einer gültigen Signatur erfordert den Besitz des entsprechenden privaten Schlüssels. Daher fasst das Papier die kryptographische Eigentumsbeziehung von Bitcoin sehr direkt zusammen. In kryptographischer Hinsicht bedeutet der Besitz von Bitcoin, dass man den privaten Schlüssel beherrscht, der zu den öffentlichen Schlüsseln gehört, die diese Bitcoin sperren.
Und genau hier liegt die grundlegende Veränderung, die das CRQC mit sich bringt. Sobald der öffentliche Schlüssel öffentlich ist, kann das CRQC mithilfe des Shor-Algorithmus durch Lösen des ECDLP den entsprechenden privaten Schlüssel ableiten.
Das Papier geht daher davon aus, dass dies das aktuelle, auf kryptographischen Problemen basierende Eigentumsmodell von Bitcoin grundlegend erschüttern wird.
Warum verdienen Kryptowährungen besondere Aufmerksamkeit?
Erstens sind viele Blockchains zur Effizienz und Skalierbarkeit stark auf das auf ECDLP basierende Kryptographiesystem angewiesen. Bei gleichem Sicherheitsniveau ist die Schlüssellänge, die diese Art von Kryptographiesystem erfordert, fast eine Größenordnung kleiner als bei RSA – daher ist das erforderliche Ausmaß des CRQC zum Knacken auch kleiner.
Zweitens verfügt das traditionelle Finanzwesen normalerweise über mehrschichtige Sicherheitsvorkehrungen und Mechanismen zur Rückverfolgung von Transaktionen, während Blockchains häufig keine Fähigkeit zur Rückverfolgung von betrügerischen Transaktionen haben. Das Papier stellt klar fest: Ein einziger erfolgreicher Fälschungsangriff auf eine digitale Signatur kann zu nicht wiederherstellbarem Vermögensdiebstahl führen.
Daher lässt sich nach der strengen Logik des Papiers die Bedrohung durch Quantencomputing für Kryptowährungen so zusammenfassen:
Das ECDLP ist das grundlegende schwierige Problem für die Sicherheit digitaler Signaturen. Der Shor-Algorithmus kann das ECDLP auf dem CRQC effizient lösen, bereits offengelegte öffentliche Schlüssel können zur Wiederherstellung privater Schlüssel verwendet werden, Angreifer können gültige digitale Signaturen erzeugen – dadurch wird der bestehende Mechanismus, der das Eigentum durch den privaten Schlüssel nachweist, bedroht.
Aber das Papier betont gleichzeitig ausdrücklich, dass daraus nicht abgeleitet werden kann, dass „Quantencomputing alle Teile der Blockchain leicht angreifen kann“. Verschiedene Protokolle und Funktionen weisen unterschiedliche Quantenresistenz auf. Beispielsweise ist nach Ansicht des Papiers der PoW-Konsens von Bitcoin selbst derzeit kein realistisches Ziel für Quantenangriffe.
02
Wie leistungsstark muss ein Gerät für einen echten Quantenangriff sein?
Dieses Papier vertritt eine wichtige Ansicht: Bei der Bewertung eines Quantencomputers, der secp256k1 angreifen kann, darf man nicht nur auf die „Anzahl der Qubits“ schauen.
Der Grund liegt darin, dass der Vergleich der aktuell fortschrittlichsten Kompilierungsschemata für den Shor-Algorithmus für das n-stellige ECDLP nicht einfach ist – es gibt einen entscheidenden Raum-Zeit-Abwägung (space-time tradeoff). Auf der einen Seite steht die Anzahl der logischen Qubits, die bestimmt, wie groß das CRQC sein muss, um einen Quantenangriff zu starten; auf der anderen Seite steht die Anzahl der Toffoli-Gatter.
Bei der fehlertoleranten Ausführung des Shor-Algorithmus dominieren Toffoli-Gatter normalerweise die gesamten Ressourcenkosten und bestimmen die Gesamtlaufzeit des Algorithmus – damit bestimmen sie auch direkt, ob Angriffe während der Transaktion möglich sind. Das Ergebnis mit der geringsten Anzahl logischer Qubits in der derzeit veröffentlichten Literatur stammt aus einem aktuellen Preprint von Chevignard et al.: Für n=256 schätzen sie, dass nur etwa 1100 logische Qubits erforderlich sind (asymptotisch 3,12n+o(n)).
Aber dieser kleine logische Quantenspeicher geht auf Kosten von mehr als 100 Milliarden Toffoli-Gattern. Eine so große Anzahl von Gattern bedeutet sowohl eine sehr hohe Laufzeit als auch eine große Anzahl physischer Qubits. Denn die tatsächlich benötigte Anzahl physischer Qubits hängt sowohl von der Anzahl der logischen Qubits als auch von der Anzahl der Schaltkreiselemente ab.
Am anderen Ende liegt das Ergebnis mit der niedrigsten Anzahl von Toffoli-Gattern in der bisher veröffentlichten Literatur etwa bei Litinski, mit etwa 200 Millionen Toffoli-Gattern. Es ist zu beachten, dass der Titel des Papiers 50 Millionen und nicht 200 Millionen angibt – das liegt daran, dass es einige Optimierungen berücksichtigt, die die Amortisationskosten für das Lösen mehrerer Instanzen senken, während wir uns hier auf Angriffe auf eine einzelne Instanz konzentrieren. Der Preis, den das Litinski-Schema für die Senkung der Anzahl von Toffoli-Gattern zahlt, ist, dass die Anzahl der logischen Qubits mehr als doppelt so hoch ist wie im Schema von Chevignard et al. Nach Berücksichtigung des Overheads der Quantenfehlerkorrektur wird für das Litinski-Schema auf einer photonischen Quantencomputing-Architektur erwartet, dass etwa 9 Millionen