Post-Quanten-Kryptografie gegen Cyberattacken der Zukunft

Mit Shors Algorithmus gegen asymmetrische Verschlüsselung

Die amerikanischen Mathematiker und Informatiker Peter W. Shor und Lov K. Grover haben bereits in den 1990er Jahren Algorithmen entwickelt, die herkömmliche Verschlüsselungstechniken obsolet machen. Dazu benötigen sie allerdings einen Quantencomputer. Allerdings waren zum damaligen Zeitpunkt nur die theoretischen Grundlagen von Quantenrechnern bekannt. Das ist heute anders.

Erste Systeme dieser Art sind in Betrieb, etwa bei IBM und Google. Zudem sind Quantensimulatoren verfügbar, beispielweise die Quantum Learning Machines des französischen IT-Hauses Atos. Solche Systeme simulieren Quanteneffekte, um Rechenaufgaben deutlich schneller zu bewältigen als konventionelle Computer.

Mit dem Algorithmus, den Shor im Jahr 1994 vorstellte, können Nutzer von Quantenrechnern vor allem Verschlüsselungsverfahren angreifen, die auf einer asymmetrischen Verschlüsselung basieren. Dazu zählen RSA und Diffie-Hellman. Solche Ansätze verwenden ein Schlüssel-Paar: einen öffentlichen Key (Public Key) sowie einen privaten Schlüssel. Der öffentliche dient dazu, eine Information vor der Übermittlung zu verschlüsseln.

Mit dem privaten Key dekodiert der Adressat die Daten, die er vom Sender empfangen hat. Das RSA-Verfahren nutzt dabei die Tatsache, dass es für einen herkömmlichen Rechner einfach ist, zwei Primzahlen zu multiplizieren. Aus dem Ergebnis der Multiplikation jedoch wieder die beiden ursprünglichen Zahlen abzuleiten, erfordert einen hohen Rechenaufwand. Das gilt für alle derzeit verfügbaren Prozessor-Architekturen und Computersysteme: Supercomputer, Rechner-Cluster oder Standardserver. Auch die Prozessor-Architektur spielt keine Rolle, etwa ob x86/x64-CPUs, die Power-Architektur von IBM oder ARM-Prozessoren zum Einsatz kommen.

Herkömmliche Computer: Jahrelange Rechenarbeit nötig

Dazu ein Beispiel zur Faktorisierung von Primzahlen, also dem Zerlegen eines Produkts in seine Bestandteile: Ein Rechner benötigt Sekundenbruchteile, um das Resultat von 13.627 x 9.817 zu ermitteln, also 133.776.259. Der umgekehrte Weg ist deutlich länger: Je nach Größe der Primzahlen dauert es Jahre oder Jahrzehnte, bis ein Computer alle möglichen Kombinationen durchprobiert hat. Diesen Aufwand können nicht einmal amerikanische, russische oder chinesische Geheimdienste betreiben, denen Supercomputer zur Verfügung stehen.

Daher galten bislang asymmetrische Verschlüsselungsverfahren wie RSA mit 2048- oder 3072-Bit-Keys als „nicht knackbar“. Laut Krysta Svore, die bei Microsoft Research den Bereich Quantenrechner leitet, würde ein klassischer Computer eine Milliarde Jahre benötigen, um eine RSA-2048-Verschlüsselung zu brechen. Stehen jedoch Quantensysteme zur Verfügung, würde eine solche Aufgabe nur 100 Sekunden erfordern. Zudem belegte Svore zusammen mit Kollegen vom Microsoft Research Center, dass andere asymmetrische Verschlüsselungstechniken, wie etwa ECDL (Elliptic Curve Discrete Logarithms), noch anfälliger als das RSA-Verfahren für Angriffe mit Quantensystemen sind.

Auch symmetrische Verschlüsselung gefährdet

Auch symmetrischen Verschlüsselungstechniken wie AES (Advanced Encryption Key) oder DES (Data Encryption Standard) sind im Quanten-Zeitalter gefährdet. Sie verwenden nur einen einzigen Schlüssel für das Ver- und Entschlüsseln von Informationen. Das Problem: Sender und Empfänger benötigen denselben Schlüssel. Dieser muss somit auf sichere Weise an beide Kommunikationspartner übermittelt werden. Daher haben sich in der Praxis hybride Verfahren entwickelt. Sie nutzen eine asymmetrische Verschlüsselung für die Übermittlung der Keys.

Allerdings hat der Mathematiker Lov K. Grover 1996 einen Quanten-Algorithmus vorgestellt, der auch die Sicherheit von symmetrischen Verschlüsselungsverfahren reduziert. Grovers Algorithmus erlaubt es, mithilfe von Quantenrechner einen symmetrischen Schlüssel mit hoher Wahrscheinlichkeit zu ermitteln. Ebenso wie Shors Algorithmus setzt der Ansatz von Grover dabei auf die Fähigkeit von Quantencomputer, Berechnungen parallel durchzuführen.

