Die Wahrheit über Bitcoin und Quantencomputer

Quantencomputer werden nach und nach Wirklichkeit. Die Folgen für Bitcoin und andere Kryptowährungen können dramatisch sein – sind aber längst nicht unbeherrschbar. Ein Team von Wissenschaftlern beschreibt, was Quantencomputer bei Bitcoin anrichten, und wie der Übergang zu quantensicheren Algorithmen gelingen kann.

Noch sind Quantencomputer Science-Fiction. Geräte, die mit einem ungeheuren Aufwand wenig Leistung bringen. Doch es gelingt den Quanten-Ingenieuren, immer mehr Quantenbits – kurz: Qubits – zu verkoppeln. So hat Googles kürzlich den Quantencomputer Bristlecone mit 72 Qubits vorgestellt. Wenn die Anzahl der Qubits weiterhin exponentiell wächst, ist die Vorhersage realistisch, dass Quantencomputer ab etwa 2031 weit genug sind, um zur Gefahr für viele kryptographische Verfahren zu werden.

Es brennt noch nicht, aber es ist kein Fehler, sich schon jetzt mit dem Thema zu beschäftigen. Schließlich sollten Bitcoins kein Verfallsdatum haben. Eine Forschungsgruppe, vor allem vom Centre for Cryptocurrency Research and Engineering beim Imperial College London, beschreibt in einem Paper, wie Quantencomputer Bitcoin angreifen können und wie man sich dagegen wappnen kann.

Die beteiligten Krypto-Algorithmen

Um die Gefahrenlage einzuschätzen, muss man wissen, welche kryptographischen Mechanismen Bitcoin und andere Kryptowährungen verwenden. Diese fallen in zwei Kategorien:

• Signatur-Algorithmen: Diese Verfahren bestehen aus einem öffentlichen und einem privaten Schlüssel. Mit dem privaten Schlüssel signiert man Transaktionen, mithilfe des öffentlichen beweist man, dass die Signatur korrekt ist. Kryptowährungen benutzen üblicherweise Signaturalgorithmen, die auf elliptischen Kurven beruhen. Bei Bitcoin ist dies ECDSA, bei manchen anderen Währungen EdDSA bzw. Schnorr-Signaturen. Unter normalen Bedingungen gilt ECDSA als absolut sicher.
• Hash-Algorithmen: Hash-Algorithmen sind mathematische Einwegfunktionen, die einen Wert deterministisch in einen anderen Wert mit fester Länge transformieren. Am besten, man probiert es auf Hashgenerator.de aus. Bitcoin verwendet Hashfunktionen auf zwei Weisen. Erstens müssen die Miner Hashes mit SHA256 berechnen, um Blöcke zu finden, und zweitens wird der öffentliche Schlüssel des Signatur-Algorithmus sowohl mit SHA256 als auch RIPEMD-160 gehasht, um die Adresse zu bilden. Dieser Schritt ist extrem wichtig, wie wir noch sehen werden.

Quantencomputer haben einen Einfluss auf die Sicherheit dieser kryptographischen Algorithmen. Warum genau, ist sehr schwer zu erklären. Ich zitiere einfach mal die Forscher: „So wie ein klassischer Computer aus Bits gebaut ist, benutzen Quantencomputer Qubits, die zwei fundamentale Zustände haben (0 und 1). Während eine Berechnung läuft, ist der Zustand allerdings eine lineare Kombination von beiden Zuständen (eine Superposition).“ Man kennt das ja von der Quantenphysik, dass ein Teilchen irgendwie in beiden Zuständen ist. Dieser Superzustand kollabiert in einen der beiden fundamentalen Zustände, sobald man das System beobachtet.

„Das bedeutet, ein Quantencomputer mit n Qubits kann intern die gesamte Spannweite von n-bit Nummern präsentieren und alle Rechnungen simultan durchführen. Sobald man es aber misst, wird der Zustand in einen der beiden Basis-Zustände kollabieren und nur eines der Resultate der Berechnungen ausgeben. Quantenalgorithmen versuchen, diese Struktur zu benutzen, um bestimmte Basis-Zustände zu verstärken und ihre Wahrscheinlichkeit zu erhöhen, was das erreichte Ergebnis wiederholbar und schlüssig macht. Für einige Probleme können Quanten-Algorithmen komplexe Probleme deutlich schneller lösen als herkömmliche Algorithmen.“

Und zu diesen Problemen gehören, leider, auch Krypto-Algorithmen.

Wie Quantencomputer die Kryptographie angreifen

