Post-Quanten-Signaturen

Von Stefan-Lukas Gazdag und Daniel Loebenberger, Kirchheim

Schon seit gut 15 Jahren beschäftigen sich Kryptologen mit der Post-Quanten-Kryptografie, also Verschlüsselungs- und Signaturverfahren, die nicht nur gegen klassische, sondern auch gegen quantencomputerbasierte kryptoanalytische Angriffe resistent sind. Das US-amerikanische National Institute of Standards and Technology (NIST) hat Ende 2017 begonnen, in einem Standardisierungsprozess geeignete Verfahren zu identifizieren, um diese in den kommenden Jahren zu analysieren und nach Möglichkeit zu normieren sowie Empfehlungen auszusprechen. Auch die für Internetstandards zuständige Internet Engineering Task Force (IETF) und ihre Schwesterorganisation Internet Research Task Force (IRTF) verfolgen über zwei geplante RFCs erste Standardisierungsbemühungen im Bereich der Post-Quanten-Kryptografie.

Hashbasierte Signaturen

Ein fortgeschrittenes Forschungsgebiet stellen hashbasierte Signaturen dar, die auch schon seit Jahren als Merkle-Signaturen in den einschlägigen Algorithmenkatalogen des BSI aufgeführt werden (aktuell TR-02102-1 vom Feb. 2017). Diese Signaturen basieren – ihrem Namen entsprechend – auf der Nutzung von kryptografisch sicheren Hashfunktionen. Anders als bei den heute üblichen Signatur-Verfahren benötigen hashbasierte Signaturen jedoch keine zusätzlichen Sicherheitsannahmen (vgl. Kasten). Da man generische Angriffe auf Hashfunktionen mit Quantenrechnern bereits heute ziemlich genau versteht, weiß man, dass diese Algorithmen gegen deren Fähigkeiten als sicher anzusehen sind. So hat man auch bei hashbasierten Signaturen ein recht genaues Verständnis über die Sicherheit dieser Verfahren im „Post-Quanten-Zeitalter“.

Um dies zu ergründen, betrachtet man den Geschwindigkeitsgewinn, den ein Quantencomputer gegenüber einem herkömmlichen Computer bei Suchproblemen in unstrukturierten Datenmengen hat. Der sogenannte Grover-Algorithmus ermöglicht es, dieses Problem mit einem Quantencomputer wesentlich effizienter zu lösen: Während man mit klassischen Rechnern bis zu n Schritte benötigt, um ein gewünschtes Datum aus der Menge zu finden, gelingt dies einem Quantencomputer in ungefähr √n Operationen – ein beträchtlicher Fortschritt. Im Kontext der Kryptoanalyse durch generische Angriffe (Brute Force) muss man also die Schlüssellänge verdoppeln, um das gleiche Sicherheitsniveau zu erhalten. Ähnliche Argumente gelten für Hashfunktionen: Eine Verdopplung der Ausgabelänge einer Hashfunktion erzielt wieder ein vergleichbares Sicherheitsniveau.

Auch die von moderneren hashbasierten Verfahren gebotenen Laufzeiten und Datengrößen eignen sich inzwischen durchaus für die Praxis. Selbst wenn – abhängig von den Parametern – speziell die Schlüsselerzeugung, aber auch die Signaturerstellung und -verifikationen im Vergleich zu klassischen Signaturverfahren unter Umständen länger benötigen, sind sie für viele Anwendungsfälle auch heute schon praktikabel.

Typische Signaturgrößen bewegen sich im Bereich von wenigen Kilobyte. Die Signaturen stellen damit – trotz mancher Beschränkungen in Protokollen – in vielen Anwendungsszenarien kein Problem dar. Quantenresistente Verfahren nutzen allgemein oft größere Datenstrukturen, als man es etwa von RSA oder DSA gewohnt ist. Soll sich Post-Quanten-Kryptografie im großen Stil verbreiten, wird man also früher oder später auch Protokolle und Implementierungen anpassen müssen, um die neuen Verfahren nutzen zu können.

Hashfunktionen und Sicherheit