Herkömmliche Verschlüsselung künftig nicht mehr sicher

Die Forscher Tanja Lange von der Technischen Universität Eindhoven und Daniel J. Bernstein von der University of Illinois at Chicago zeichnen in einem ein ernüchterndes Bild der Sicherheit der heute gebräuchlichen Verschlüsselung. Demnach lassen sich mit Shors Algorithmus und Quantenrechnern alle Public-Key-Verfahren brechen. Das gilt für RSA und Diffie-Helman (DH) sowie den Digital Signature Algorithm (DSA), und zwar auch dann, wenn 3.072-Bit-Keys eingesetzt werden.

Etwas besser sieht es bei symmetrischen Techniken wie AES (Advanced Encryption Key) mit 128- oder 256-Bit-Schlüsseln und SHA (Secure Hash Algorithm) mit 256 Bit. Deren Schutzwirkung reduziert sich jedoch auf die Hälfte, wenn Quantencomputer in Verbindung mit dem Algorithmus von Grover zur Schlüsselanalyse herangezogen werden können. Das bedeutet beispielsweise, dass eine AES-Verschlüsselung mit 256 Bit (AES-256) nur noch eine Schutzwirkung wie AES 128 hat, also die Version, die mit 128-Bit-Keys arbeitet.

Empfehlungen des BSI

Das Bundesamt für Sicherheit in der Informationstechnik (BSI) hat in der technischen Richtlinie "Kryptographische Verfahren: Empfehlungen und Schlüssellängen" (BSI TR-02102-1) vom Januar 2018 Folgendes festgelegt: Asymmetrische Verschlüsselungstechniken in Systemen, die bis zum Jahr 2022 im Einsatz sind, sollten Schüssel mit mindestens 2.000 Bit verwenden. Das gilt beispielsweise für RSA und das Hybridverfahren DLIES (Discrete Logarithm Integrated Encryption Scheme).

Ab dem Jahr 2022 empfiehlt das BSI eine Schlüssellänge von mindestens 3.000 Bit. Allerdings räumt das Bundesamt ein, dass bei diesen Empfehlungen Fortschritte bei der Entwicklung von Quantensystemen nicht berücksichtigt wurden. Der Grund sei, dass sich die Geschwindigkeit der technischen Entwicklung auf diesem Gebiet nur schwer abschätzen lasse. Daher gilt die Richtlinie auch nur bis 2024. Generell, so das BSI, sei eine Post-Quanten-Kryptografie (PQC) notwendig, um langfristig die Sicherheit von Daten zu garantieren.

Post-Quanten-Kryptografie notwendig

Der Faktor Zeit spielt bei einer Post-Quanten-Kryptografie in mehrfacher Hinsicht eine Rolle. So müssen bereits heute entsprechende Verfahren entwickelt werden. Zum einen deshalb, weil die Entwicklung und Standardisierung solcher Techniken langwierig ist. Zum anderen ist zu berücksichtigen, dass Investitionsgüter und langlebige Konsumartikel möglichst schnell mithilfe einer PQC geschützt werden müssen. Der Grund ist der lange Einsatzzeitraum solcher Komponenten. Hinzu kommt, dass immer mehr „Dinge“ miteinander kommunizieren, Stichwort Internet der Dinge.

Maschinen und Anlagen in Industrie-4.0-Umgebungen sind beispielsweise bis zu 20 oder 30 Jahre lang im Einsatz. Smart Cars, die untereinander und mit Verkehrsleitsystemen kommunizieren, haben eine Lebensdauer von etwa zehn Jahren. Daher müssen Kryptosysteme, die in solchen Komponenten eingesetzt werden, bereits heute so ausgelegt sein, dass sie eine einfache Migration zu einer PQC ermöglichen.

Neue Verschlüsselungsverfahren auf dem Prüfstand

Fachleute von Forschungseinrichtungen und Unternehmen arbeiten bereits an einer Post-Quanten-Kryptografie (PQC). Koordiniert werden die Arbeiten vom amerikanischen Standardisierungsgremium NIST (National Institute of Standards and Technology). Es hat Kryptografie-Spezialisten aufgefordert, im Rahmen eines Wettbewerbs quantensichere Verfahren zur Prüfung einzureichen. Derzeit sind rund 70 Algorithmen im Rennen. Einige stammen von europäischen Teilnehmern, etwa dem IT-Haus Atos und der Universität Toulouse.

Der Zeitplan des NIST sieht vor, dass die vorgeschlagenen PQC-Algorithmen etwa ab Mitte 2018 überprüft werden. Das wird drei bis fünf Jahre dauern. Weitere zwei Jahre später, also zwischen 2023 und 2025, soll ein Standard verabschiedet werden. Dann, so das NIST, werden standardisierte Verschlüsselungsverfahren bereitstehen, die „quantensicher“ sind.