Man muss all das nicht im Detail verstehen. Wichtig ist, dass es mehrere Quantenalgorithmen gibt, die kryptographische Verfahren auf neue Weisen angreifen:

• Shors Algorithmus: Dieser Quantenalgorithmus beschleunigt die Faktorisierung von Integern exponentiell. Dies schwächt die Sicherheit von asymetrischen Kryptoverfahren wie RSA und auch ECDSA drastisch. Shor kann benutzt werden, um die von so gut wie allen Kryptowährungen (außer IOTA) verwendeten Signaturalgorithmen zu brechen.
• Grovers Algorithmus: Dieser Quantenalgorithmus kann unstrukturierte Daten durchsuchen und findet mit einer relativ hohen Wahrscheinlichkeit einen Treffer. Mit Grovers Algorithmus kann man Kollissionen von Hash-Algorithmen quadratisch beschleunigen. Dies könnte theoretisch verwendet werden, um Bitcoins zu minen, aber es wird vermutlich noch sehr lange dauern, bis dies die Leistung von Asics übertrifft. Falls überhaupt jemals.

Da vor allem Signaturalgorithmen wie ECDSA von Quantencomputern bedroht sind, werden wir uns diesen zuwenden. Mit herkömmlichen Computern ist ECDSA unmöglich zu brechen. Was passiert aber, wenn Quantencomputer in der Lage sind, sie zu knacken?

Es wird möglich werden, mithilfe des öffentlichen Schlüssels den privaten Schlüssel zu erraten. Dies bedeutet aber nicht, dass eine solche Operation trival oder schnell durchführbar ist. So wird zwar davon ausgegangen, dass Quantencomputer mit 2.000 bis 10.000 logische Qubits in der Lage sein werden, die weit verbreitete RSA-Verschlüsselung zu brechen (bisher erreichen sie 72). Wie lange die Quantencomputer dann dafür brauchen werden, eine Sekunde, zwei Wochen oder ein Jahr, hängt von ihrer Stärke und der Bit-Anzahl der Verschlüsselung ab.

Für die von Bitcoin benutzte ECDSA-Verschlüsselung wird angenommen, dass man etwa 1.800 Qubits braucht. Allerdings muss ein Quantencomputer für jedes effektiv benutzte Qubits zahlreiche physische Qubits bereitstellen, die Fehler korrigieren. Ein Kryptograph auf Bitcointalk schätzt daher, dass ein Quantencomputer mehr als 40.000 physische Qubits brauchen wird, um ECDSA zu brechen. Und selbst wenn dies einmal möglich sein wird, wird es nicht in einer Sekunde passieren, sondern eine Menge von Rechenoperationen brauchen. Wie viele genau weiß ich aber nicht.

Was passiert, wenn es so weit ist?

Aber nehmen wir an, es gibt solche mächtigen Quantencomputer, die mithilfe von Shor ECDSA in einem vernünftigen Zeitraum brechen können. Was dann?

Die gute Nachricht ist: Die Quantencomputer werden weiterhin nicht einfach so Bitcoins stehlen können. Denn Adressen sind kein öffentlicher Schlüssel, sondern ein Hash davon, und diese sind weit weniger anfällig gegen Quantenkryptographie. Ergo: Wer seine Bitcoin auf einer Adresse liegen lässt, läuft nicht Gefahr, dass diese gestohlen werden. Der Rat, eine Adresse nur einmal zu benutzen, macht so plötzlich noch viel mehr Sinn.

Die schlechte Nachricht ist: Es gibt einen weiteren Angriff. Die Forscher nennen ihn die „Entführung von Transaktionen“ nennen. Sobald man eine Transaktion signiert, enthüllt man den öffentlichen Schlüssel. Damit macht man die Adresse für die Zukunft unbrauchbar. Schlimmer noch ist aber, dass ein Quantenhacker unbestätigte Transaktionen kapern kann. Denn wenn die Transaktion im Netz ist, ist der öffentliche Schlüssel bekannt. Dies kann ein Quantencomputer ausnutzen: „So wie bei einem Double-Spend  erzeugt der Angreiffer eine Transaktion, die dieselben Münzen woanders hin überweist und damit die Guthaben des Opfers stiehlt.“

Anders als ein Double-Spend kann eine solche Entführung nicht nur von demjenigen, der bezahlt, ausgeführt werden, sondern von jeder beliebigen dritten Partei. Das Versenden von Bitcoins wird damit zu einem schwer kontrollierbaren Risiko. Die Forscher räumen allerdings ein, dass der Aufwand selbst für starke Quantencomputern nicht trivial ist: „Da der Angreifer nicht nur die alternative Transaktion erschaffen, signieren und propagieren muss, sondern auch zuerst mit dem Shor-Algorithmus den privaten Schlüssel errechnen muss, ist das Timining essenziell für diesen Angriff.“