Hashfunktion bilden (quasi) beliebig große Daten auf eine alphanumerische Zeichenfolge bestimmter Länge ab, den sogenannten Hashwert (im Engl. oft auch „Message Digest“). Kryptografisch sichere Hashfunktionen erfüllen dabei zusätzlich bestimmte Sicherheitsannahmen: So darf man praktisch nicht in der Lage sein, mit dem Wissen über einen Hashwert die ursprünglich eingegebenen Daten, also das Urbild, zu ermitteln. Des Weiteren muss es praktisch unmöglich sein, mit Wissen über die Eingabedaten und den Hashwert weitere Eingabedaten zu finden, die denselben Hashwert liefern (zweites Urbild). Und drittens müssen die Funktionen „kollisionsresistent“ sein, es praktisch also unmöglich sein, zwei beliebig gewählte Eingabedaten zu finden, die denselben Hashwert ergeben (Kollision).

Um eine kryptografische Signatur beliebiger Nachrichten zu realisieren, wird typischerweise nur deren Hashwert signiert, sodass die Sicherheitsannahmen an die Hashfunktion sich direkt auf Sicherheitsaussagen der darauf aufbauenden Signaturen auswirken. Bei klassischen Verfahren wie RSA oder DSA kommen weitere Sicherheitsannahmen hinzu: Bei RSA beruht die Sicherheit im Wesentlichen auf der Faktorisierung großer Zahlen, bei DSA auf der Berechnung diskreter Algorithmen. Beide Probleme gelten im klassischen Szenario als schwer lösbar – skalierbare Quantencomputer können sie jedoch effizient lösen. Rein hashbasierte Signaturen benötigen hingegen keine zusätzlichen Sicherheitsannahmen, sondern basieren einzig auf der Sicherheit von Hashfunktionen.

Zustandsbehaftung

Ein besonderer Nachteil hashbasierter Signaturen ist die sogenannte Zustandsbehaftung: Die Verfahren nutzen nämlich Einmalsignaturverfahren (One-Time-Signature-Schemes) – es werden also Schlüsselpaare verwendet, mit denen man nur ein einziges Mal signieren darf. Wird eine zweite Nachricht mit demselben Schlüssel signiert, so besteht die Gefahr, dass weitere Nachrichten/Signatur-Paare gefälscht werden können. Somit benötigt man folglich genau so viele Einmalsignaturschlüsselpaare, wie Nachrichten signiert werden sollen. Wie bei allen Signaturverfahren müssen die Verifikationsschlüssel dem Empfänger der Nachricht übermittelt werden. Ein sehr einfaches Einmalsignaturverfahren (Lamport One-Time-Signature-Scheme) ist in Abbildung 1 skizziert.

Um das Handling der Schlüssel praktikabler zu gestalten, werden spezielle Datenstrukturen – sogenannte Merkle-Bäume – verwendet, um die Schlüsselpaare zu verwalten (siehe Abb. 2). Ein n-stufiger Merkle-Baum fasst durch sukzessive Hashwertbildung benachbart Knoten 2n öffentliche Schlüssel zusammen (Blätter des Baums). Elternknoten (z. B. A) werden jeweils durch Konkatenation und Hashen zweier Kindsknoten (z. B. B und C) berechnet. Würde, wie im Beispiel dargestellt, mit dem zweiten Einmal-Signaturschlüsselpaar signiert, könnte der Empfänger/Verifizierer das darüber liegende Blatt C des Baums berechnen. Mithilfe zusätzlicher Informationen über den Baum (im Bild rot) könnte ein Verifizierer alle nötigen Knoten bis einschließlich der Wurzel (root) berechnen. Hat der Empfänger die Wurzel unabhängig von der Nachricht vom Ersteller auf sicherem Wege erhalten, so ist die Authentizität des Signierers gewährleistet.

Der Verifikationsschlüssel des Einmalsignaturschlüsselpaars dient dann nur der Überprüfung der Authentizität der Nachricht selbst. Durch den Merkle-Baum kann also ein einziger öffentlicher Schlüssel (Hashwert) für alle verwalteten Schlüsselpaare erzeugt werden – nämlich die Wurzel des Baums. Der Empfänger erhält neben der eigentlichen Nachricht, der Signatur und dem Verifikationsschlüssel, um die Nachricht zu überprüfen, die genannten Zusatzinformationen über den Baum (fehlende Knoten = Hashwerte), um die Wurzel selbst berechnen und mit dem veröffentlichten Referenzwert vergleichen zu können. Dazu wird die Wurzel über einen anderen Weg (z. B. als Zertifikat) zur Verfügung gestellt und weist so den Absender der Nachricht aus.

