Wann lohnt sich der Quantensprung? Post-Quanten-Kryptographie 

Asymmetrische Kryptographie ist heute weit verbreitet. Algorithmen, die heute noch als sicher gelten, können von den Quantencomputern von morgen gebrochen werden. 

Asymmetrische Kryptographie-Algorithmen basieren auf mathematischen Problemen (Primfaktorzerlegung oder Berechnung des diskreten Logarithmus), die als schwer zu lösen gelten. Bereits Anfang der 90er-Jahre hat Peter Shor den nach ihm benannten Algorithmus entwickelt, mit dem die genannten mathematischen Probleme auf einem Quantencomputer effizient berechnet werden können. Um das zu verdeutlichen: Um eine n-Bit Zahl zu faktorisieren, sind etwa 2n Qubits nötig. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) fordert bei der Verwendung von RSA eine Schlüssellänge von mindestens 2000 Bit, für den Einsatzzeitraum über das Jahr 2022 hinaus sogar mindestens 3000 Bit. Das bedeutet, dass man bei der Verwendung von RSA mit einer Schlüssellänge von 2048 Bit schon theoretisch einen Quantencomputer mit über 4000 Qubit braucht. Praktisch sind wegen technischer Herausforderungen beim Bau von Quantencomputern wesentlich mehr Qubits notwendig. Der Physikforscher Michele Mosca schätzt, dass es mit einer Wahrscheinlichkeit von 50 % einen effizienten Quantencomputer bereits ab 2030 geben wird. 

Aber nicht nur asymmetrische Verschlüsselungs- und Signaturverfahren sind gefährdet, sondern auch symmetrische Verschlüsselungsverfahren und Hashfunktionen. Denn mit dem ebenfalls in den 90er-Jahren entwickelte Such-Algorithmus „Grover“ kann die Komplexität von Suchproblemen auf ungeordnete Daten auf die Wurzel der klassischen Komplexität reduziert werden. Infolgedessen müssen die Schlüssellängen angepasst werden. Es wird heute schon bei Neuentwicklungen davon abgeraten, AES-128 zu verwenden. Stattdessen sollte AES-256 genutzt werden, da davon ausgegangen wird, dass die Verwendung einer Schlüssellänge von 256 Bit langfristig einen hinreichenden Schutz gegen Quantencomputer-Angriffe bietet. 

Auch wenn der Durchbruch in der Quanteninformatik noch einige Jahre auf sich warten lässt, müssen sich Organisationen rechtzeitig auf den reibungslosen Übergang zu quantensicheren Systemen vorbereiten. Die Auswahl geeigneter Algorithmen sowie das Umstellen auf quantensichere Systeme kann eine besondere Herausforderung für viele Organisationen sein. In den letzten Jahren wurden enorme Fortschritte in der Quanteninformatik erzielt, so dass der erste Quantencomputer, der in der Lage ist, asymmetrische Kryptographie-Verfahren zu brechen, in wenigen Jahren zur Verfügung stehen könnte. Organisationen, die die gefährdeten Verfahren verwenden, um Daten mit langen Lebenszyklen zu schützen, müssen sich am besten jetzt schon um eine geeignete Alternative kümmern. Dazu zählen z. B. Gesundheitsdaten, die 10 Jahre sicher aufbewahrt werden müssen. Wenn 2030 der erste Quantencomputer zur Verfügung stehen sollte, könnten die Angreifer die verschlüsselten Daten bereits jetzt abfangen und dann entschlüsseln (hack now – decrypt later). Für Signaturen drängt die Zeit noch weniger, denn Angriffe auf frühere Kommunikation sind nicht möglich. 

Die US-Bundesbehörde National Institute of Standards and Technology (NIST), die bereits in der Vergangenheit für den Standardisierungsprozess bekannter kryptographischer Verfahren (wie z. B. AES) zuständig war, ist bereits seit 2016 auf der Suche nach neuen kryptographischen Standards, die gegen Quantencomputer resistent sind.  

