Sollte Krypto Quantencomputing fürchten?

Sachen zu wissen:

– Quantencomputer, eine Spitzentechnologie, birgt mit ihrer unübertroffenen Rechenleistung ein immenses Potenzial zur Revolutionierung der Berechnung.

– Quantum Computing wird, obwohl es noch mindestens einige Jahre von einem großen Durchbruch entfernt ist, aufgrund seiner immensen Datenverarbeitungsfähigkeiten als erhebliche Bedrohung für die Kryptografie wahrgenommen.

– Die potenziellen Auswirkungen von Quantencomputing auf die Kryptografie und sichere Systeme wie den Proof-of-Work von Bitcoin müssen sorgfältig geprüft werden. Als weltweit sicherster Zugang zu Krypto verdienen solche grundlegenden Fragen die volle Aufmerksamkeit von Ledger.

Quantencomputing: Der nächste große Technologiesprung

Die Computer, die wir täglich verwenden, verarbeiten Informationen auf Basis von „Bits“. Ein Bit kann nur einen der folgenden Werte enthalten: 0 oder 1, und kann aneinandergereiht werden, um ein Stück Binärcode zu erstellen. Heute ist alles, was wir mit einem Computer tun, vom Versenden von E-Mails über das Ansehen von Videos bis hin zum Teilen von Musik, dank solcher binären Ziffernfolgen möglich.

Die binäre Natur herkömmlicher Computer erlegt ihrer Rechenleistung Beschränkungen auf. Diese Computer führen Operationen nur Schritt für Schritt aus und haben Mühe, reale Probleme genau zu simulieren. Im Gegensatz dazu arbeitet die physikalische Welt eher auf der Basis von Amplituden als von Binärziffern, was sie viel komplexer macht. Hier kommen Quantencomputer ins Spiel.

1981 sagte Richard Feynman: „Die Natur ist nicht klassisch, und wenn Sie eine Simulation der Natur machen wollen, sollten Sie sie besser quantenmechanisch machen.“ Anstatt Bits zu manipulieren, verwendet Quantencomputer „Quantenbits“ oder Qubits, wodurch Daten wesentlich effizienter verarbeitet werden können. Qubits können null, eins und vor allem eine Kombination aus null und eins sein.

Quantencomputing steht an der Schnittstelle von Physik und Informatik. Um die Dinge ins rechte Licht zu rücken: Ein 500-Qubit-Quantencomputer würde mehr klassische Bits benötigen als … die Anzahl der Atome im gesamten Universum.

Ist Quantum eine Bedrohung für die Kryptografie?

Public-Key-Kryptographie, auch als asymmetrische Kryptographie bezeichnet, bildet die Grundlage für die Sicherheit von Kryptowährungen. Es handelt sich um eine Kombination aus einem öffentlichen Schlüssel (für alle zugänglich) und einem privaten Schlüssel. Die schnellen Berechnungsfähigkeiten von Qubits erhöhen das Potenzial, die Verschlüsselung zu knacken und die Sicherheit der Kryptowährungsindustrie zu stören, wenn das Quantencomputing weiter voranschreitet.

Zwei Algorithmen müssen genau betrachtet werden: Shors und Grovers. Beide Algorithmen sind theoretisch, da es derzeit keine Maschine gibt, um sie zu implementieren, aber wie Sie sehen werden, könnte die potenzielle Implementierung dieser Algorithmen der Kryptografie schaden.

Einerseits ermöglicht der nach Peter Shor benannte Quantenalgorithmus von Shor (1994) die Faktorisierung großer ganzer Zahlen oder die Lösung des Problems des diskreten Logarithmus in Polynomialzeit. Dieser Algorithmus könnte die Public-Key-Kryptographie mit einem ausreichend leistungsfähigen Quantencomputer brechen. Der Algorithmus von Shor würde die überwiegende Mehrheit der heute verwendeten asymmetrischen Kryptographie brechen, da er auf RSA (basierend auf dem ganzzahligen Faktorisierungsproblem) und der Elliptic-Curve-Kryptographie (abhängig vom diskreten Logarithmusproblem in einer Elliptic-Curve-Gruppe) basiert.