Die soeben beschriebene Methodik entspricht den klassischen Merkle-Signaturen – moderne hashbasierte Signaturen verwenden etliche Optimierungen, die vor allem die Laufzeiten verbessern, die benötigten Datenstrukturen verkleinern und auch mehr Sicherheit bieten. Um den Überblick zu behalten, welche Schlüsselpaare innerhalb des Baums schon verwendet wurden und welche noch zur Verfügung stehen, muss im einfachsten Fall bei sequentieller Nutzung der Index des ersten noch unbenutzten Schlüsselpaares gespeichert werden. Auch hier ist offensichtlich, dass nur eine begrenzte Anzahl an Signaturen pro öffentlichem Schlüssel erstellt werden kann.

Die Zustandsbehaftung bringt weitreichende Konsequenzen mit sich: So ist der geheime Schlüssel (Signaturschlüssel, Private Key) eine kritische Ressource und benötigt ein Schlüsselmanagement, das den Zugriff darauf reguliert. Außerdem dürfen nicht mehrere Prozesse parallel das Schlüsselmaterial nutzen, da der Signaturschlüssel mit jeder Signatur geändert werden muss. Viele kryptografische Implementierungen sind jedoch nicht dafür konzipiert, dass der Signaturschlüssel stetig zu aktualisieren ist. Diese Hürden lassen sich jedoch durch entsprechende Anpassungen in der Software und durch anwendungsfallorientierte Verwaltung und Zugriffskontrolle der Schlüssel oft meistern.

