Post-Quanten-Kryptografie – Neuer Algorithmus „in 60 Minuten verschwunden“

Wir haben über PQC geschrieben, kurz für Post-Quanten-Kryptographie, schon mehrfach.

Falls Sie die ganze Medienaufregung der letzten Jahre über das sogenannte Quantencomputing verpasst haben …

… es ist (wenn Sie mir verzeihen, was einige Experten wahrscheinlich als rücksichtslose Vereinfachung ansehen werden) eine Möglichkeit, Computergeräte zu bauen, die den Überblick behalten können mehrere mögliche Ergebnisse einer Berechnung gleichzeitig.

Mit viel Sorgfalt und vielleicht ein bisschen Glück können Sie einige Arten von Algorithmen so umschreiben, dass sie die richtige Antwort finden, oder zumindest eine ganze Reihe falscher Antworten richtig verwerfen, ohne jedes mögliche Ergebnis ausprobieren und testen zu müssen Einer nach dem anderen.

Mit einem Quantencomputergerät sind zwei interessante kryptoanalytische Beschleunigungen möglich, vorausgesetzt, ein entsprechend leistungsfähiges und zuverlässiges Gerät kann tatsächlich konstruiert werden:

• Grovers Quantensuchalgorithmus. Wenn Sie eine zufällig geordnete Reihe von Antworten durchsuchen möchten, um zu sehen, ob Ihre auf der Liste steht, würden Sie im schlimmsten Fall erwarten, die gesamte Liste durchzupflügen, bevor Sie eine endgültige Antwort erhalten. Wenn Sie beispielsweise den 128-Bit-AES-Entschlüsselungsschlüssel zum Entschlüsseln eines Dokuments finden möchten, müssen Sie die Liste aller möglichen Schlüssel durchsuchen, beginnend bei 000..001, ..2, ..3, und so weiter, bis hin zu FFF..FFF (16 Bytes Wert von FF), um sicher zu sein, das Problem zu lösen. Mit anderen Worten, Sie müssen ein Budget haben, um alle 2 auszuprobieren¹²⁸ mögliche Schlüssel, bevor Sie entweder den richtigen Schlüssel finden oder feststellen, dass keiner vorhanden ist. Grovers Algorithmus behauptet jedoch, bei einem ausreichend großen und leistungsstarken Quantencomputer in der Lage zu sein, dasselbe Kunststück mit dem zu vollbringen Quadratwurzel des üblichen Aufwands, wodurch der Code theoretisch in nur 2 geknackt wird⁶⁴ versucht es stattdessen.
• Shors Quantenfaktorisierungsalgorithmus. Einige zeitgemäße Verschlüsselungsalgorithmen verlassen sich darauf, dass die Multiplikation zweier großer Primzahlen schnell möglich ist, während es so gut wie unmöglich ist, ihr Produkt wieder in die beiden Ausgangszahlen zu teilen. Um ein Gefühl dafür zu bekommen, versuche 59×87 mit Stift und Papier zu multiplizieren. Es kann ungefähr eine Minute dauern, um es herauszubekommen (5133 ist die Antwort), aber es ist nicht so schwer. Versuchen Sie es jetzt andersherum. Teilen Sie, sagen wir, 4171 wieder in seine zwei Faktoren. Viel härter! (Es ist 43×97.) Stellen Sie sich nun vor, dies mit einer Zahl zu tun, die 600 Ziffern lang ist. Grob gesagt müssen Sie versuchen, die 600-stellige Zahl durch jede mögliche 300-stellige Primzahl zu teilen, bis Sie den Jackpot knacken oder feststellen, dass es keine Antwort gibt. Shors Algorithmus verspricht jedoch, dieses Problem mit dem zu lösen Logarithmus des üblichen Aufwands. Daher sollte das Faktorisieren einer Zahl von 2048 Binärziffern nur doppelt so lange dauern wie das Faktorisieren einer 1024-Bit-Zahl, nicht doppelt so lange wie das Faktorisieren einer 2047-Bit-Zahl, was eine enorme Beschleunigung darstellt.

Der Bedrohung entgegenwirken

