Erster Schritt in eine quantensichere öffentliche Verwaltung : Migration zu einer quantensicheren Verwaltungs-PKI

Bei den bereits etablierten kryptografischen Algorithmen sind die zugrunde liegenden mathematischen Probleme sehr gut untersucht, und es gibt sehr viel Erfahrung, diese sicher (bezogen auf z. B. Seitenkanäle) zu implementieren. Beides ist bei den Post-Quanten-Verfahren noch nicht in diesem Maße der Fall, da diese relativ neu sind. Das BSI setzt daher auf hybride Lösungen, in denen ein standardisiertes Post-Quanten-Verfahren in Kombination mit einem klassischen Algorithmus – zum Beispiel basierend auf Elliptic Curve Cryptography – zum Einsatz kommt. Die einzige Ausnahme hierbei bilden die hashbasierten Signaturverfahren, deren Einsatz aus Sicht des BSI – aufgrund der Sicherheitseigenschaften dieser Verfahren – auch nicht-hybrid erfolgen kann.

Bei den hashbasierten Signaturverfahren XMSS/ XMSS^MT und LMS/HSS stellt die sogenannte Zustandsbehaftung eine Herausforderung für die Schlüsselverwaltung dar, welche sorgfältig berücksichtigt werden muss. Durch die Zustandsbehaftung ist die Anzahl der erstellbaren Signaturen pro Schlüsselpaar beschränkt und bei jeder Signaturerzeugung muss ein streng monotoner Zähler fehlerfrei hochgezählt werden. Kommt es hierbei zu einem Fehler, impliziert dies ein erhebliches Sicherheitsrisiko. In diesem Fall könnte ein Angreifer (mit hoher Wahrscheinlichkeit) den Fehler ausnutzen, um Signaturen zu fälschen. Daher kommen auf der Ebene der Endnutzer ausschließlich nicht-zustandsbehaftete Signaturverfahren infrage, da hier eine Zählerverwaltung nicht praktikabel ist. Auf der Ebene der Root-CA der V-PKI prüft das BSI hingegen den Ansatz, XMSS/XMSS^MT oder LMS/ HSS einzusetzen. Hier hält das BSI die Zustandsverwaltung für umsetzbar, da

• in der kontrollierten Umgebung der Root-CA grundsätzlich nur Hardwaresicherheitsmodule (HSM) zur Signaturerzeugung verwendet werden und
• in der gesamten Lebensdauer eines Root-CA-Schlüsselpaars, welche in der Regel zehn Jahre beträgt, nur eine moderate Anzahl an Signaturen erzeugt werden.

Für die Anwendung der Zertifikate in der V-PKI müssen auch entsprechende Anforderungen an die Performance der Verfahren berücksichtigt werden. Hier ist bei der Erfassung der Ökosysteme und Anwendungsszenarien deutlich geworden, dass die Größe der Zertifikate ein besonders wichtiges Performance-Merkmal ist. Die Größe der Zertifikate ist im Wesentlichen determiniert durch die kombinierte Größe

• der Signatur des Post-Quanten-Signaturverfahrens, mit dem das Zertifikat signiert wird, und
• dem Public Key (PK), für das das Zertifikat ausgestellt wird.

In Tabelle 1 werden die jeweiligen Größen der zur Auswahl stehenden Post-Quanten-Signaturverfahren verglichen.

Hierbei wird ersichtlich, dass nur die zustandsbehafteten hashbasierten Signaturverfahren – im Hinblick auf die zugehörigen Zertifikatsgrößen – im Bereich der aktuellen, auf RSA basierenden Zertifikate liegen. Es wird deutlich, dass auf der Endnutzer-Ebene deutlich größere Zertifikate verarbeitet werden müssen, weil die zustandsbehafteten hashbasierten Signaturverfahren auf dieser Ebene nicht infrage kommen.

Das letzte Kriterium bei der Auswahl der Post-Quanten-Verfahren, welche wir hier im Detail betrachten möchten, ist die Hochverfügbarkeit. Diese ist besonders wichtig, da in der V-PKI mitunter sicherheitskritische Anwendungen angebunden sind, sodass Ausfälle weittragende negative Konsequenzen haben können. Außerdem ist es wichtig, dass auf der Root-CA- sowie auf der Sub-CA-Ebene mit einem Schlüsselpaar über die volle Laufzeit des zugehörigen Zertifikats Signaturen erstellt werden können. Insbesondere ist dies mit der Notwendigkeit von Signaturen für Sperrlisten zu begründen.

Daher ist die Ausarbeitung eines sicheren Backup-Managements notwendig. Bei den nicht-zustandsbehafteten Post-Quanten-Verfahren sind diesbezüglich keine Änderungen relativ zur aktuellen, auf RSA basierenden V-PKI zu erwarten. Aus diesem Grund kann hier auf die langjährig etablierte Erfahrung des BSI beim Betrieb dieses Hochsicherheitssystems zurückgegriffen werden.

