Droht die Quantenapokalypse?

François Weissbaum, Kryptologe beim VBS.
Theoretisch lassen sich mit Quanten­computern die gebräuchlichen Schlüssel­austausch­verfahren wie RSA, Diffie-Hellman und ECC (Elliptic Curve Cryptography) in Windeseile knacken. Wie real und wie gross ist das Risiko wirklich?
 
An einem Anlass der Security Interest Group Switzerland (SIGS) zeigten Fachspezialisten die möglichen und zu erwartenden Auswirkungen auf Public-Key-Infrastrukturen (PKI) auf. Dies sind allgegenwärtige Systeme, welche digitale Zertifikate ausstellen, verteilen und prüfen. Als Basis dient ein asymmetrisches Kryptosystem. Zur Sprache kamen auch die möglichen Gegenmassnahmen, um sich gegen das Schlüsselbrechen durch Quantencomputer zu wappnen. Der Anlass fand in den Räumlichkeiten der Mobiliar in Bern statt, einer Versicherungsgesellschaft, die auch Cyber Insurance im Angebot hat und deshalb direkt von einer Quantenapokalypse betroffen wäre.
 
Quantencomputer, Algorithmen und Schlüssel
François Weissbaum, Kryptologe beim VBS, zeigte die Ausgangslage und die aktuellen Entwicklungen auf. Quantencomputer unterscheiden sich im Aufbau und in der Arbeitsweise von klassischen Computern. Traditionelle Computer basieren auf Bits. Jedes Bit hat entweder einen Wert von O oder 1. Das System ist deterministisch; es treten nur definierbare und reproduzierbare Zustände auf.
 
Quantencomputer bauen auf Qubits auf. Jedes Qubit kann einen Wert von 0, 1 oder einer Quanten-Superposition dieser beiden Qubit-Zustände aufweisen. Ein Paar von Qubits kann in einer beliebigen Quanten-Superposition von vier Zuständen sein, während drei Qubits in einer beliebigen Superposition von acht Zuständen sein können. Ein Quantum-Register umfasst deutlich mehr Werte als ein klassisches binäres Register. Bei Qubits handelt es sich um Zwei-Zustands-Systeme, die mittels Bloch-Kugel visuell dargestellt werden können.
 
Quantencomputer schaffen die Grundlage für neue Algorithmen. Es stellt sich somit die Frage, welche Probleme bei Verfügbarkeit von universellen Quantencomputern gelöst werden können. In Bezug auf das Brechen von Verschlüsselungen existieren zurzeit zwei Algorithmen, welche bei Verfügbarkeit eines universellen Quantencomputers mit mindestens 64 Qubits wirkungsvoll eingesetzt werden könnten: Shor's Algorithmus und Grover's Algorithmus.
 
Ersterer verringert die benötigte Zeit zur Integer-Faktorisierung und zur Berechnung von diskreten Logarithmen. Die schnelle Integer-Faktorisierung kann das RSA-Verfahren knacken. Diffie-Hellman, DSA (Digital Signature Algorithm), ElGamal-Signaturverfahren und Elliptic Curve Cryptography (ECC) basieren auf der Problemstellung des diskreten Logarithmus und sind deshalb ebenfalls betroffen. Bei allen betroffenen Verfahren handelt es sich ausschliesslich um asymmetrische Kryptosysteme. Im Gegensatz dazu kann Grover's Algorithm mittels Brachialgewalt symmetrische Schlüssel knacken. Für einen 128-bit-Schlüssel braucht es dafür allerdings 2 hoch 64 (18'446'744'073'709'551'616) Iterationen.
 
Noch bleibt Zeit
Die Auswirkungen von Quantencomputern auf die Kryptographie sind derzeit äusserst limitiert. Für die Beurteilung der künftigen Auswirkungen muss daher die hypothetische Frage nach den Auswirkungen auf die Sicherheit für den Fall gestellt werden, dass ein universeller Quantencomputer verfügbar wäre.
 
Für den Angriff auf symmetrische Schlüssel steht derzeit nur Grove's Algorithmus zur Verfügung. Um die Gefahr zu bannen genügt es, die Schlüssellängen zu verdoppeln, um das gleiche Sicherheitsniveau aufrecht zu erhalten. Ein AES-Schlüssel mit einer Länge von 256 Bit bietet selbst bei Verwendung von Grover's Algorithmus mit einem universellen Quantencomputer noch das Sicherheitsniveau, das ein AES-Schlüssel mit einer Länge von 128 Bit heute bei Verwendung von klassischen Computern bietet. Auch für Hash-Funktionen steht nur Grover's Algorithmus zur Verfügung. Längen von 384 Bit sind theoretisch auch bei Verfügbarkeit von universellen Quantencomputern sicher. Das betrifft SHA-384, SHA-512, SHA3-384 und SHA3-512. Selbst praktikable Attacken auf SHA-256 und SHA3-256 sind in der vorhersehbaren Zukunft nicht möglich.
 
Anders sieht es bei asymmetrischen Kryptosystemen aus. Shor's-Algorithmus kann Problemstellungen wie Faktorisierung und Diskreter Logarithmus schnell und effizient lösen. Würde ein universeller Quantencomputer existieren, dann wären sämtliche heutigen asymmetrischen Verfahren unsicher.
 
Für eine einfache PKI braucht es nur zwei Algorithmen: Einen für Hash-Funktionen und einen für die digitale Signatur. Nur letztere verwenden ein asymmetrisches Krypto-System und sind verwundbar. Für diesen Bereich werden quantensichere mathematische Algorithmen (Post-Quantum Cryptography/PQC) entwickelt. Es gibt unterschiedliche Ansätze, von denen die meisten wenig praktikabel sind. Es wird sich aber in nächster Zeit ein praktikabler Ansatz durchsetzen.
 
Nach Einschätzung von äusserst optimistischen Physikern werden universelle Quantencomputer frühestens in zehn bis 15 Jahren zur Verfügung stehen. Relevant ist Quantensicherheit deshalb nur für Daten, welche auf lange Zeit sensitiv sind und für Signaturen, die noch in mehr als zehn Jahren gültig sein müssen.
 
Blockchain als Rettungsanker für PKIs?
Eine Public Key Infrastructure (PKI) besteht aus Software. Man kann sie als Software-Applikation auf einem PC, Server oder sicherer und schneller auf einem Hardware Security Modul (HSM) betreiben. Die Sicherheit einer PKI hängt von drei Hauptfaktoren ab: Implementierung, Konfiguration und Sicherheit der Schlüssel. Mittels Blockchain kann eine PKI zusätzlich abgesichert werden. Quantensicher sind die von Blockchain verwendeten Algorithmen allerdings nicht. Vielmehr geht es darum, PKI-spezifische Probleme abzudecken oder eine PKI zu dezentralisieren.
 
Zu den aktuellen Projekten gehören "Instant Karma", das eine Blockchain-basierte Lösung für log-basierte PKIs und für Fehlverhalten der Certificate Authority (CA) bietet; "Decentralized Public Key Infrastructure", welche eine Blockchain-basierte Dezentralisierung von PKIs ermöglicht; und "Keyless Signature Infrastructure (KSI)", die eine PKI um ein dezentrales System zum Zeitstempeln und für Server-unterstützte digitale Signaturdienste zwecks Schutz der Integrität von Daten erweitert.
 
Post-Quantum Cryptography (PQC)
Es gibt bereits erste brauchbare Quantum-sichere Algorithmen für asymmetrische Kryptosysteme. In den nächsten Jahren werden diese immer mehr Verbreitung finden. So entwickelt auch der schweizerische Sicherheitsspezialist Securosys im Rahmen eines KTI-Projekts zusammen mit der Hochschule für Technik Rapperswil eine Implementierung von PCQ-Algorithmen für seine HSMs. (Christoph Jaggi)
 
Die Präsentationen des Events sind auf der Website der Security Interest Group Switzerland abrufbar. SIGS-Events sind auf Endanwender ausgerichtet. Im März gibt es einen Event zum Thema GDPR und im Mai findet die dreitägige SIGS Technology Conference statt. Für die Teilnahme an Events wird nur ein Unkostenbeitrag erhoben.