Der Bedrohung durch Grovers Algorithmus kann einfach entgegengewirkt werden, indem die Größe der von Ihnen verwendeten Zahlen erhöht wird, indem Sie sie quadrieren, was bedeutet, dass Sie die Anzahl der Bits in Ihrem kryptografischen Hash oder Ihrem symmetrischen Verschlüsselungsschlüssel verdoppeln. (Mit anderen Worten, wenn Sie denken, dass SHA-256 im Moment in Ordnung ist, würde die Verwendung von SHA-512 stattdessen eine PQC-resistente Alternative darstellen.)

Aber Shors Algorithmus lässt sich nicht so einfach kontern.

Die Größe eines öffentlichen Schlüssels von 2048 Bit müsste exponentiell erhöht werden, nicht einfach durch Quadrieren, sodass Sie anstelle eines Schlüssels von 2 × 2048 = 4096 Bit entweder einen neuen Schlüssel mit der unmöglichen Größe von 2 benötigen würden²⁰⁴⁸ Bits…

… oder Sie müssten eine völlig neue Art von Post-Quanten-Verschlüsselungssystem übernehmen, auf das Shors Algorithmus nicht zutrifft.

Nun, das US-Standardisierungsgremium NIST hat eine PQC-„Wettbewerb“ seit Ende 2017.

Der Prozess war offen für alle, alle Teilnehmer waren willkommen, alle Algorithmen wurden offen veröffentlicht und eine öffentliche Überprüfung war nicht nur möglich, sondern auch möglich aktiv gefördert:

Aufforderung zur Einreichung von Vorschlägen. [Geschlossen am 2017]. […] Es ist beabsichtigt, dass die neuen Public-Key-Kryptografiestandards eine oder mehrere zusätzliche, nicht klassifizierte, öffentlich offengelegte digitale Signaturen, Public-Key-Verschlüsselung und Schlüsselerstellungsalgorithmen spezifizieren, die weltweit verfügbar sind und in der Lage sind, sensible Regierungsinformationen zu schützen bis weit in die absehbare Zukunft, auch nach dem Aufkommen von Quantencomputern.

Nach drei Einreichungs- und Diskussionsrunden Das gab NIST bekannt, am 2022, dass es vier Algorithmen ausgewählt hatte, die es mit sofortiger Wirkung als „Standards“ betrachtete, alle mit wohlklingenden Namen: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON und SPHINCS+.

Der erste (CRYSTALS-KYBER) wird als sogenanntes a verwendet Schlüsselvereinbarungsmechanismus (KEM), wo zwei Enden eines öffentlichen Kommunikationskanals sicher einen einmaligen privaten Verschlüsselungsschlüssel zusammenstellen, um die Daten einer Sitzung vertraulich auszutauschen. (Einfach gesagt: Schnüffler bekommen einfach zerkleinerten Kohl, damit sie das Gespräch nicht belauschen können.)

Die anderen drei Algorithmen werden für verwendet Digitale Signaturen, wodurch Sie sicherstellen können, dass die Daten, die Sie auf Ihrer Seite erhalten, genau mit denen übereinstimmen, die der Absender auf der anderen Seite eingegeben hat, wodurch Manipulationen verhindert und die Integrität sichergestellt werden. (Einfach gesagt: Wenn jemand versucht, die Daten zu beschädigen oder zu manipulieren, werden Sie es wissen.)

Mehr Algorithmen benötigt

Gleichzeitig mit der Bekanntgabe der neuen Standards kündigte NIST auch a vierte Runde seiner Konkurrenz und stellt weitere vier Algorithmen als mögliche alternative KEMs vor. (Denken Sie daran, dass wir zum Zeitpunkt des Verfassens dieses Artikels bereits drei zugelassene digitale Signaturalgorithmen zur Auswahl haben, aber nur ein offizielles KEM.)

Diese waren: BIKE, Classic McEliece, HQC und SIKE.

Interessanterweise die McEliece-Algorithmus wurde bereits in den 1970er Jahren vom amerikanischen Kryptographen Robert Mc Eliece erfunden, der 2019 starb, lange nachdem der Wettbewerb von NIST bereits im Gange war.

Es hat sich jedoch nie durchgesetzt, da es im Vergleich zur populären Alternative des Tages, dem Diffie-Hellman-Merkle-Algorithmus (DHM, oder manchmal nur DH), riesige Mengen an Schlüsselmaterial erforderte.

Leider einer der drei Round-Four-Algorithmen, nämlich SIKE, scheint geknackt worden zu sein.