Bei den zustandsbehafteten hashbasierten Signaturverfahren müssen dagegen andere Lösungen implementiert werden.

Distributed multi-tree hash-based signatures

Wie kann nun ein geeignetes Backup-Management für zustandsbehaftete hashbasierte Signaturverfahren gelingen? Um die Schwierigkeit zu verstehen, muss man zwei Einschränkungen aus der NIST-Spezifikation [2] beachten:

• Schlüssel- und Signaturgenerierung dürfen nur in kryptografischen Hardware-Modulen (wie etwa HSM) durchgeführt werden.
• Es darf kein privates Schlüsselmaterial (inklusive der Seeds, aus dem die OTS in den Single-Tree-Instanzen erzeugt werden) aus den kryptografischen Modulen exportiert werden.

Insbesondere impliziert letztere Bedingung, dass hier andere Strategien für das Backup-Management gewählt werden müssen als bei nicht-zustandsbehafteten Verfahren, wo der private Schlüssel oft in einer sicheren Umgebung redundant abgespeichert wird, um im Falle eines Ausfalls ein neues HSM mit dem gewünschten Schlüsselpaar initiieren zu können. In der NIST-Spezifikation [2] wird die Sicherungskopie von privatem Schlüsselmaterial verboten, da sich dadurch die Wahrscheinlichkeit für die Wiederverwendung einer OTS-Instanz erhöht. So eine Wiederverwendung hätte schwerwiegende negative Folgen, weil ein Angreifer dann (mit hoher Wahrscheinlichkeit) Signaturen fälschen kann.

Wir möchten nun das Konzept der Distributed multi-tree hash-based signatures aus der NIST-Spezifikation [2] (vereinfacht und in einem konkreten Fall) vorstellen. Die von der NIST vorgeschlagene Lösung gilt für Multi-Tree-Instanzen. Ohne Einschränkung nehmen wir nun an, dass es sich hierbei um HSS handelt. Die Konstruktion erfolgt gemäß den folgenden Schritten:

• Es wird eine LMS-Instanz der Höhe 5 in einem HSM implementiert. Dieses HSM bezeichnen wir als HSM_0. Es ist nun möglich, 2^5=32 Einmalsignaturen zu erstellen mit diesem HSM_0. HSM_0 entspricht dem TopLevel der Multi-Tree-Instanz.
• Es werden zwei weitere LMS-Instanzen auf zwei weiteren HSM, die wir als HSM_1 und HSM_2 bezeichnen, generiert. Diese LMS-Instanzen haben jeweils die Höhe 15. Demnach sind mit HSM_1 oder HSM_2 theoretisch jeweils 2^15 Signaturen möglich. HSM_1 und HSM_2 werden die ersten zwei Single-Tree-Instanzen auf dem Bottom-Level darstellen.
• Die Wurzeln der LMS-Instanzen in HSM_1 und HSM_2 werden mit den ersten beiden OTS aus HSM_0 signiert. Wir bezeichnen diese Signaturen mit Sigma_1 und Sigma_2.
• Die zugehörigen Kopien der Signaturen Sigma_1 und Sigma_2 werden außerhalb der HSM redundant abgespeichert.
• HSM_0 und HSM_2 werden heruntergefahren.
• HSM_1 wird genutzt, um Nachrichten zu signieren. Hierbei wird die Sicherungskopie von Sigma_1 genutzt, um die Signaturen aus HSM_1 in Multi-Tree-Signaturen zu konvertieren.

Theoretisch wäre nun die Erstellung von 2^15 Signaturen mit HSM_1 möglich. Diese Anzahl ist für den Einsatz in der Root-CA völlig ausreichend. Und in der Theorie wäre ein unvorhergesehener Ausfall von HSM_1 dahingehend abgesichert, da man auf das bereits initiierte HSM_2 umsteigen könnte, das als Backup für HSM_1 bereitsteht.

Es gibt aber in der Praxis ein wichtiges Problem. Dieses Problem betrifft insbesondere die Anforderung, dass in der Root-CA das Schlüsselpaar über die volle Laufzeit des Zertifikats (10 Jahre) signierfähig sein muss: Es ist aus technischer Sicht nicht unüblich, dass kryptografische Module eine kürzere Lebensdauer haben als zehn Jahre. Das hat folgende Konsequenzen: Sei x < 10 die typische Lebensdauer des genutzten kryptografischen Moduls in Jahren. Dann wäre der Plan, nach x Jahren auf HSM_2 umzusteigen. Aber wenn HSM_2 zeitgleich mit HSM_1 und HSM_0 initiiert wurde, so kann wahrscheinlich auch HSM_2 nicht aktiviert werden, obwohl es bisher noch nicht für das Signieren von Nachrichten genutzt wurde. Aktuell arbeitet das BSI an der Ausarbeitung einer geeigneten Lösung des Problems.

