Die Wahrheit über Bitcoin und Quantencomputer

Ein Waver des D-Wave Quantencomputers. Sieht gar nicht so abenteuerlich aus. Bild von Steve Jurvetson via flickr.com. Lizenz: Creative Commons

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.

About Christoph Bergmann (1235 Articles)
Das Bitcoinblog wird von bitcoin.de gesponsort, ist inhaltlich aber unabhängig und gibt die Meinung des Redakteurs Christoph Bergmann wieder. Wenn Ihnen das Blog gefällt, freuen wir uns über Spenden. Sie können Bitcoin oder Bitcoin Cash an die folgende Adresse spenden: 1BvayiASVCmGmg4WUJmyRHoNevWWo5snqC Weitere Adressen (bech32, SegWit, Litecoin, Ethereum) finden Sie HIER. Dort erfahren Sie auch, wie Sie das Bitcoinblog anderweitig unterstützen können, etwa durch Affiliate-Links.

13 Comments on Die Wahrheit über Bitcoin und Quantencomputer

  1. Christoph // 28. March 2018 at 19:19 // Reply

    Danke für den interessanten Beitrag. Die Quantencomputer dürften sicher diverse andere heutige Verschlüsselungssysteme herausfordern…

  2. Fabian Suhr // 28. March 2018 at 20:09 // Reply

    Das Problem mit den Quantencomputern ist doch die permanente “Zerstörung der Kohärenz” bei deren irgendeiner praktischer Nutzung.

    Sprich, sobald man von denen wissen will, was denn nun das (Zwischen-)Ergebnis der Berechnung ist, ist das eine Messung, eine Wechselwirkung des schön vor sich hin rechnenden theoretischen Quantencomputers mit seiner Umgebung, die sofort zur Dekohärenz des Systems führt und die schönen Quibits zerstört. War die Quantenberechnung zum Zeitpunkt der Abfrage nicht fertig, ist sie nun “kaputt” und alles muss ganz von vorne angefangen werden.

    Hinzu kommt, dass die Qubits auch ohne jegliches Abfragen, “von alleine” ihre Kohärenz verlieren und man nie so richtig weiß, ob sie noch “richtig ticken” oder gerade nur noch Fehler und Quatsch-Ergebnisse produzieren. Es wird meiner Meinung nach noch sehr lange dauern, bis man mit solchen Systemen irgendwas Brauchbares wirklich berechnen kann.
    Es kann genauso gut sein, dass die genannten Probleme fundamental sind und trotz zahlreicher Tricks, die die Wissenschaftler schon seit Jahren versuchen, nie wirklich gelöst werden können.

    Dekohärenz ist fundamental. Nach den aktuellen wissenschaftlichen Erkenntnissen liegt die Ursache dafür in der Gravitation – einer Wechselwirkung, die immer und überall stattfindet und sich nicht durch wissenschaftliche Tricks beseitigen oder abschirmen lässt. Kann man die Gravitation mal eben kurz abstellen, neutralisieren, überwinden?

    Genauso kommen mir die Versuche und Meldungen zu dem Thema vor, einen wirklich funktionierenden, zu irgendwas tauglichen Quantencomputer zu bauen. Seit Jahren hört man praktisch entweder dieselben oder neue Märchen von den angeblichen Fortschritten auf dem Gebiet der “Gravitations-Beseitigung” (bildlich gesprochen).

    Ich mache mir da um die Angriffe auf Verschlüsselungen durch Quantencomputer wenig sorgen. Wenn dann eher durch Algorithmus-Schwachstellen, Sicherheitslücken, Hash-Kollisionen. So wie bei IOTA übrigens – was nützten einem Winternitz-Signaturen, wenn der Chef-Entwickler dann eine dilettantische, selbstgeschriebene Curl-Hash-Funktion implementiert, die Kollisionen produziert.

    • Danke, für die Erläuterung der Koheränz. Das prinzipielle Problem war mir im Grunde bekannt, dass es etwas mit der Gravitation zu tun hat nicht. Man lernt nie aus.

      Ich habe mir auch immer überlegt, dass wenn man das Problem für >10000QBits lösen kann, man auch durch Wände tunneln kann und der Heisenberg-Kompensator wäre wohl auch möglich.
      Ich sehe genauso: Quantencomputer sind wie die Fusionsgeneratoren bei der Energieerzeugung. Theoretisch ist alles klar, in der Praxis gibt es dann aber grundlegende Probleme.
      Selbst wenn es irgendjemand schafft: Im Vergleich zu den umfassenden wirtschaftlichen Verwerfungen durch den Wegfall der assymetrischen Krypto sind geknackte Bitcoinadressen ein laues Lüftchen…

    • Ich dachte, das Problem wäre fundamentaler. Aber wenn es nur an der Gravitation liegt, dann ist das längst gelöst: Parabelflüge. Die simulieren Schwerelosigkeit für ein paar Sekunden. Quantencomputer sollen dafür schnell genug sein, nicht wahr?

      Weil ich eh grad schreibe: D-Wave war schonmal Thema und der D-Wave sieht deshalb nicht ungewöhnlich aus, weil er KEIN Quantencomputer ist!
      らんま

    • Name required // 31. March 2018 at 18:29 // Reply

      Vermutlich wird die Quanten-Computerei nur wirklich brauchbare Ergebnisse produzieren, wenn man die Wahrscheinlichkeit abschafft. Wie das gehen soll, steht allerdings noch “in den Sternen” (sic!). 😉

    • Coinling // 4. April 2018 at 9:35 // Reply

      Was kann man denn gegen eine iota „Kollision“ unternehmen? Mir wurden so coins gestohlen…

  3. Name required // 31. March 2018 at 18:33 // Reply

    @ Christoph: Hier noch ein relativ bodenständiger Hinweis: Intervall schreibt man mit “v”, nicht mit “w”. Wie oft müssen wir es Dir noch eintrichtern? lol 🙂

    https://www.duden.de/rechtschreibung/Intervall

    • verfl… Immer wenn ich das schreibe, denke ich mir: Da war doch was! Also schreibe ich es im Deutschen anders als im Englischen und lande bei w — so kann man sich selbst verarschen 🙂 Vielleicht lerne ich es ja noch —

      • Ranma // 3. April 2018 at 0:23 //

        Ist es dir ein Bedürfnis, dich so gängeln zu lassen? Auf deinem eigenem Blog? Ich würde Name required verstehen, wenn du Mißverständnisse verursachen würdest…
        らんま

      • Naja, ich ärgere mich eben, wenn ich Wörter falsch schreibe, die ich eigentlich gut kenne …

  4. super Artikel, die Befürchtungen bzgl. Quantencomputer und Kryptograhie hört man ja allenthalben
    ich denke auch, dass es Kryptowährungen wohl erst erwischen wird, wenn viele industriell verwendete kryptograpie schon ausgedient hat, man muss sich halt auch bei BTC rechtzeitig Gedanken über Lösungen machen und – der kritische Punkt – zu einem Konsens kommen 😉

    Der Vergleich mit Kerfusion zieht mMn nicht. Das Problem der Kernfusion ist die Zykluszeit von Experienten. Wenn man Milliarden in ein Experiment stecken muss und der Bau der nächsten Stufe dann ein Jahrzehnt dauert, dann kommt man logischerweise nicht schnell voran. Die Stufen von Quantencomputern werden dagegen im Halbjahrestakt entwickelt und getestet, ganz andere Baustelle. Der genannte grobe kritische Termin von 2030 für Kryptos könnte schon so hinkommen, denke ich.

  5. Vielen Dank für den Beitrag,
    Trotz all dieser Ängste finde ich, dass Bitcoin-Mining relativ sicher ist, da in naher Zukunft die Mining-Hardware noch viel leistungsfähiger als Quantencomputer sein wird.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s