Andererseits ist der Algorithmus von Grover (1996) ein Quantensuchalgorithmus, der 1996 von Lov Grover entwickelt wurde und zur Lösung unstrukturierter Suchprobleme verwendet werden kann. Der Grover-Algorithmus beeinträchtigt die Sicherheit symmetrischer Primitive erheblich, ist aber nicht unüberwindbar. Es wird im Allgemeinen empfohlen, die Schlüssellänge zu verdoppeln, um die Quadratwurzelkomplexität dieses Bruchs auszugleichen. Die Verwendung von AES256 anstelle von AES128 wird als ausreichend angesehen, aber es sollte beachtet werden, dass diese Faustregel gilt möglicherweise nur manchmal für alle Chiffren gültig[5]. Was Hash-Funktionen betrifft, die Teil der Landschaft des symmetrischen Primitivs sind, wird angenommen, dass sie keinen Einfluss auf die Kollisionsresistenz haben. Forscher fanden jedoch Fälle des Problems, in denen das ist nicht wahr[6] (z. B. Multi-Target-Preimage-Suche).

Im Wesentlichen stellen beide Algorithmen potenzielle Gefahren für die Kryptografie dar. Der Algorithmus von Shor vereinfacht den Prozess der Faktorisierung großer Zahlen, wodurch es einfacher wird, einen privaten Schlüssel aufzudecken, der mit einem öffentlichen Schlüssel verbunden ist, und der Algorithmus von Grover ist in der Lage, kryptografisches Hashing effizienter zu kompromittieren als aktuelle Computer.

Wann werden verschlüsselungsbrechende Quantencomputer auftauchen?

Lassen Sie uns einige der neuesten Experimente durchgehen und sehen, wie schnell die Forschung voranschreitet. Der erste echte Quantencomputer ist noch weit entfernt, aber das hindert einen globalen Wettlauf nicht daran, die „Quantenüberlegenheit“ zu erreichen. Für Ayal Itzkovitz, geschäftsführender Gesellschafter eines auf Quanten fokussierten VC-Fonds: „Wenn wir vor drei Jahren nicht wussten, ob es überhaupt möglich ist, einen solchen Computer zu bauen, wissen wir jetzt bereits, dass es Quantencomputer geben wird, die dazu in der Lage sein werden etwas anderes machen als klassische Computer.“

Ein Ereignis, von dem wahrscheinlich jeder schon einmal gehört hat, war Googles „Quantum Supremacy Experiment“ im Jahr 2019 mit einem Gerät mit 54 Qubits. Im Jahr 2021 wird die Universität für Wissenschaft und Technologie von China löste eine komplexere Berechnung mit 56 Qubits und erreichte später 60 Qubits. Sein Ziel war es, eine Berechnung durchzuführen, die den Algorithmus von Shor nicht beinhaltete und die ebenso eine Quantenbeschleunigung gegenüber klassischem Rechnen demonstrieren würde.

Definitionsgemäß zeigen diese Experimente keinen Fortschritt in Richtung auf das Brechen der Kryptografie, weil sie entworfen wurden, um die Größe und Komplexität einer Quanten-Integer-Faktorisierung zu vermeiden. Sie zeigen jedoch, dass es nicht länger schwierig ist, mehr Qubits in einen Quantencomputer einzubauen, da verschiedene Hardwarelösungen verfügbar sind. Die „Sycamore“-Chip-Qubits von Google unterscheiden sich grundlegend von den Photonen des USTC. Der nächste wichtige Schritt auf dem Weg zu einem Computer, der die Verschlüsselung knackt, wird im Allgemeinen darin gesehen, fehlertolerante Berechnungen und fehlerkorrigierende Qubits zu erstellen.

Stand der Quantencomputerentwicklung des BSI [1] zeigt, wie weit aktuelle Quantencomputer davon entfernt sind, einen diskreten 160-Bit-Logarithmus (unterste blaue Linie im folgenden Bild) zu brechen. Die Abszisse zeigt, wie die Verringerung der Fehlerrate durch reine Hardwareverbesserungen oder fehlertolerantes Rechnen dazu beiträgt, solche Rechenniveaus zu erreichen, ohne die Anzahl der verfügbaren Qubits (y-Achse) dramatisch zu skalieren.

Die skalierbare Implementierung des Shor-Algorithmus erfordert eine fehlertolerante Berechnung auf einigen tausend logischen Qubits: mindestens 2124 Qubits, um eine elliptische 256-Bit-Kurve wie secp256k1 von Bitcoin zu durchbrechen. für Verbesserte Quantenschaltungen für diskrete Logarithmen mit elliptischen Kurven[7]. Ein „logisches“ Qubit in einem solchen System besteht aus mehreren Qubits, die so konzipiert sind, dass sie als fehlerkorrigierte Version eines einzelnen Qubits funktionieren.