Exkurs: Konstruktion zustandsbehafteter hashbasierter Signaturverfahren

Im Folgenden möchten wir uns auf eine knappe Beschreibung zustandsbehafteter hashbasierter Signaturverfahren beschränken. Genaue Details zur Konstruktion der Verfahren XMSS und LMS sowie deren Multi-Tree-Varianten XMSS^MT und HSS sind den zugehörigen RFCs [6], [7] oder dem BSI-Leitfaden [8] zu entnehmen.

Single-Tree-Instanzen solcher Verfahren – wie etwa XMSS und LMS – bestehen aus der Bündelung von einer vorher festgelegten, festen Anzahl an Einmal-Signaturverfahren (One-Time Signature scheme, OTS), welche nur die einmalige Verwendung eines privaten Schlüssels zur Erzeugung von genau einer Signatur erlauben. Diese Bündelung geschieht anhand eines binären Hashbaums, des sogenannten Merkle-Trees, bei dem

• die OTS-Public-Keys die Blätter des Baums darstellen und
• jedem (Nicht-Blatt-)Knoten der Hashwert der Konkatenation der beiden Kindknoten zugeordnet wird.

Die Wurzel des Baums definiert den übergeordneten Public Key (PK_total). So kann man 2^n OTS durch einen Merkle-Baum der Höhe n zu einem Public Key bündeln, mit dem sich dann entsprechend 2^n Signaturen erzeugen lassen können. Abbildung 2 veranschaulicht dies für den Fall n=3.

Da man die OTS nur einmal verwenden darf, muss ein Zähler verwaltet werden, der kenntlich macht, welche OTS – das heißt, welche Blätter des Merkle-Trees – bereits genutzt wurden und welche noch nicht. Der aktuelle Wert dieses Zählers wird in jeder Signatur festgehalten, da der Verfizierer der Signatur diesen Wert (und den zugehörigen Authentisierungspfad im Merkle-Tree) benötigt, um den Merkle-Tree nachrechnen zu können. Hierdurch erhält der Verifizierer PK_total‘, die Wurzel des nachgerechneten Merkle-Trees. Nun kann der Verfizierer durch einen Abgleich vom Kandidaten PK_total‘ mit dem bereits authentisch vorverteilten PK_total die Signatur verifizieren. Abbildung 3 liefert ein einfaches Beispiel für eine solche Signatur für eine Nachricht M.

Es ist noch wichtig zu erwähnen, dass in der Regel die Erzeugung aller OTS-Schlüsselpaare einer Single-Tree-Instanz aus einem einzelnen Seed geschieht. Hierfür werden Pseudo-Random-Functions (PRF) genutzt.

Multi-Tree-Instanzen solcher Verfahren – wie etwa XMSS^MT und HSS – bestehen aus einer Bündelung mehrerer Single-Tree-Instanzen. Hierbei wächst die Anzahl der Single-Tree-Instanzen pro Ebene exponentiell. Genauer gilt für eine Multi-Tree-Instanz mit d Ebenen und bei der jede Single-Tree-Instanz die Höhe h‘ hat:

• Auf der Ebene d-1, dem Top-Level, gibt es nur eine Single-Tree-Instanz.
• Auf der Ebene d-2 gibt es 2^h‘ Single-Tree-Instanzen. Auf der Ebene j gibt es 2^((d-1-j)*h‘) Single-Tree-Instanzen.
• Auf der untersten Ebene, dem Bottom-Level oder der Ebene 0, gibt es 2^((d-1)*h‘) Single-Tree-Instanzen.

Hier haben wir der Einfachheit halber angenommen, dass alle Single-Tree-Instanzen die gleiche Höhe haben. Bei HSS ist es erlaubt, unterschiedliche Höhen der Single-Tree-Instanzen auf den verschiedenen Level zu implementieren.

Die Wurzel der Single-Tree-Instanz auf dem Top-Level liefert den übergeordneten Public Key. Die Signatur einer Multi-Tree-Instanz besteht aus

• der Single-Tree-Signatur der Nachricht mithilfe der Single-Tree-Instanz auf dem Bottom-Level sowie
• der Single-Tree-Signaturen der Wurzeln aller Single-Tree-Instanzen bis zur obersten Single-Tree-Instanz.

Zusammenfassung zur Auswahl der möglichen Verfahren

Welche genauen Verfahren ausgewählt werden, wird erst nach der Veröffentlichung der NIST-Standardisierungsentwürfe endgültig entschieden. In Tabelle 2 fassen wir die oben geschilderten Erkenntnisse für die infrage kommenden Post-Quanten-Signaturverfahren zusammen.