Das NIST hat bereits im Juni 2022 erste Post-Quanten-Kryptographie-Verfahren zur öffentlichen Kommentierung standardisiert. Als Beispiel wurde CRYSTALS-Kyber ausgewählt, das auf dem Learning with Error (LWE) Problem basiert, welches auf Probleme in mathematischen Gittern zurückzuführen ist. Dieses Forschungsfeld ist jedoch noch recht jung. 

Ebenfalls im Juni 2022 hat die Runde 4 des Auswahlprozesses bei NIST begonnen. Einer der Finalisten ist das codebasierte Verfahren McEliece, welches auf fehlerkorrigierenden Codes basiert. Im Gegensatz zu den gitterbasierten Verfahren wurde das McEliece-Verfahren bereits im Jahr 1973 entwickelt und konnte somit bereits lange ausgiebig erforscht werden. Jedoch ist die Schlüsselerzeugung mit einem hohen Aufwand verbunden, da große Matrizen verarbeitet werden müssen. Dafür sind die Ver- und Entschlüsselungsalgorithmen extrem schnell und der Ciphertext ist bisher der kleinste aller NIST-Post-Quanten-Kryptographie-Kandidaten. 

Auch das BSI hat bereits erste Empfehlungen ausgesprochen. Dazu zählen z. B. die Entwicklung von kryptoagilen Lösungen und die Verwendung von Post-Quanten-Kryptographie Algorithmen in hybrider Form, also in Kombination mit klassischen kryptographischen Algorithmen, da viele Verfahren noch sehr jung und wenig erforscht sind. Dies führt zu den nächsten Herausforderungen. Kryptographische Protokolle müssen weiterentwickelt werden und die Public-Key-Infrastruktur muss in der Lage sein, Zertifikate zu verarbeiten, die sowohl die längeren klassischen Schlüssel als auch die quantensicheren Schlüssel enthalten. 

Unsere Experten der HiSolutions AG analysieren für Sie Ihre spezifischen Systeme, die kryptographische Verfahren verwenden, um die notwendigen Änderungen für die Migration zu Post-Quanten-Kryptographie-Lösungen unter Berücksichtigung spezifischer Anforderungen zu identifizieren. Dabei entwickeln wir für Sie geeignete Migrations- und Übergangslösungen. Ebenfalls möchten wir das Bewusstsein für die Problematik schärfen, die sich aus der Entwicklung der Quanteninformatik ergeben. 

Für mehr Informationen zum Quantencomputer und den Gefährdungen wie Lösungsmöglichkeiten, siehe auch dieses Dokument des BSI

Da waren‘s nur noch sieben: Nächster quantensicherer Algorithmus (SIKE) gebrochen

Ein erfolgreicher Angriff auf den Verschlüsselungsalgorithmus SIKE (Supersingular Isogeny Key Encapsulation) hat die Zahl der Verfahren, in die das US-amerikanische Normungsinstitut NIST noch Hoffnung in Bezug auf Sicherheit vor dem Quantencomputer setzt, auf sieben reduziert. Damit sind nun bereits über 90 % der Kandidaten ausgeschieden: Motiviert von den offenen Wettbewerben zur Wahl von AES (1997-2000) und SHA-3 (2007-2012) hatte es 2017 ganze 69 Einreichungen für Post Quantum Cryptography (PQC) gegeben, die in der Folge immer weiter zusammenschrumpften.

SIKE fiel dabei ganz sang- und klanglos einem älteren Modell eines Nicht-Quanten-Rechners zum Opfer – und einigen mathematischen Tricks aus dem jungen Forschungsfeld der Isogenie-Graphen. Dies macht noch einmal das Risiko deutlich, welches in der Verwendung neuer Mathematik für die Kryptographie liegt. Andererseits besteht inzwischen starker Handlungsdruck, quantensichere Verfahren zu standardisieren. Denn ein ausreichend großer Quantencomputer wird wahrscheinlich in den nächsten fünf bis zwanzig Jahren alles an Kryptographie knacken, was wir im Großmaßstab im Einsatz haben, vor allem sämtliche asymmetrische (und damit auch hybride) Verschlüsselung und alle digitalen Signaturen.