Je nach Double-Spending-Verfahren hat der Hacker einige Sekunden bis einige Minuten Zeit, um all das auszuführen. Selbst wenn Quantencomputer also in der Lage sind, theoretisch ECDSA zu brechen, bedeutet das noch lange nicht, dass sie schnell genug sind, um in der Praxis auch Transaktionen zu entführen. Es ist durchaus möglich, dass ein solcher Angriff nicht nur 1.800 bis 10.000 Qubits benötigt, sondern sehr viel mehr. Kryptowährungen mit kürzeren Block-Interwallen, etwa Ethereum mit 13 Sekunden, dürften ihm zudem nochmal deutlich besser widerstehen.

Problematisch bleibt der Angriff aber dennoch. Er eröffnet eine Schwachstelle im System, die man systematisch, automatisch und risikofrei ausnutzen kann. Zudem ist es auch möglich, die Attacke für DoS-Angriffe zu nutzen oder damit Selfish-Mining-Angriffe noch einmal schlimmer bzw. für den Miner profitabler zu gestalten. Dies würde nicht nur einzelne Guthaben gefährden, sondern das System Bitcoin an sich.

Wie kann man sich schützen?

Auch wenn es noch lange nicht brennt, kann man nicht früh genug darüber nachdenken, wie man sich auf den Tag vorbereitet, an dem Quantencomputer ECDSA brechen werden. Glücklicherweise gibt es eine Vielzahl an Optionen.

Zum einen kann man kurzzeitig Zeit gewinnen, indem man die bit-Zahl von ECDSA erhöht. Je nach Fortschritt der Quantencomputer kann dies helfen, oder auch nicht. Eine dauerhafte Lösung wird es aber nur sein, wenn man auf einen quantensicheren Algorithmus umsteigt. Die Autoren des Papers zeigen auf, welche Möglichkeiten hierfür bereits bekannt sind:

• Das McElieve-System „widersteht der Dekodierung von unbekannten Codes zur linearen Fehler-Korrektur“ und ist damit quantensicher. Der Preis ist, dass einzelne Signaturen erheblich größer sind (bis zu ein Megabyte).
• Es gibt Methoden zur Hash-basierten Signatur, welche durch Quantencomputer nur in sehr schwachem Umfang angegriffen werden können. Die bekannteste dieser Konzepte ist die Lamport-Diffie-Einmalsignatur, aber auch die von IOTA verwendeten Winternitz-Signaturen gehören zu dieser Familie.
• Schließlich gibt es noch die Möglichkeit, Signaturen auf der Basis von Gitternetzen zu bilden (Lattice-based cryptography). Beispiele sind die aber eher theoretisch ausgearbeiteten Verfahren GGH und NTRUSign.

Es ist wichtig, erklären die Autoren, „dass sich die Bitcoin Community darauf einigt, eine gute Alternative zu implementieren (oder vielleicht auch mehr), die die Kryptographie durch elliptische Kurven als Basis der Signaturen von Transaktionen ersetzt.“

Allerdings wird dies das Problem nicht vollständig lösen: Denn um die Vorteile der quantensicheren Algorithmen zu genießen, müssen alle User ihre Coins auf neue Adressen bewegen. Sollte dies nicht bis zum Tag X geschehen sein – dem Tag, ab dem Quantencomputer unbestätigte Transaktionen entführen können – werden die Bitcoins mehr oder weniger eingefroren sein. Zumindest wird es bei großen Summen unmöglich sein, sie ohne ein erhebliche Risiko zu überweisen.

Die Forscher des Imperial College schlagen nun eine Lösung für dieses Problem vor: Ein Konzept, dass es erlaubt, Bitcoins auch nach diesem Zeitpunkt sicher auf quantensichere Adressen zu verschieben. Das Konzept ist relativ komplex. Es bildet quasi einen Smart Contract, der eine Transaktion so komponiert, dass sie erst nach Ablauf einer relativ langen Zeit und bei Beweis des Besitzes von sowohl einem herkömmlichen als auch einem quantensicheren privaten Schlüssel gültig ist. Mit dieser Methode könnte man wohl auch Guthaben von nicht-quantensicheren Adressen sicher gegen alle Angriffe auf eine quantensichere Adresse überführen.

Wer mehr über die Methode erfahren möchte, sollte das letzte Drittel des Papers lesen. Zeit genug wird er dafür auf jeden Fall haben.