Zertifikatsgestaltung

Da die aktuell in der V-PKI verwendeten kryptografischen Algorithmen auf RSA basieren, ist es bisher möglich, sowohl für die Signaturerstellung als auch für die Verschlüsselung dasselbe Schlüsselpaar und somit ein einzelnes Zertifikat zu verwenden. In einer quantensicheren PKI werden die Endnutzer hingegen zwangsläufig getrennte Signatur- und Verschlüsselungszertifikate besitzen müssen, da hier kein Post-Quanten-Verfahren für beide Anwendungen genutzt werden kann.

Ein wichtiger Aspekt zur Gewährleistung von Interoperabilität ist die Standardisierung der Post-Quanten-Verfahren in gängigen Zertifikatsformaten. Hier leistet das BSI derzeit in Kooperation mit der genua GmbH einen Beitrag für die Standardisierung von hashbasierten Signaturverfahren in X.509-Zertifikaten [9].

Migrationskonzept

Die Migration soll über einen parallelen Ansatz durchgeführt werden. Das bedeutet, die aktuelle auf RSA basierende V-PKI bleibt bis zum vollständigen Umstieg aller Endnutzer-Zertifikate aktiv, während parallel dazu eine quantensichere V-PKI aufgebaut wird. Dadurch soll ein umfangreicher Testbetrieb sowie ein reibungsloser und unterbrechungsfreier Übergang ohne Stichtagsumstellung ermöglicht werden. In Abbildung 1 wird dies anhand eines beispielhaften Migrationsplans veranschaulicht. Aus der Abbildung wird deutlich, dass – aufgrund langer Zertifikatslaufzeiten – mit erheblichen Migrationszeiten zu rechnen ist.

Fazit

In diesem Artikel werden erste Ideen zur Gestaltung der Migration zur Post-Quanten-Kryptografie für die Verwaltungs-PKI vorgestellt. Als wichtiger Schritt hierbei wurde die Auswahl der Post-Quanten-Verfahren analysiert. Hierzu wurden Ansätze thematisiert, die folgenden Kriterien bei der Auswahl genügen: Interoperabilität, Kompatibilität mit Standardanwendungen, Sicherheit, Performance (insb. Zertifikatsgröße), Hochverfügbarkeit.

Bei den Signaturverfahren stellen hashbasierte Signaturverfahren eine konservative Option dar. Es ist ersichtlich geworden, dass gerade bei den zustandsbehafteten hashbasierten Signaturverfahren gewisse Einschränkungen im Hinblick auf die gewünschten Kriterien gelten, die sorgfältig berücksichtigt werden müssen.

Letztlich wurden weitere Schritte wie die Zertifikatsgestaltung sowie das Migrationskonzept erläutert. Es steht fest, dass die Migration hochkomplexer PKI wie die Verwaltungs-PKI enorm aufwendig und langwierig ist. Daher ist es wichtig, die Migration frühzeitig zu planen und einzuleiten, um den Umstieg zur Post-Quanten-Kryptografie rechtzeitig und mit der erforderlichen Betriebskontinuität umsetzen zu können.

Literatur

[1] National Institute of Standards and Technology (NIST), Post-Quantum Cryptography, Selected Algorithms 2022, August 2023, https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

[2] National Institute of Standards and Technology (NIST), Recommendation for Stateful Hash-Based Signature Schemes, Oktober 2020, https://doi.org/10.6028/NIST. SP.800-208

[3] National Institute of Standards and Technology (NIST), Status Report on the Third Round of the NIST PostQuantum Cryptography Standardization Process, Juli 2022, https://doi.org/10.6028/NIST.IR.8413-upd1

[4] National Security Agency, Announcing the Commercial National Security Algorithm Suite 2.0, September2022, https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF

[5] BSI, BSI TR-02102-1 „Kryptographische Verfahren: Empfehlungen und Schlüssellängen“ Version: 2023-01, Januar2023, www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.html

[6] Internet Research Task Force (IRTF), XMSS: eXtended Merkle Signature Scheme, Mai 2018, https://datatracker.ietf.org/doc/html/rfc8391

[7] Internet Research Task Force (IRTF), Leighton-Micali Hash-Based Signatures, April 2019, https://datatracker.ietf.org/doc/html/rfc8554

[8] BSI, Kryptografie quantensicher gestalten – Grundlagen, Entwicklungen, Empfehlungen, Oktober 2021, www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Broschueren/Kryptografie-quantensicher-gestalten.pdf?__blob=publicationFile&v=5

[9] Internet Engineering Task Force, Internet X.509 Public Key Infrastructure: Algorithm Identifiers for Hash-based Signatures, April 2023, https://datatracker.ietf.org/doc/draft-gazdag-x509-hash-sigs/