Original-URL des Artikels: https://www.golem.de/news/post-quanten-kryptographie-zu-viele-vorschlaege-und-zu-viele-bytes-1901-138500.html    Veröffentlicht: 07.01.2019 09:00    Kurz-URL: https://glm.io/138500

Post-Quanten-Kryptographie

Zu viele Vorschläge und zu viele Bytes

Die Standardisierung von Verschlüsselungsverfahren, die Sicherheit vor Quantencomputern bieten, ist nicht einfach. Noch sind viel zu viele Vorschläge im Rennen.

Seit etwa einem Jahr versuchen sich Kryptographen daran, im Rahmen eines Verfahrens der US-Standardisierungsbehörde Nist Verschlüsselungsverfahren für die Zukunft auszuwählen, die Schutz vor Quantencomputern bieten - man spricht auch von Post-Quanten-Kryptographie. Insgesamt 69 Verfahren standen zur Auswahl, einige davon sind bereits gebrochen.

Doch nach wie vor sind 48 Vorschläge im Rennen. Immer noch zu viele, findet Daniel Bernstein. Er sprach auf dem Chaos Communication Congress (35C3) von einem Denial-of-Service-Angriff auf die kryptographische Community. Denn ein großes Problem bei vielen Verfahren der Post-Quanten-Kryptographie: Es gibt große Zweifel an deren Sicherheit, da es sich um teilweise relativ neue Methoden handelt, die bislang nicht hinreichend untersucht wurden.

Überall zu viele Bytes

Doch das ist nicht die einzige Herausforderung, vor der die zukünftigen Verschlüsselungs- und Signaturverfahren stehen. Wie Daniel Bernstein und Tanja Lange in ihrem Vortrag zeigen, sind viele der neuen Verfahren für die Praxis nur schwer tauglich, da Schlüssel, Signaturen und verschlüsselte Daten zu viel Platz benötigen. Bei fast allen Verfahren liegen die Größen im Bereich von Kilobytes und bei einigen auch Megabytes. Zum Vergleich: Bei Verfahren auf Basis elliptischer Kurven kommt man mit 32 Byte Schlüsselgröße aus.

Insbesondere für Protokolle wie TLS, bei denen es auf Geschwindigkeit und einen schnellen Verbindungsaufbau ankommt, sind Schlüsselgrößen von mehreren Kilobyte eine Herausforderung. Realistischerweise gibt es nur zwei Klassen von Algorithmen, die für solche Protokolle in Frage kommen: Sogenannte Lattice- oder Gitter-basierte Algorithmen und Supersinguläre Isogenien. Letztere bieten zwar die kleinsten Schlüsselgrößen, sie sind aber auch sehr langsam und noch vergleichsweise neu.

Ganz praktische Erfahrungen mit Post-Quanten-Kryptographie versucht gerade Google zu sammeln. Schon 2016 hatte Google in Chrome und auf einigen seiner Server ein Experiment gestartet, das aber nach wenigen Monaten wieder eingestellt wurde.



Google experimentiert mit HRSS

Google-Entwickler Adam Langley hat im Dezember angekündigt, dass bald ein zweites Post-Quanten-Experiment mit TLS starten solle. Dafür setzt man auf einen Verschlüsselungsalgorithmus namens HRSS, dieser wird aber kombiniert mit einem klassischen Verfahren auf Basis elliptischer Kurven genutzt. HRSS ist ein Lattice-Schlüsselaustausch und basiert auf dem Ntru-Verfahren. Google setzt eine neue Variante von HRSS ein, die nicht mit der im Nist-Verfahren übereinstimmt.

Ntru ist unter den Post-Quanten-Algorithmen einer der älteren Kandidaten. Es wurde bereits 1996 entwickelt, lange Zeit wurde es aber praktisch nicht genutzt, da es durch Patente geschützt war. Doch die Ntru-Patente sind inzwischen ausgelaufen.

