Bitcoin-Sicherheitslücke aufgedeckt: Quantencomputer-Bedrohung kann Geldbörsen in weniger als 10 Minuten leeren
Teil 1 dieser Serie erklärte, was Quantencomputer eigentlich sind. Nicht nur schnellere Versionen normaler Computer, sondern eine grundlegend andere Art von Maschine, die die seltsamen Regeln der Physik ausnutzt, die nur auf der Skala von Atomen und Teilchen gelten.
Aber wenn man weiß, wie ein Quantencomputer funktioniert, weiß man nicht, wie er von einem Kriminellen dazu genutzt werden kann, Bitcoin zu stehlen. Dazu muss man verstehen, was es eigentlich angreift, wie die Sicherheit von Bitcoin aufgebaut ist und wo genau die Schwachstelle liegt.
Dieser Artikel beginnt mit der Verschlüsselung von Bitcoin und geht bis zu dem neunminütigen Zeitfenster, das nötig ist, um sie zu knacken, wie in Googles aktuellem Artikel über Quantencomputer identifiziert.
Die Einwegkarte
Bitcoin verwendet ein System namens Elliptische-Kurven-Kryptographie, um nachzuweisen, wem was gehört. Jedes Portemonnaie hat zwei Schlüssel. Ein privater Schlüssel, bei dem es sich um eine Geheimzahl mit einer Länge von 256 binären Ziffern handelt, etwa so lang wie dieser Satz. Ein öffentlicher Schlüssel wird aus dem privaten Schlüssel abgeleitet, indem eine mathematische Operation an der spezifischen Kurve namens „secp256k1“ ausgeführt wird.
Betrachten Sie es als eine Einwegkarte. Beginnen Sie an einem bekannten Ort auf der Kurve, über den sich alle einig sind, dem sogenannten Generatorpunkt G (wie in der Tabelle unten dargestellt). Machen Sie eine bestimmte Anzahl von Schritten in einem Muster, das durch die Mathematik der Kurve definiert wird. Die Anzahl der Schritte ist Ihr privater Schlüssel. Wo Sie auf der Kurve landen, ist Ihr öffentlicher Schlüssel (Punkt K im Diagramm). Jeder kann bestätigen, dass Sie an diesem bestimmten Ort gelandet sind. Niemand kann herausfinden, wie viele Schritte Sie unternommen haben, um dorthin zu gelangen.
Technisch gesehen wird dies als K = k × G geschrieben, wobei k Ihr privater Schlüssel und K Ihr öffentlicher Schlüssel ist. Bei der „Multiplikation“ handelt es sich nicht um eine reguläre Multiplikation, sondern um eine geometrische Operation, bei der Sie entlang der Kurve wiederholt einen Punkt zu sich selbst addieren. Das Ergebnis landet an einer scheinbar zufälligen Stelle, die nur Ihre spezifische Zahl k ergeben würde.
Die entscheidende Eigenschaft ist, dass das Vorwärtsgehen einfach ist und das Rückwärtsgehen für klassische Computer praktisch unmöglich ist. Wenn Sie k und G kennen, dauert die Berechnung von K Millisekunden. Wenn Sie K und G kennen und k herausfinden möchten, lösen Sie das, was Mathematiker das Problem des diskreten Logarithmus der elliptischen Kurve nennen.
Es wird geschätzt, dass die bekanntesten klassischen Algorithmen für eine 256-Bit-Kurve länger dauern würden als das Alter des Universums.
Diese einseitige Falltür ist das gesamte Sicherheitsmodell. Ihr privater Schlüssel beweist, dass Sie der Eigentümer Ihrer Münzen sind. Ihr öffentlicher Schlüssel kann sicher weitergegeben werden, da kein klassischer Computer die Mathematik umkehren kann. Wenn Sie Bitcoin versenden, erstellt Ihr Wallet mithilfe des privaten Schlüssels eine digitale Signatur, einen mathematischen Beweis dafür, dass Sie die Geheimnummer kennen, ohne sie preiszugeben.
Shors Algorithmus öffnet die Tür in beide Richtungen
1994 entdeckte ein Mathematiker namens Peter Shor einen Quantenalgorithmus, der die Falltür aufbricht.
Shors Algorithmus löst das Problem des diskreten Logarithmus effizient. Shors Algorithmus verarbeitet die gleiche Mathematik, die ein klassischer Computer länger brauchen würde, als das Universum existiert, in dem, was Mathematiker Polynomialzeit nennen, was bedeutet, dass die Schwierigkeit langsam zunimmt, wenn die Zahlen größer werden, und nicht explosionsartig.
Die Vorstellung davon, wie es funktioniert, geht auf die drei Quanteneigenschaften aus Teil 1 dieser Serie zurück.
Der Algorithmus muss Ihren privaten Schlüssel k finden, wenn Ihr öffentlicher Schlüssel K und der Generatorpunkt G gegeben sind. Er wandelt dies in ein Problem um, die Periode einer Funktion zu finden. Stellen Sie sich eine Funktion vor, die eine Zahl als Eingabe verwendet und einen Punkt auf der elliptischen Kurve zurückgibt.
Wenn Sie ihm fortlaufende Zahlen 1, 2, 3, 4 zuführen, wiederholen sich die Ausgaben schließlich in einem Zyklus. Die Länge dieses Zyklus wird Periode genannt, und sobald Sie wissen, wie oft sich die Funktion wiederholt, lässt sich die Mathematik des diskreten Logarithmusproblems in einem einzigen Schritt lösen. Der private Schlüssel fällt fast sofort heraus.
Das Finden dieser Periode einer Funktion ist genau das, wofür Quantencomputer gebaut sind. Der Algorithmus überlagert sein Eingaberegister (oder in der Quantenmechanik existiert ein Teilchen an mehreren Orten gleichzeitig) und repräsentiert alle möglichen Werte gleichzeitig. Die Funktion wird auf alle gleichzeitig angewendet.
Dann wendet es eine Quantenoperation namens Fourier-Transformation an, die dazu führt, dass die Anzahl der falschen Antworten aufgehoben wird, während die richtigen Antworten verstärkt werden.
Wenn Sie das Ergebnis messen, wird der Zeitraum angezeigt. Aus diesem Zeitraum gewinnt die gewöhnliche Mathematik k zurück. Das ist Ihr privater Schlüssel und damit Ihre Münzen.
Der Angriff nutzt alle drei Quantentricks aus dem ersten Teil. Superposition wertet die Funktion für jede mögliche Eingabe gleichzeitig aus. Durch die Verschränkung werden Eingabe und Ausgabe verknüpft, sodass die Ergebnisse korreliert bleiben. „Interferenz“ filtert das Rauschen, bis nur noch die Antwort übrig bleibt.
Warum Bitcoin auch heute noch funktioniert
Shors Algorithmus ist seit mehr als 30 Jahren bekannt. Der Grund dafür, dass Bitcoin immer noch existiert, ist, dass für den Betrieb ein Quantencomputer mit einer ausreichend großen Anzahl stabiler Qubits erforderlich ist, um die Kohärenz während der gesamten Berechnung aufrechtzuerhalten.
Der Bau dieser Maschine war unerreichbar, aber die Frage war immer, wie groß „groß genug“ ist.
Frühere Schätzungen