Neben dem NIST beschäftigen sich auch Einrichtungen in Europa en mit einer quantensicheren Verschlüsselung. Dazu zählt das europäische Forschungsprojekt PQCRYPTO. Seine Teilnehmer haben mehr als 20 Vorschläge im Rahmen es NIST-Wettbewerbs eingereicht. Sie decken mehrere Anwendungsbereiche und Sicherheitsanforderungen an. Zudem beteiligt sich PQCRYPTO an der Analyse der vorgeschlagenen Algorithmen. Die Forscher haben bereits in 18 der eingereichten Vorschläge massive Sicherheitsdefizite identifiziert.

Auch das Konsortium SAFEcrypto arbeitet an Technologien im Bereich Post-Quanten-Kryptografie. Der Vereinigung gehören Universitäten und Unternehmen aus Europa an, darunter die Ruhr-Universität in Bochum. Sie konzentrieren sich auf die Entwicklung einer PQC-Lösung auf Basis von Gittern (Lattice). Dieser Ansatz basiert darauf, dass es extrem aufwändig ist, in einem mehrdimensionalen Gitter den kürzesten Vektor zu errechnen. Mit dieser Aufgabe sind nach derzeitigem Stand selbst Quantenrechner überfordert.

Wichtig: Migrationspfad und Hybrid-Modus

Mit der Entwicklung und Standardisierung von neuen Verschlüsselungsverfahren ist es jedoch nicht getan. So hat das Fraunhofer-Institut für Sichere Informationstechnologie (SIT) in einem Hintergrundpapier zu PQC mehrere Herausforderungen identifiziert, die mit der Implementierung von PQC-Lösungen verbunden sind.

Eine besteht darin, dass die Industrie sichere und gleichzeitig effiziente PQC-Verfahren benötigt, die mit der vorhandenen Hard- und Software zusammenspielt. So müssen Smartcards, Token, Hardware Security Modules (HSM) und kryptografische Coprozessoren für PQC ausgelegt sein. Utimaco, ein deutscher Hersteller von HSM, verfügt beispielsweise über ein Software Development Kit (SDK). Mit ihm lassen sich auch Post-Quanten-Verschlüsselungsalgorithmen in die Hardwaremodule integrieren. Entsprechende SDK müssen auch für andere Komponenten bereitstehen, die bei der Verschlüsselung von Informationen eingesetzt werden.

Die Effizienz von PQC-Algorithmen ist wiederum deshalb wichtig, weil auch der Datentransfer von und zu mobilen Geräten und IoT-Komponenten (Internet of Things) geschützt werden muss. Solche Systeme verfügen nur über eine begrenzte Rechenleistung und Akkulaufzeit. Zudem ist es nach Angaben des Fraunhofer-Instituts erforderlich, während einer Übergangsphase parallel herkömmliche Verschlüsselungstechniken und PQC-Verfahren einzusetzen. Dies ist solange der Fall, bis standardisierte und geprüfte Post-Quanten-Kryptografie-Systeme zur Verfügung stehen. Doch speziell Hersteller von Produkten mit langer Lebensdauer könnten gezwungen sein, bereits Vorabversionen solcher Lösungen einzusetzen, um das Sicherheitsniveau zu erhöhen.

Fazit: Sich für den Ernstfall rüsten

Eine unmittelbare Gefahr durch Hacker oder Geheimdienste, die Quantenrechner verwenden, droht derzeit nicht. Dazu sind Quantensysteme noch nicht leistungsfähig genug. Aber das kann sich schnell ändern. Wie hoch der Schutzbedarf ist, lässt sich mit einer Formel von Dr. Michele Mosca errechnen, einem Spezialisten auf dem Gebiet Post-Quanten-Kryptografie und Chef des IT-Sicherheitsunternehmens EvolutionQ.

Die Basis ist die Summe von zwei Faktoren: wie lange eine Information geschützt sein muss und wie lange es dauert, eine PQC-Lösung zu implementieren. Ein Beispiel: Daten müssen 10 Jahre geheim bleiben; bis eine PQC zur Verfügung steht, dauert es weitere 8 Jahre. Das ergibt 18 Jahre.

Dem steht die Zeit gegenüber, bis Quantenrechner auf dem Markt sind, die eine herkömmliche Verschlüsselung brechen können. Ist das in weniger als 18 Jahren der Fall, droht Gefahr. Es liegt daher auf der Hand, dass sich bereits heute alle Unternehmen und öffentlichen Einrichtungen intensiv mit dem Thema Post-Quanten-Kryptografie auseinandersetzen müssen. Vor allem solche, die Informationen über einen längeren Zeitraum hinweg vor dem Zugriff Unbefugter schützen müssen.

Folgen Sie SearchSecurity.de auch auf Twitter, Google+, Xing und Facebook!