Tausend logische Qubits entsprechen ungefähr mehreren Millionen Qubits, die die Größe eines Fußballfelds abdecken. Eine praktische Demonstration einer solchen fehlertoleranten Berechnung wurde kürzlich durchgeführt Fehlertolerante Steuerung eines fehlerkorrigierten Qubits[2], wobei es sich um ein einzelnes logisches Qubit handelt, dessen Fehlerwahrscheinlichkeit geringer ist als die der Qubits, aus denen es besteht. Die Verbesserung dieses Bereichs wird voraussichtlich schnell folgen, da er zum Schwerpunkt wird.

Fortschritte in dieser Richtung werden sich direkt in eine konkrete Bedrohung der Public-Key-Kryptographie übersetzen. Eine weitere Möglichkeit für schnellen Fortschritt können sich schließlich aus rein algorithmischen Verbesserungen oder reinen Hardware-Entdeckungen ergeben. Stand der Quantencomputerentwicklung des BSI[1] erklärt: „Es kann disruptive Entdeckungen geben, die [den aktuellen Wissensstand] dramatisch verändern würden, die wichtigsten sind kryptografische Algorithmen, die kurzfristig auf nicht fehlerkorrigierten Maschinen ausgeführt werden können, oder dramatische Durchbrüche in der Fehlerrate einiger Plattformen.“ Mit anderen Worten, es ist nicht nur ein Problem, große Computer mit vielen Qubits bauen zu können (eigentlich mehr Qubits zuverlässig zu bauen ist nicht das Hauptaugenmerk, sondern fehlertolerantes Rechnen), sondern auch ein algorithmisches und möglicherweise eine Materialforschung eins.

Während wir diesen Artikel schrieben, veröffentlichte IBM seine Ergebnisse zu einem 127-Qubit-Chip mit einer Fehlerrate von 0.001 und plant die Herausgabe eines 433-Qubit-Chips im nächsten Jahr und eines 1121-Qubit-Chips im Jahr 2023.

Alles in allem bleibt es schwer vorherzusagen, wie schnell ein Quantencomputer zum Leben erwachen wird. Dennoch können wir uns auf Expertenmeinungen zu diesem Thema verlassen: Ein Ressourcenschätzungs-Framework für Quantenangriffe auf kryptografische Funktionen – aktuelle Entwicklungen[3] und Expertenumfrage zum Thema Quantenrisiko[4] zeigen, dass viele Experten darin übereinstimmen, dass wir in 15 bis 20 Jahren einen Quantencomputer zur Verfügung haben sollten.

Zitieren Ein Ressourcenschätzungs-Framework für Quantenangriffe auf kryptografische Funktionen – aktuelle Entwicklungen [3] als Zusammenfassung:

„Die derzeit eingesetzten Public-Key-Schemata wie RSA und ECC werden durch Shors Algorithmus vollständig gebrochen. Im Gegensatz dazu werden die Sicherheitsparameter von symmetrischen Verfahren und Hash-Funktionen durch die bekannten Angriffe – durch „Brute Force“-Suchen mit dem Suchalgorithmus von Grover – höchstens um den Faktor zwei reduziert. All diese Algorithmen erfordern große, fehlertolerante Quantenmaschinen, die noch nicht verfügbar sind. Die meisten Experten sind sich einig, dass sie wahrscheinlich innerhalb von 10 bis 20 Jahren Realität werden.“

Nachdem wir nun untersucht haben, warum Quantenalgorithmen der Kryptographie schaden könnten, wollen wir die erheblichen Risiken analysieren, die für die Krypto- und Web3-Bereiche impliziert sind.

Quantum: Welche Risiken für Kryptowährungen?

Der Bitcoin-Fall:

Beginnen wir mit Pieter Wuilles Analyse des Problems für Bitcoin, das aufgrund von Adressen manchmal als „quantensicher“ gilt Hashes von öffentlichen Schlüsseln und damit nicht preiszugeben.

Nicht in der Lage zu sein, einen privaten Bitcoin-Schlüssel zu knacken, basierend auf der Annahme, dass Hashes dies unmöglich machen, hängt auch davon ab, dass man seinen öffentlichen Schlüssel niemals offenlegt, was auch immer die Mittel sind, was für viele Konten bereits falsch ist.

Unter Bezugnahme auf einen anderen Thread gibt Pieter Wuille eine Vorstellung von den Auswirkungen, wenn etwa 37 % der exponierten Gelder (damals) gestohlen wurden. Bitcoin würde wahrscheinlich tanken, und selbst unexponiert verlieren alle anderen ebenfalls.

Der entscheidende Punkt ist hier die Erwähnung, dass die Fortschritte in Richtung Bau eines Quantencomputers sein werden inkremental: Milliarden von Dollar werden öffentlich in diesen Bereich investiert, und jede Verbesserung findet weltweit Resonanz, wie Googles Quantenüberlegenheitsexperiment gezeigt hat.

Das bedeutet, dass es einige Zeit dauern wird, am Ende mit gefährdeten Geldern fertig zu werden, und alternative Lösungen können richtig ausgelegt werden. Man kann sich vorstellen, eine Gabelung der Kette einzurichten, die post-quantenkryptografische Algorithmen zum Signieren verwendet und es den Leuten ermöglicht, ihre Gelder von der alten Kette auf diese neue Kette zu übertragen, sobald die Nachricht von einem einigermaßen kräftigen Quantencomputer unmittelbar bevorsteht.

Der Ethereum-Fall:

Der Fall von Ethereum ist interessant, da ETH 2.0 einen Backup-Plan für einen katastrophalen Ausfall enthält EIP-2333.

Für den Fall, dass die BLS-Signaturen von ETH2 brechen, was gleichzeitig mit ECDSA passieren würde, da beide angesichts des Algorithmus von Shor gleichermaßen anfällig sind, wird eine Hard Fork der Blockchain ausgeführt, bevor der Verdacht besteht, dass der Algorithmus kompromittiert ist. Dann enthüllen Benutzer ein Vorabbild ihres Schlüssels, das nur legitime Besitzer besitzen können. Dies schließt Schlüssel aus, die durch Brechen einer BLS-Signatur abgerufen werden. Mit diesem Preimage signieren sie eine bestimmte Transaktion, die es ihnen ermöglicht, zur Hard Fork zu wechseln und neue Post-Quantum-Algorithmen zu verwenden.

Dies ist noch kein Wechsel zu einer Post-Quanten-Kette, aber es bietet einen Ausweg. Einige weitere Informationen hier.

Post-Quanten-Signaturen:

Bei der Umstellung auf ein Post-Quantum-Signaturschema zur Verwendung in einer Kryptowährung könnten einige Dinge verbessert werden. Die aktuellen NIST-Finalisten haben ziemlich große Speicheranforderungen. Wenn die Signaturgröße nicht unangemessen größer als die eines ECDSA ist, erhöht die Größe des öffentlichen Schlüssels die Blockgröße und die damit verbundenen Gebühren.

Name des Kandidaten	Größe
Regenbogen	58.3 kB
Dilithium	3.5 kB
Falke	1.5 kB
GeMSS	352 kB
Picknick	12 kB
SPHINCS +	7 kB

Der Falcon-Algorithmus wurde entwickelt, um die Größe des öffentlichen Schlüssels und der Signatur zu minimieren. Allerdings sind seine 1563 Bytes noch weit von den 65 Bytes entfernt, die ECDSA derzeit erreicht.

Kryptografische Techniken können Blockgrößen reduzieren, wie das Zusammenfassen mehrerer Signaturen. Dieses [Multisignaturschema] (https://eprint.iacr.org/2020/520) für die GeMSS-Signatur tut genau das und reduziert die Speicherkosten pro Signatur auf ein akzeptables Maß, trotz der enormen einmaligen Gebühr einer GeMSS-Signatur .

Bedrohungen für kryptografische Hardware:

Signaturgrößen wirken sich auch auf Hardware-Wallets aus, in denen der Speicher stark eingeschränkt ist: Ein Ledger Nano S verfügt über 320 KB Flash-Speicher und nur 10 Kilobyte RAM. Wenn wir plötzlich Rainbow-Signaturen verwenden müssten, wäre es nicht möglich, den öffentlichen Schlüssel auf native Weise zu generieren.

Da jedoch die gesamte Kryptographie-Community von dem Problem betroffen ist, einschließlich der Banken-, Telekommunikations- und Identitätsindustrie, die den größten Teil des Marktes für sichere Chips ausmachen, erwarten wir, dass sich die Hardware schnell an den Bedarf an Post-Quanten-Algorithmen anpassen wird. benutzerfreundliche Hardware und entfernen Sie diesen Speicher (oder manchmal die Leistung) mit der Zeit zusammen.

Die Folgen dieser Brüche sind der Zusammenbruch des derzeitigen Bankensystems, der Telekommunikation und von Identitätssystemen wie Pässen. Was tun angesichts einer solchen apokalyptischen Zukunft? Fürchte dich nicht, oder ein bisschen, denn Kryptographen haben es abgedeckt.

Gibt es eine Heilung, Doktor?

Während unsere heutigen Computer Tausende von Jahren brauchen würden, um die Public-Key-Kryptographie zu knacken, würden voll entwickelte Quantencomputer dies in Minuten oder Stunden schaffen. „Quantensicherheits“-Standards werden unweigerlich erforderlich sein, um dieser Bedrohung entgegenzuwirken und die Sicherheit unserer zukünftigen Finanztransaktionen und Online-Kommunikation zu gewährleisten.

An der sogenannten „Post-Quanten-Kryptografie“ wird bereits gearbeitet das würde möglicherweise sein „kompatibel mit heutigen Computern, die aber auch in Zukunft Angreifern von Quantencomputern standhalten werden.“ Die Post-Quanten-Kryptographie bringt Algorithmen und mathematische Standards auf die nächste Stufe und ermöglicht gleichzeitig die Kompatibilität mit aktuellen Computern.

Das NIST-Wettbewerb eigens dafür geschaffen, hat bereits die dritte Runde erreicht und eine Liste potenzieller Standardisierungskandidaten erstellt. Der Post-Quantum-Sicherheitskonferenz wurde bereits 2006 gestartet, um kryptografische Primitive zu untersuchen, die bekannten Quantenangriffen widerstehen würden.

Die Grundlagen dieser Forschung stammen von Expertenwarnungen, dass verschlüsselte Daten bereits gefährdet sind, kompromittiert zu werden, da die ersten praktischen Quantencomputer voraussichtlich in den nächsten 15 Jahren auf den Markt kommen werden.
Diese Art von Angriff wird als „Daten jetzt horten, später angreifen“ bezeichnet, bei der eine große Organisation verschlüsselte Informationen von anderen Parteien speichert, die sie knacken möchte, und wartet, bis ein ausreichend leistungsstarker Quantencomputer dies zulässt. Dies ist zum Beispiel die gleiche Sorge dieses Artikels: „Die USA sind besorgt, dass Hacker heute Daten stehlen, damit Quantencomputer sie in einem Jahrzehnt knacken können“, aber es sagt nicht aus, was staatliche Akteure in der gleichen Weise tun könnten. Sie haben viel mehr Ressourcen und Speicherplatz zur Verfügung.

Abschließende Gedanken

Die genaue Geschwindigkeit, mit der verschlüsselte Kommunikation für die Quantenforschung angreifbar wird, bleibt schwer zu bestimmen.

Eines ist sicher: Obwohl im Quantencomputing erhebliche Fortschritte erzielt werden, sind wir noch weit davon entfernt, die Fähigkeit zu besitzen, die Kryptografie mit diesen Maschinen zu knacken. Die Wahrscheinlichkeit eines plötzlichen Durchbruchs, der zum Entwurf eines solchen Computers führt, ist minimal, was uns Zeit gibt, uns auf seine Ankunft vorzubereiten. Wenn es über Nacht passieren würde, wären die Auswirkungen katastrophal und würden nicht nur Kryptowährungen, sondern eine Vielzahl von Sektoren betreffen.

Glücklicherweise sind Lösungen, einschließlich Post-Quanten-Kryptographie, verfügbar, um der Bedrohung zu begegnen, aber die Kryptoindustrie muss noch die Dringlichkeit erkennen, in diese Maßnahmen zu investieren.

Der Kryptowährungsmarkt muss die Quantenentwicklungen genau beobachten. In Bezug auf die Hardware gibt es wenig Anlass zur Sorge, da wir mit der Entwicklung neuer sicherer Elemente rechnen, um die Nachfrage zu befriedigen. Es ist entscheidend, über die neuesten Fortschritte bei Seitenkanal- und fehlerresistenten Versionen dieser Algorithmen auf dem Laufenden zu bleiben, um unseren Benutzern eine zuverlässige Implementierung zu bieten.