Beim Google-Experiment ist nur der Schlüsselaustauch sicher vor Quantencomputern, die Signaturen nutzen weiterhin klassische Algorithmen wie RSA oder ECDSA. Doch das hat auch seine Berechtigung: Heute verschlüsselte Daten könnten gespeichert und in Zukunft entschlüsselt werden, bei Signaturen gibt es derartige Probleme nicht.

Patente könnten jedoch für andere der vorgeschlagenen Algorithmen zum Problem werden. Wie Daniel Bernstein ausführt, gibt es eine ganze Reihe von Vorschlägen, bei denen die Entwickler der Algorithmen Patente halten. Bei weit verbreiteten Protokollen wie TLS ist die Nutzung von patentierten Algorithmen praktisch nicht vorstellbar, zumindest nicht, wenn die Patentinhaber keine kostenlose Nutzung zulassen.

Ein Patent, das lange Zeit nicht bekannt war, betrifft eine Klasse von Lattice-Algorithmen, die eine Methode namens Ring Learning with Errors nutzen. Eine ganze Reihe von Einreichungen des Nist-Wettbewerbs basiert darauf. Laut Bernstein ist nicht eindeutig, ob dieses Patent vor den ersten Veröffentlichungen des RLWE-Algorithmus eingereicht wurde. Wäre dies der Fall, wäre das Patent ungültig.



CSIDH: Ersatz für Diffie Hellman und kleine Schlüssel

Neben großen Schlüssellängen ist laut Tanja Lange eine weitere Herausforderung, dass sich bisher keines der beim Nist vorgeschlagenen Verfahren eignet, den klassischen Diffie-Hellman-Schlüsselaustausch direkt zu ersetzen. Doch da gibt es möglicherweise bald Abhilfe: Ein Team, an dem Lange beteiligt ist, hat einen neuen Algorithmus auf Basis supersingulärer Isogenien entwickelt, der genau das bietet: CSIDH (ausgesprochen "Seaside").

Für die Implementierung ist CISDH sehr attraktiv: Mit 64 Byte kommt der Algorithmus mit sehr kleinen Schlüsseln aus und ist damit schon nahe an aktuellen Verschlüsselungsverfahren ohne Quantensicherheit dran. CSIDH ist nicht Teil des Nist-Verfahrens, dafür wurde er zu spät entwickelt.

Auch warnt Tanja Lange, dass im Moment niemand diesen Algorithmus nutzen sollte. Denn dafür ist er noch zu neu. Die gesamte Klasse der Verfahren basierend auf Isogenien gilt bisher als nur begrenzt vertrauenswürdig, denn es ist von allen Post-Quanten-Methoden die jüngste. Der erste Vorschlag für derartige Verschlüsselungsalgorithmen wurde 2011 veröffentlicht.

Nist aufgrund von Haushaltssperre inaktiv

Als nächsten Schritt plant das Nist, die Zahl der Algorithmen für die zweite Runde deutlich zu reduzieren. Zurzeit passiert dort allerdings nichts, da die US-Behörde aufgrund der Haushaltssperre in den USA nicht arbeitet. Auch die Webseite ist derzeit nicht erreichbar, die Informationen über die eingereichten Vorschläge lassen sich gerade nur über die Wayback-Machine abrufen.  (hab)


Verwandte Artikel:
Anton Zeilinger: Wissenschaftler kommunizieren quantenverschlüsselt   
(30.09.2017, https://glm.io/130370 )
Anja Karliczek: Bundesregierung will Quantentechnologien fördern   
(25.09.2018, https://glm.io/136763 )
Privatsphäre: "Kaum wird die App geöffnet, landen Daten bei Facebook"   
(03.01.2019, https://glm.io/138460 )
Sicherheit: Fünf von sechs Routern enthalten bekannte Sicherheitslücken   
(05.10.2018, https://glm.io/136957 )
Quantencomputer: Erste Empfehlungen für Post-Quanten-Kryptographie   
(07.09.2015, https://glm.io/116166 )

© 1997–2019 Golem.de, https://www.golem.de/