Um das Problem der Zustandsbehaftung zu umgehen, gibt es neuerdings auch das zustandslose Verfahren SPHINCS (https://sphincs.cr.yp.to), bei dem Mehrfachsignaturverfahren (Few-Time-Signature-Schemes) zum Einsatz kommen: Damit kann man pro Schlüsselpaar mehrfach signieren, wobei die Sicherheit mit jeder neuen Signaturerstellung schwindet. Ist der Baum groß genug, lässt sich das Schlüsselpaar zufällig auswählen und auf einen nachzuhaltenden Zustand verzichten – dieser wurde somit gegen eine Wahrscheinlichkeitsbetrachtung getauscht.

Zustandslose hashbasierte Signaturen haben etwas längere Laufzeiten und größere Signaturen als ihre zustandsbehafteten Alternativen. Sollte dies (und das Vertrauen auf eine Wahrscheinlichkeitsrechnung) für ein Einsatzszenario kein Problem darstellen, so kann prinzipiell auf solche Verfahren zurückgegriffen werden. Optimierte Varianten von SPHINCS wurden zwar bereits beim NIST-Standardisierungsprozess eingereicht – eine Standardisierung dürfte somit aber leider noch ein paar (wenige) Jahre dauern.

Standardisierung

Anders sieht es beispielsweise für das „eXtended Merkle Signature Scheme“ (kurz XMSS) und dessen sogenannte Multi-Tree-Variante XMSS^MT aus: Hierfür gibt es schon seit 2015 einen Internet-Draft, der voraussichtlich bis Mitte 2018 als RFC veröffentlicht werden wird (siehe https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatures/). Die RFCs der IETF/IRTF zählen schon lange als De-facto-Standards des Internets, auch wenn sie keinen „offiziellen“ Standard-Charakter (gem. RFC 2026) besitzen.

Überdies plant das NIST, zustandsbehaftete hashbasierte Signaturen außerhalb ihres Standardisierungsprozesses zu behandeln und mit der IETF/IRTF zusammenzuarbeiten. Ursprünglich wurde der angesprochene Internet-Draft als Individualeinreichung veröffentlicht, doch kurz darauf zu einem Working-Group-Draft der „Crypto Forum Research Group“ (CFRG) erhoben. Im Rahmen umfangreicher Diskussionen und dank unzähliger Kommentare konnte der Entwurf in mehr als zehn Iterationen immer weiter verbessert werden. Inzwischen konvergierte all dies zu einem finalen Stand, der schließlich als RFC veröffentlicht werden soll. Die ersten Reviews diverser Gutachter hat der Entwurf bereits hinter sich gebracht. Mit dem Ergebnis der derzeit durchgeführten Überprüfung durch eine der letzten Instanzen auf dem Weg zum offiziellen RFC wird noch im Januar gerechnet.

Das beschriebene Verfahren XMSS ist das momentan fortgeschrittenste zustandsbehaftete Verfahren. Statt des in Abbildung 1 skizzierten Lamport-Verfahrens wird eine optimierte Variante des „Winternitz One-Time Signature Scheme“ (WOTS) verwendet, nämlich WOTS+. Dabei werden nicht für einzelne Bits Zufallswerte generiert und mit einem einzelnen Aufruf der Hashfunktion verarbeitet, sondern stattdessen mehrere Bits gleichzeitig verarbeitet und hierfür ganze Ketten an Funktionsaufrufen genutzt. Diverse weitere Vorkehrungen sollen zudem die gesamte Konstruktion gegen eine Vielzahl möglicher Angriffe stärken.

Bezüglich der Hashfunktionen wird im jetzigen Internet-Draft die Nutzung der SHA-2-Familie (gemeint sind SHA-256 etc.) und von SHA-3 (bzw. SHAKE) beschrieben – doch auch weitere, kryptografisch sichere Hashfunktionen sind denkbar. Positiv ist hieran, dass die grundlegende Konstruktion hashbasierter Signaturen auch bei Angriffen auf eine spezifische Hashfunktion weiter nutzbar bleibt. Sollte es in Zukunft also beispielsweise effiziente Angriffe auf SHA-2 geben, so könnte man von einer XMSS-Instantiierung mit SHA-2 auf ein Schlüsselpaar migrieren, welches das weiterhin sichere SHA-3 nutzt. Dabei ist zu beachten, dass im Falle von XMSS und XMSS^MT mit einer WOTS+-Instantiierung für einen erfolgreichen Angriff zumindest ein zweites Urbild gefunden werden muss – das Auffinden von Kollisionen reicht hingegen nicht aus. Während für SHA-1 und dessen Vorgänger MD5 inzwischen erfolgreiche Kollisionsangriffe gefunden wurden, ist bis dato für keine der beiden Konstruktionen eine Möglichkeit zum Auffinden eines (zweiten) Urbilds bekannt.

Neben XMSS gibt es derzeit noch einen weiteren Internet-Draft zu hashbasierten Signaturen, der das „Leighton-Micali Signature System“ (LMS) und dessen Multi-Tree-Variante „Hierarchical Signature System“ (HSS) beschreibt (siehe https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/) – dieser Entwurf wird voraussichtlich ebenfalls als RFC veröffentlicht werden. Im Unterschied zu XMSS und XMSS^MT sind LMS/HSS schneller, haben aber einen schwächeren Sicherheitsbeweis. Beide Systeme sind praktikabel – die Entscheidung zwischen ihnen ist eher eine Frage des persönlichen Geschmacks.

Anwendungen

Das beste Beispiel für eine Anwendung hashbasierter Signaturen sind Signaturen für Software-Updates, mit denen Hersteller ihren Kunden gegenüber nachweisen, dass die veröffentlichten Aktualisierungen unverändert sind und tatsächlich vom Hersteller selbst stammen. Der öffentliche Schlüssel zur Verifikation wird dabei ab Werk mit ausgeliefert oder durch ein Update eingespielt, das wiederum selbst mithilfe eines vorherigen, aber noch gültigen öffentlichen Schlüssels überprüft wurde.

Dieses Einsatzszenario ist besonders geeignet für zustandsbehaftete Verfahren: Einerseits sind Entwicklungsumgebungen ohnehin meist sehr restriktiv – der Zugriff auf Entwicklungsrechner ist oft eingeschränkt und Signaturschlüssel werden über speziell abgesicherte KeyServer verwaltet. Daher kann man hier vergleichsweise einfach als Sicherheitsanker zum Beispiel auf Smartcards oder Hardware-Sicherheitsmodule zurückgreifen.

Das Update-Szenario wirkt in der Gesamtheit der kryptografischen Anwendungen im Alltag fast etwas unscheinbar, doch seine Relevanz ist nicht zu unterschätzen. Updates stellen letztlich die wichtigste Möglichkeit dar, um schnell Sicherheitslücken zu schließen. Bis Kunden aber einen aktuellen Software-Stand nutzen und tatsächlich auf quantenresistente Signaturen umsteigen, können viele Jahre vergehen – man denke nur daran, welch alte Betriebssysteme noch heute im Praxiseinsatz sind.

Sollte es in der Zwischenzeit einen skalierbaren Quantencomputer geben, der Signaturen fälschen könnte, so wäre kein sicheres Update mehr möglich! Denn kein Hersteller möchte seine Patches selbst oder über vertrauenswürdige Kuriere ausliefern müssen. Daher ist es nötig, schon jetzt quantensichere Signaturen für Updates anzubieten, um im Fall der Fälle einen sicheren Übergang ins Post-Quanten-Zeitalter zu ermöglichen. Die genua gmbh hat dies bereits erfolgreich getestet.

Auch andere Anwendungsfälle für hashbasierte Signaturen sind denkbar: Das größte Problem bei der Nutzung von zustandsbehafteten hashbasierten Signaturen ist die sichere und ausreichend effiziente Verwaltung der geheimen Schlüssel. Kann dies gewährt werden, etwa durch die Nutzung einer Smartcard, so wird eine Nutzung hashbasierter Signaturen auch für E-Mails, sichere Verbindungen über SSH und ähnliche Anwendungen vorstellbar.

Für Szenarien mit TLS/SSL, etwa sicheres Surfen auf Websites, die mit HTTPS abgesichert wurden, ist dies schwieriger umzusetzen. Dabei kommen serverseitig häufig virtuelle Maschinen (VM) zum Einsatz, welche die Nutzung von Kryptografie in vielerlei Hinsicht gefährden, sollte ein Angreifer etwa eine Kopie eines Zustands der VM erlangen – und die Last durch die Vielzahl eingehender Verbindungen kann teils sehr hoch sein. Eine parallelisierte Nutzung der Signaturschlüssel ist möglich, bedarf allerdings eines komplexeren Schlüsselmanagements. Hashbasierte Signaturen sind in diesem Kontext daher prinzipiell möglich, aber in der Praxis oft schwierig umzusetzen und nicht empfehlenswert. Bezüglich weiterer Anwendungsfälle besteht also noch deutlicher Forschungsbedarf.

Ausblick

Ein grundlegendes Problem neuer Algorithmen ist prinzipiell das fehlende Vertrauen ihnen gegenüber. Klassische Verfahren wie RSA werden tagtäglich von Millionen Nutzern eingesetzt und wurden bisher – soweit wir wissen – praktisch nie gebrochen, sofern zum jeweiligen Zeitpunkt ausreichend große Parameter genutzt wurden. Dies gibt eine gewisse Zuversicht in die Sicherheit der eingesetzten „Cryptographic Primitives“ und führte zu einem breiten Einsatz in der Praxis.

Bei neuen Verfahren sind sowohl Experten als auch Anwender verständlicherweise vorsichtig. Dabei ist ein Praxiseinsatz genauso wichtig wie die zuvor durchgeführte theoretische Begutachtung: Nur bei täglicher Nutzung lässt sich zeigen, wie sehr sich ein Verfahren bewährt – und nur in realen Einsatzszenarien kann man testen, welche Angriffe eventuell möglich sind.

Im Gegensatz zu den meisten anderen quantenresistenten Verfahren sind hashbasierte Signaturen bereits reif für erste ernsthafte Praxiseinsätze und die Sicherheit ist – zumindest generisch – wohlverstanden. Teilweise kann die Einführung der Verfahren auch hybrid mit etablierten Mechanismen erfolgen. Dabei lassen sich alte und neue Verfahren parallel nutzen, wobei man zum Beispiel anfangs bei etwaigen Unstimmigkeiten mit dem neuen Verfahren noch auf das alte vertraut, oder sie werden – sofern möglich – so verschachtelt, dass sie beide zur Sicherheit beitragen und beim Bruch des einen Verfahrens die gesamte Konstruktion weiter sicher bleibt.

Gerade Firmen mit Geschäftsfeldern in sicherheitskritischen Bereichen arbeiten schon heute mit Nachdruck daran, ihre Produkte auch in der Post-Quanten-Ära absichern zu können. Mit frei nutzbaren hashbasierten Signaturen wie XMSS und den öffentlich verfügbaren Informationen wie beispielsweise zum zugehörigen Schlüsselmanagement kann jeder Interessierte den Einstieg in die Post-Quanten-Kryptografie in der Praxis wagen.

Stefan-Lukas Gazdag und Dr. Daniel Loebenberger sind Kryptografen bei der genua gmbh.