In einem hirnverdrehenden Papier mit dem Titel EIN EFFIZIENTER SCHLÜSSELWIEDERHERSTELLUNGSANGRIFF AUF SIDH (VORLÄUFIGE VERSION), scheinen die belgischen Kryptografen Wouter Castryk und Thomas Decru dem SIKE-Algorithmus einen tödlichen Schlag versetzt zu haben

Falls Sie sich fragen, SIKE ist die Abkürzung für Supersinguläre Isogeny-Schlüsselkapselung, und SIDH steht für Supersinguläre Isogenie Diffie-Hellman, eine spezifische Verwendung des SIKE-Algorithmus wobei zwei Enden eines Kommunikationskanals einen DHM-ähnlichen „Cryptodance“ durchführen, um eine Reihe öffentlicher Daten auszutauschen, die es jedem Ende ermöglichen, einen privaten Wert abzuleiten, der als einmaliger geheimer Verschlüsselungsschlüssel verwendet werden kann.

Wir werden hier nicht versuchen, den Angriff zu erklären; wir werden nur wiederholen, was das Papier behauptet, nämlich dass:

Ganz grob gesagt umfassen die Eingaben hier die öffentlichen Daten, die von einem der Teilnehmer an der Kryptotanz zur Schlüsselerstellung bereitgestellt werden, zusammen mit den vorher festgelegten (und daher öffentlich bekannten) Parametern, die im Prozess verwendet werden.

Aber die extrahierte Ausgabe (die Informationen, die als die Isogenie φ oben) soll der nie offenbarte Teil des Prozesses sein – der sogenannte private Schlüssel.

Mit anderen Worten, allein aus öffentlichen Informationen, wie den Daten, die während der Schlüsseleinrichtung offen ausgetauscht werden, behaupten die Kryptographen, den privaten Schlüssel eines der Teilnehmer wiederherstellen zu können.

Und sobald Sie meinen privaten Schlüssel kennen, können Sie sich einfach und unbemerkt als ich ausgeben, sodass der Verschlüsselungsprozess unterbrochen wird.

Anscheinend benötigt der Schlüsselknackalgorithmus etwa eine Stunde, um seine Arbeit zu erledigen, wobei nur ein einziger CPU-Kern mit der Art von Rechenleistung verwendet wird, die Sie in einem alltäglichen Laptop finden würden.

Das ist gegen den SIKE-Algorithmus, wenn er so konfiguriert ist, dass er Level 1 erfüllt, NISTs grundlegende Stufe der Verschlüsselungssicherheit.

Was ist zu tun?

Nichts!

(Das ist die gute Nachricht.)

Wie die Autoren des Papiers vorschlagen, nachdem sie festgestellt haben, dass ihr Ergebnis noch vorläufig ist, "Mit dem aktuellen Stand der Dinge scheint SIDH für jede öffentlich generierte Basiskurve vollständig gebrochen zu sein."

(Das ist die schlechte Nachricht.)

Da der SIKE-Algorithmus jedoch noch nicht offiziell zugelassen ist, kann er jetzt entweder angepasst werden, um diesen speziellen Angriff zu vereiteln (was die Autoren zugeben, dass dies möglich sein könnte) oder einfach ganz fallen gelassen werden.

Was auch immer letztendlich mit SIKE passiert, dies ist eine hervorragende Erinnerung daran, warum der Versuch, eigene Verschlüsselungsalgorithmen zu erfinden, voller Gefahren ist.

Es ist auch ein deutliches Beispiel dafür, warum proprietäre Verschlüsselungssysteme die auf die Geheimhaltung des Algorithmus selbst angewiesen sind zur Aufrechterhaltung ihrer Sicherheit sind im Jahr 2022 einfach nicht akzeptabel.

Wenn ein PQC-Algorithmus wie SIKE mehr als fünf Jahre lang von Experten aus der ganzen Welt persual und sondiert wurde, obwohl er ausdrücklich offengelegt wurde, damit er einer öffentlichen Prüfung unterzogen werden könnte …

… dann brauchen Sie sich nicht zu fragen, wie gut Ihre selbst erstellten, unsichtbaren Verschlüsselungsalgorithmen wahrscheinlich abschneiden werden, wenn sie in die Wildnis entlassen werden!

---