Mit dem Scheitern der Isogenie als Quelle für mögliche PQC sind wir nun vorerst auf Gedeih und Verderb den verbleibenden drei Forschungsrichtungen ausgeliefert: Gitter, fehlerkorrigierende Codes und Hashsignaturen. Gerade weil jedes der betrachteten Verfahren seine spezifischen Vor- und (zum Teil gravierenden) Nachteile mitbringt, können wir nur hoffen, dass von den noch im Rennen befindlichen Kandidaten möglichst viele auch die Angriffe der nächsten Jahre heil überstehen werden.

https://t3n.de/news/algorithmus-quantencomputern-1489626/

Post für das Quantum – BSI-Handlungsempfehlungen zur Post-Quantum-Kryptografie

Laut BSI sollten nicht mehr die Fragen im Vordergrund stehen, ob und wann es einen leistungsfähigen Quantencomputer geben wird, sondern wie wir die Migration zu quantensicheren Verfahren heute schon gestalten können, um auf der sicheren Seite zu sein. Dies beschreiben die neuen Handlungsempfehlungen „Migration zu Post-Quanten-Kryptografie“ auf netto sieben Seiten kurz und prägnant.

https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf?__blob=publicationFile&v=2

Mal überlegen ob überlegen: Erste „Quanten-Supremacy“ erreicht

Nachdem bereits vor einer Weile die erste tatsächlich erreichte „Quanten-Supremacy“ verkündet worden war, hat Google nun endlich den offiziellen Bericht zu dem Erfolg in der Grundlagenforschung herausgebracht. Supremacy (Überlegenheit) bedeutet hier, dass ein Quantencomputer ein praktisches Problem schneller als jeder konventionelle Computer löst. Objektiv ist dies eindrucksvoll gelungen: Der supraleitende Quantenrechner konnte in 200 Sekunden eine Aufgabe berechnen, für die ein konventioneller Supercomputer 10.000 Jahre brauchen würde. Der Konkurrent IBM behauptet zwar, das Problem in einem theoretisch möglichen Supercomputer in 2 ½ Tagen bewältigen zu können, aber an der Überlegenheit ändert dies nichts.

Allerdings war das zu berechnende Problem aus der theoretischen Chemie so speziell auf den Erfolg geschneidert, dass es keinerlei sinnvolle Anwendung hat. Insofern ist Supremacy nicht gleich sinnvolles Ergebnis. Trotzdem ist hiermit ein technischer und theoretischer Meilenstein erreicht worden, den einige Kritiker den Quantencomputern bzw. ihren Konstrukteuren nie zugetraut hatten. Bis zum Brechen von Verschlüsselung ist noch ein längerer Weg – von dem allerdings ein wichtiger Schritt nun geschafft wurde.

https://www.heise.de/newsticker/meldung/Jetzt-auch-offiziell-Googles-Quantencomputer-zeigt-Quantum-Supremacy-4565771.html

Millionen? Ich dachte Milliarden! Quantencomputer rücken dank Rechentricks näher

Quantencomputer gefährden bekanntlich, wenn sie einmal in ausreichender Größe gebaut werden können, das Gros der heute im Einsatz befindlichen kryptographischen Verfahren. Unter anderem sind asymmetrische Kryptographie wie RSA und elliptische Kurven sowie die meisten Arten von Signaturen hinfällig, symmetrische Algorithmen wie AES büßen de facto „nur“ die Hälfte ihrer effektiven Schlüssellänge ein. Noch gibt es jedoch große technische Hürden, ausreichend Stabilität hinzubekommen, um einen Quantenrechner ernstzunehmende Dechiffrierung ausführen zu lassen –theoretisch. Forschern von Google und des Royal Institute of Technology in Stockholm ist es nun gelungen, die Algorithmen so umzuformen, dass 20 Millionen wackelige Qubits genügen könnten, um RSA 2048 zu brechen. Das ist immer noch weit über dem aktuellen Rekord von 70 Qubits, aber zwei Größenordnungen unter der zuvor benötigten Zahl von einer Milliarde Qubits. Sollte die Forschung in diesem Tempo weitergehen, wären praktische Quantencomputer vermutlich weniger als 10 Jahre entfernt.

https://www.technologyreview.com/s/613596/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours