Post-Quantum-Kryptographie

Die Zukunft der Kryptographie im Zeitalter der Quanten

| Autor / Redakteur: Dr. Thomas Pöppelman, Dr. Josef Haid / Peter Schmitz

Durch Quantencomputer können aktuelle kryptographische Algorithmen wie RSA und ECC in Zukunft die Sicherheitsanforderungen aus Industrie und Verwaltung wohl nicht mehr erfüllen. Ein Ausweg ist die Migration zu Post-Quantum-Kryptographie (PQC).
Durch Quantencomputer können aktuelle kryptographische Algorithmen wie RSA und ECC in Zukunft die Sicherheitsanforderungen aus Industrie und Verwaltung wohl nicht mehr erfüllen. Ein Ausweg ist die Migration zu Post-Quantum-Kryptographie (PQC). (Bild: Infineon Technologies AG)

Lange waren Quantencomputer pure Theorie, aber bereits vor über 20 Jahren zeigten Forscher, dass Krypto-Algorithmen gegen die Besonderheiten von Quantencomputern anfällig sind. In den nächsten 15 bis 20 Jahren ist die Entwicklung von Quantencomputern zum Einsatz in der Kryptoanalyse ein realistisches Szenario. Viel Zeit für die Entwicklung neuer Algorithmen und einer Post-Quantum-Kryptographie bleibt also nicht mehr.

Verschiedene Internet- und Industriestandards verwenden asymmetrische Kryptographie auf der Basis von RSA oder elliptischen Kurven („Elliptic Curve Cryptography“, ECC). So lässt sich beispielsweise mit dem RSA-Algorithmus ein Verschlüsselungsschema mit öffentlichen Schlüsseln („Public-Key Encryption“, PKE) realisieren, mit dem eine verschlüsselte E-Mail-Nachricht an einen Empfänger gesendet werden kann (z.B. mit PGP/GPG oder S/MIME), ohne dass zuvor ein symmetrischer Schlüssel ausgetauscht werden muss – der öffentliche Schlüssel des Empfängers reicht aus. Weitere Anwendungen der asymmetrischen Kryptographie sind digitale Signaturen auf der Basis von RSA oder ECC, die zum Signieren und Verifizieren von Daten verwendet werden können. Gemeinsam bilden PKE und digitale Signaturen ein entscheidendes Element im Transportschicht-Sicherheitsprotokoll („Transport Layer Security“, TLS), dem Rückgrat der gesicherten Kommunikation im Internet, das von Browsern, Smartphones und zunehmend auch von IoT-Geräten verwendet wird.

Seit der Arbeit von Peter Shor aus dem Jahr 1994 ist allerdings bekannt, dass RSA und ECC gegenüber Angriffen von Quantencomputern anfällig sind. Shors Algorithmus, ausgeführt auf einem Quantencomputer, ermöglicht das Faktorisieren des öffentlichen Schlüssels des RSA-Kryptosystems bzw. einen ähnlichen Angriff auf ECC. Somit fällt die Bit-Sicherheit aller praktischen Parametersets von RSA und ECC und der darauf basierenden Schlüsselaustausch-, PKE- und Signaturverfahren auf einen Wert nahe Null. Ein weiterer, von Grover vorgeschlagener Quanten-Algorithmus kann zum Beschleunigen von Brute-Force-Attacken auf symmetrische Block-Chiffren wie AES verwendet werden. AES wird in der Regel zum Verschlüsseln von Nutzdaten eingesetzt, wobei der Schlüssel in der Regel zuvor mittels RSA oder ECC etabliert wurde. Als Folge muss gegenüber Quantencomputern die Schlüssellänge der derzeitigen symmetrischen Algorithmen mit 128 Bit klassischer Sicherheit verdoppelt werden. Ein AES-128 müsste also beispielsweise durch AES-256 ersetzt werden, um weiter 128-Bit-Sicherheit zu erzielen.

Verschlüsselung in Zeiten der Post-Quantum-Kryptographie

Neue Algorithmen gegen Quantencomputer

Verschlüsselung in Zeiten der Post-Quantum-Kryptographie

20.06.17 - Ohne zuverlässige Verschlüsselung ist die digitale Welt unvorstellbar. Nach zahllosen Tests gelten die etablierten Verfahren heute als äußerst sicher. Doch das könnte sich bald ändern, wenn Codebrecher über Quantencomputer verfügen. Mit Hochdruck arbeiten Mathematiker an neuen Verfahren. Läuft alles glatt, sollen sie in 10 Jahren einsatzfähig sein, die Frage ist aber, ob das schnell genug ist. lesen

Quantencomputer: Von der Theorie zur Realität und weiter...

Ein Quantencomputer lässt sich als ein Computer beschreiben, der zur Beschleunigung der Berechnung quantenmechanische Phänomene nutzt. Entscheidende Konzepte zum Bau eines Quantencomputers sind die so genannten Quanten-Bits oder Qubits zum Speichern des Status in einem Quantencomputer. Gemäß dem Überlagerungsprinzip (Superposition) hat ein Qubit nicht einen Zustand Null oder Eins wie in einem klassischen Computer. Stattdessen hat das Qubit eine unbegrenzte Anzahl von Zuständen, und der Status ist eher eine Wahrscheinlichkeit dafür, welchen Wert (Null oder Eins) das Qubit annimmt, wenn es gemessen wird. Dieses Messen zerstört allerdings die Überlagerung. Verwendet man Qubits in einem so genannten verschränkten („entangled“) Zustand, sind einzelne Qubits zwar bedeutungslos aber der gesamte verschränkte Zustand ist von Bedeutung. Und während z.B. ein klassisches 4-bit Register mit vier Bits beschrieben ist, ist der Zustand eines Quantencomputers ein 2^4=16 dimensionaler Zustandsraum komplexwertiger Koeffizienten. Die Manipulation eines einzelnen verschränkten Qubit hat dann Auswirkungen auf alle anderen Qubits und somit auf den gesamten großen Zustandsraum. Solche Manipulationen werden als Quanten-Gatter beschrieben, die auf ein oder mehreren Qubits angewandt werden. Im Vergleich zu klassischen Gattern („gates“) gelten für Quanten-Gatter einige Einschränkungen (z. B. die Umkehrbarkeit und das No-Cloning-Theorem) die das einfache Kopieren von Qubits unmöglich machen. Wegen dieser Einschränkungen sind Quantencomputer nicht per se auch Supercomputer. Stattdessen wird davon ausgegangen, dass sie in der Lage sind, spezifische Aufgaben, für die schnelle Quantenalgorithmen existieren, effizient zu berechnen. Neben der genannten Anwendung in der Kryptoanalyse kann es sich bei derartigen Problemen um Optimierungsprobleme handeln, das Suchen langer Muster in großen Datenmengen, medizinische Forschung oder die Simulation der Quantenmechanik für ein besseres Verständnis biochemischer Prozesse für den Pharma- oder Chemiebereich.

Der tatsächliche Bau eines universalen Quantencomputers scheint heute jedoch extrem teuer und kompliziert, und das Ziel aktueller Forschung ist die Steigerung der Anzahl unterstützter Qubits. Im März 2017 präsentierte IBM einen öffentlich zugänglichen 16 Qbit-Prozessor, der über eine Cloud-Schnittstelle programmiert werden kann, sowie einen ersten kommerziellen Prototyp-Prozessor mit 17 Qubits. Von Unternehmen wie Google und Microsoft ist bekannt, dass sie ebenfalls an Quantentechnologien arbeiten. Dabei ist insbesondere die Fehlertoleranz von größter Bedeutung, wenn das System lange Zeit ausgeführt wird; dies erfordert eine komplexe Quanten-Fehlerkorrektur und redundante Qubits. Daher scheint die Entwicklung von Quantencomputern mit Anwendungen in der Kryptoanalyse (z.B. Shor oder Grover) innerhalb der nächsten 15 bis 20 Jahre ein realistisches Szenario zu sein. Michele Mosca, der Leiter des Instituts für Quantum Computing an der Universität von Waterloo, geht von einer 50-Prozent-Chance aus, RSA-2048 bis 2031 zu knacken. Möglicherweise als Reaktion auf die verstärkten Aktivitäten bei der Entwicklung von Quantencomputern hat die NSA im August 2015 bekannt gegeben, dass sie „in nicht allzu ferner Zukunft“ den Übergang zu quantenresistenten Algorithmen plant; ein konkreter Zeitplan wurde jedoch nicht genannt.

Der Quantencomputer ist auch für die NSA noch nicht in Reichweite

Keine Gefahr für aktuelle Verschlüsselung

Der Quantencomputer ist auch für die NSA noch nicht in Reichweite

28.01.14 - Steht die NSA schon kurz vor der Entwicklung eines Quantencomputers, mit dem sich jede Verschlüsselung in kürzester Zeit knacken lässt? Deutsche Experten geben Entwarnung. lesen

Post-Quantum- und Quantum-Kryptographie

Als Gegenmaßnahme zur Bedrohung durch Quantencomputer gibt es derzeit in der Kryptographie zwei Ansätze. Einer ist die Post-Quantum-Kryptographie (PQC), die auf die Ausführung neuer kryptographischer Algorithmen auf klassischen Computern setzt und diese damit gegen Attacken von Quantencomputern effizient sichern soll. Der andere Ansatz ist die Quantum-Kryptographie, oder genauer der Quanten-Schlüsselaustausch („Quantum Key Distribution“, QKD), bei dem Eigenschaften der Quantenmechanik zur Einrichtung eines geheimen Schlüssels zwischen den beiden Parteien genutzt werden. Dieser geheime Schlüssel kann dann zur Verschlüsselung großer Datenmengen mit klassischen symmetrischen Chiffren wie AES verwendet werden. Die Sicherheit von QKD basiert nicht auf Berechnungen, sondern auf der Annahme, dass eine Messung eines Quantenzustands (z. B. dem Spin eines Photons) den Zustand zerstört und dass der Quantenzustand nicht kopiert werden kann. Wenn daher ein passiver Angreifer eine Messung durchführt, um den Zustand zu erhalten, soll diese Attacke vom Empfänger erkannt werden. QKD ist jedoch kein universeller Ersatz für RSA und ECC, da die derzeitigen Systeme kostspielige Einrichtungen und dedizierte Glasfaserverbindungen mit bestimmten Einschränkungen hinsichtlich ihrer Länge oder eine direkte Sichtlinie erfordern.

Stattdessen werden Post-Quantum-Kryptosysteme auf klassischen Computern ausgeführt und zeigen normalerweise auf abstrakter Ebene das gleiche Verhalten wie derzeit verfügbare Chiffren, sodass sie als direkter Ersatz agieren. Derzeit liegt das Hauptaugenmerk der Forschung im PQC-Bereich auf der asymmetrischen Kryptographie (d.h. dem Ersetzen von RSA und ECC), da die Bedrohung des Grover-Algorithmus durch den Umstieg auf bereits verfügbare sichere 256-Bit-Schlüssel Algorithmen (z.B. AES-256 oder SHA-512) gemildert werden kann. Als Schutz gegen Attacken mithilfe des Shor-Algorithmus vertrauen PQC-Systeme auf unterschiedliche fundamentale Härteannahmen, die auf Quantencomputern praktisch nicht lösbar sein sollen. Es ist jedoch zu beachten, dass es keinen bekannten Ansatz gibt, um mit Sicherheit nachzuweisen, dass eine solche Härteannahme Quantencomputern immer standhalten wird. Infolgedessen lautet der typische Ratschlag, ausschließlich PQC-Algorithmen zu verwenden, die einer Kryptoanalyse ausreichend lange standhalten konnten und damit als ausreichend sicher gelten können.

Verschlüsselung für das Post-Quanten-Zeitalter

Forschung

Verschlüsselung für das Post-Quanten-Zeitalter

06.02.17 - An Quantencomputern wird weltweit intensiv geforscht. Experten schätzen, dass 2025 ein funktionierender Quanten-Computer gebaut werden könnte – dieser könnte bisher benutzte Public-Key-Verschlüsselungs- und Signaturverfahren brechen. Damit geschützte Daten wären offengelegt und entsprechende Signaturen wären fälschbar. Um sich auf das sogenannte Post-Quantum-Zeitalter vorzubereiten, forscht ein Team der TU Darmstadt um Professor Johannes Buchmann, Sprecher des Sonderforschungsbereichs CROSSING, mit Partnern aus der Industrie und Behörden an neuen kryptographischen Verfahren, die auch von einem Quantencomputer nicht gebrochen werden können. lesen

Die fünf typischen Härteannahmen oder Algorithmus-Familien zur Realisierung einer asymmetrischen Post-Quantum-Kryptographie sind:

Hash-basierte Signaturen: Signatursysteme, deren Sicherheit auf die Härte des Brechens einer symmetrischen Hashfunktion (z. B. SHA-256) reduziert werden kann. Diese Systeme wurden von Lamport 1979 vorgeschlagen, und aktuelle für die Standardisierung in Betracht gezogene Systeme sind das eXtended Merkle Signature Scheme (XMSS) [4] oder die Leighton Micali Signatures (LMS). Ein Nachteil von XMSS und LMS ist, dass sie zustandsbehaftet sind – der Signierer muss den geheimen Schlüssel nach jedem Signierungsvorgang aktualisieren, und die Anzahl der Signaturen pro öffentlichem/privatem Schlüssel ist begrenzt. Ein alternativer Vorschlag ist das zustandslose Signatursystem SPHINCS, welches diese Begrenzungen überwindet, aber auch mehr Rechenzeit erfordert und längere Signaturen (41 KB) erzeugt.

Code-basierte Kryptographie: Die beiden wichtigsten code-basierten Verschlüsselungssysteme sind das McEliece Kryptosystem (1978) und eine Variante mit dem Namen Niederreiter Kryptosystem (1986). Beide Systeme basieren auf der Annahme, dass bestimmte mathematische Probleme der Codierungstheorie schwer sind. Für eine ausreichende Post-Quantum-Sicherheit führen die für öffentliche Schlüssel empfohlenen Parametersets jedoch zu öffentlichen Schlüsseln mit einer Größe von ca. 1 Megabyte wenn die sogenannten Goppa-Codes verwendet werden. In letzter Zeit wurden diese Größen durch den Einsatz von besser strukturierten Codes (z. B. QC-MDPC-Codes) reduziert, die jedoch bisher nicht so gründlich untersucht wurden wie die Goppa-Code-Variante.

Multivariate Kryptographie (MQ): Bezieht sich auf Kryptosysteme, deren Sicherheit auf der Härte des Lösens multivariater Polynomgleichungen basiert. Die meisten MQ-Systeme sind Signatursysteme und verwenden normalerweise sehr kurze Signaturen, aber sehr lange öffentliche Schlüssel.

Gitterbasierte Kryptographie: Ein Gitter ist eine regelmäßige Struktur von Punkten, und die Sicherheit von gitterbasierten Kryptosystemen hängt mit der Schwere von mathematischen Probleme in derartigen Gittern zusammen bzw. wird auf diese reduziert. In letzter Zeit wurden zahlreiche Systeme vorgeschlagen. Beispiele für effiziente Schlüsselaustauschsysteme auf Gitterbasis sind New Hope, Frodo und Kyber, einige ausgewählte Signatursysteme sind BLISS, Tesla oder Dilithium.

Isogen-basierte Kryptographie: Verwendet eine mathematische Struktur bestimmter elliptischer Kurven zum Design von Schlüsselaustausch- oder digitalen Signatursystemen.

Seit den letzten Jahren entwickelt sich PQC von einem Thema für Kryptographen hin zu einem Feld welches auch für Software- und Hardwareentwickler interessant ist. Denn die Implementierung von PQC ist sehr wichtig, um mehr über die Eigenschaften dieser neuen Systeme zu lernen und den Entwicklern bei Bedarf Rückmeldungen zu weiteren Optimierungen geben zu können. Ein Beispiel eines solchen Kryptosystems ist das von Alkim, Ducas, Pöppelmann und Schwabe entwickelte so genannte gitterbasierte New Hope Schlüsselaustauschsystem. New Hope wurde als Ersatz (oder Ergänzung) aktueller Schlüsselaustausch-Mechanismen mit Diffie-Hellman oder Elliptic Curve Diffie-Hellman entwickelt und bietet 256-Bit Sicherheit. 2016 wurde der New-Hope-Algorithmus von Google in einer öffentlichen Freigabe einer Testversion seines Chrome-Browsers getestet. Infineon hat vor kurzem New Hope auf einer kontaktlosen Smartcard implementiert und gezeigt, dass PQC auch auf Systemen mit weniger Speicher und kontaktloser Stromversorgung implementiert werden kann. Dies ist ein weiterer Beweis dafür, dass manche PQC-Systeme praktikabel sind und als Ersatz für RSA und ECC dienen können oder die Sicherheit durch die parallele Anwendung von PQC und diesen Systemen verbessert werden kann. Es sind jedoch noch weitere Forschungsarbeiten erforderlich, um bessere Systeme zu entwickeln und vorhandene Systeme im Hinblick auf einen niedrigen Stromverbrauch, einen geringen Speicherbedarf und hohe Sicherheit zu optimieren.

Allianz für Sicherheit im Zeitalter des Quanten-Computing

Mobile World Congress — Quantum Alliance

Allianz für Sicherheit im Zeitalter des Quanten-Computing

28.02.17 - Mit Quantencomputern lassen sich vielleicht bald aktuell noch als sicher geltende Verschlüsselungs-Algorithmen knacken. Damit wären heute gebräuchliche kryptografische Verfahren quasi unbrauchbar. SK Telecom und Deutsche Telekom haben die „Quantum Alliance“ gegründet, um sichere Kommunikation in Zeiten des Quantencomputers zu ermöglichen. lesen

Anwendungen, Überblick und Standardisierung

Derzeit gibt es eine Vielzahl akademischer Vorschläge für PQC, aber es wurden bisher keine Standards entwickelt. Das U.S. National Institute of Standards and Technology (NIST) hat daher sein Post-Quantum Crypto Project als wettbewerbsähnliche Anstrengungen zur Standardisierung (Letzter Abgabetermin ist der 30. November 2017) gestartet. NIST bittet dabei um Beiträge zum Post-Quantum-Schlüsselaustausch, zur Verschlüsselung öffentlicher Schlüssel und zu Signatursystemen. Im April 2018 plant NIST dann die erste PQC-Standardisierungskonferenz abzuhalten.

Es kann jedoch mehrere Jahre dauern, bis die ersten PQC-Standards zu erwarten sind, gefolgt von einer Übergangsphase von natürlich ebenfalls einigen Jahren. Eine Ausnahme hiervon sind zustandsbehaftete hashbasierte Signatursysteme (z. B. XMSS oder LMS), die gut verstanden sind und für die derzeit ein Standardisierungsprozess bei der IETF läuft.

In der Praxis wird PQC höchstwahrscheinlich zuerst in Anwendungen eingeführt, die eine langfristige Vertrauenswürdigkeit erfordern. Derzeit ist es jedoch unklar, wie spezifische Industrien auf die Bedrohung durch Quantencomputer reagieren werden:

TLS- und Internetprotokolle: Eventuell wird ein Post-Quantum-Schlüsselaustauschsystem in TLS eingeführt, um schon bald eine langfristige Vertraulichkeit der Kommunikation zu erzielen. Dies ist möglich, weil die meisten Geräte, die TLS ausführen, eine relativ hohe Leistung haben (z. B. Smartphones oder PCs) und derzeit gute Mechanismen zur Software-Aktualisierung vorliegen (z. B. bei allen wichtigen Browsern). Adam Langley von Google sagt außerdem, „es ist wahrscheinlich, dass TLS in Zukunft eine Post-Quantum-Schlüsselvereinbarung erfordern wird“, aber er bevorzugt einen multilateralen Ansatz bzgl. der Auswahl eines Algorithmus.

Hochsicherheits-Kommunikation: Bei besonders kritischen Kommunikationsleitungen, beispielsweise bei Behörden, Telekommunikationsunternehmen, Rechenzentrums-Verbindungen oder Unternehmens-Intranets mit Anforderungen zur langfristigen Vertraulichkeit ist zu erwarten, dass PQC schon bald eingeführt wird, eventuell auch ohne Standards. Eine zusätzliche sofortige Maßnahme für die Einführung derartiger kritischer Kommunikationsleitungen könnte die Nutzung von vorab platzierten symmetrischen 256-Bit-Schlüssel und Schlüssel-Rotationssystemen sein.

Automobilindustrie: Die wachsende Vernetzung von Automobilen bietet eine Vielzahl neuer Services und Geschäftsmodelle. Gleichzeitig entstehen dadurch Sicherheitsrisiken in den Fahrzeugen. Aus diesem Grund werden derzeit komplexe Sicherheitsarchitekturen auf der Basis einer asymmetrischen Kryptographie in Autos implementiert. Wegen der langen Lebensdauer von Automobilen (ca. 15 Jahre) muss die Industrie nach Antworten auf die Bedrohung durch Quantencomputer suchen und zumindest einen Plan als Antwort auf das Aufkommen von Quantencomputern haben.

Internet der Dinge (IoT): Die steigende Anzahl von Attacken auf IoT-Geräte zeigt, dass immer mehr Sicherheitsmaßnahmen notwendig werden. Insbesondere für Geräte mit einer längeren Lebensdauer, z. B. in der Industrieautomation, aber auch im Bereich Smart Home (Heizungssystem, Home-Automation oder verkabelter Einbruchsalarm), müssen Angriffe auf das System durch Quantencomputer berücksichtigt werden

Infineon, als führender Hersteller von Security ICs und Chips für das Internet der Dinge und die Automobilindustrie ist hier auf mehreren Ebenen aktiv, um zukünftige Lösungen für Kunden und Anwender bereitzustellen. Aktivitäten umfassen dabei wissenschaftliche Beiträge, Teilnahme an der PQC Standardisierung und prototypische Entwicklungen und Forschung.

Kontaktloser Sicherheits-Chip sicher vor Quantencomputern

Post-Quantum-Kryptographie

Kontaktloser Sicherheits-Chip sicher vor Quantencomputern

01.06.17 - Quantencomputer besitzen aufgrund ihrer Rechenleistung das Potenzial, verschiedene aktuell verwendete Verschlüsselungsalgorithmen zu knacken. Infineon Technologies will jetzt den reibungslosen Übergang von heutigen Sicherheitsprotokollen auf die Post-Quantum-Kryptographie (Post-Quantum Cryptography; PQC) schaffen. Infineon hat die erste PQC-Implementierung auf einem kontaktlosen Sicherheitschip, der üblicherweise für Ausweisdokumente verwendet wird, erfolgreich realisiert. lesen

Über die Autoren

Dr. Thomas Pöppelmann ist Ingenieur im Bereich Sicherheit und Kryptographie bei der Infineon Technologies AG in München. Sein Hauptarbeitsbereich ist die Entwicklung von Konzepten für abgesicherte Kryptographiemodule, die Standardisierung im Bereich Sicherheit und die Post-Quantum-Kryptographie. 2015 erhielt er einen PhD (Dr.-Ing.) von der Ruhr-Universität Bochum. Für seine Arbeiten an dem Post-Quantum-Schlüsselaustauschsystem New Hope wurde ihm und seinen Co-Autoren der Facebook Internet Defense Prize 2016 verliehen.

Dr. Josef Haid studierte Elektrotechnik und promovierte 2003 an der Technischen Universität Graz in Österreich zum Doktor der Ingenieurwissenschaften. Seit 2004 bei Infineon, bekleidete Dr. Haid verschiedene Positionen in der Konzepttechnik und im technischen Marketing für kontaktlose Sicherheitscontroller, die bei Bezahlvorgängen und in behördlichen Identifikationsanwendungen eingesetzt werden. 2015 übernahm er die Verantwortung für das technische Marketing integrierter Sicherheitslösungen.

Kommentare werden geladen....

Kommentar zu diesem Artikel

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 44900590 / Verschlüsselung)