Hardcore-Krypto: NISTs Post-Quantum-Wettbewerb und mehr

Die Kryptografie verändert sich schnell, und mit dem Quantencomputer am Horizont, worauf müssen wir uns als nächstes vorbereiten?

Wir haben uns mit David Hook auf den PrimeKey Tech Days 2021 um mehr darüber zu erfahren, was in einer Post-Quantum-Welt zu erwarten ist. Hier ist, was er zu sagen hatte.

Der Post-Quantum-Wettbewerb (PQC) des NIST schreitet weiter voran. Ursprünglich sollte der Wettbewerb in der ersten Hälfte des Jahres 2021 abgeschlossen werden, doch er wurde erneut verlängert, wobei der aktuelle Termin für die endgültige Entscheidung auf Dezember 2021 festgelegt wurde. Da wir uns dem Ende dieses Wettbewerbs nähern, gibt es einige wichtige Aktualisierungen zu beachten:

• SP 800-208, "Stateful Signature Schemes XMSS and LMS" ist jetzt verfügbar. Obwohl der Standard vollständig ist, gibt es noch einige Bereiche, die mit "TBD" gekennzeichnet sind. Dies ist etwas ungewöhnlich, aber wahrscheinlich darauf zurückzuführen, dass es sich bei XMSS und LMS um zustandsbehaftete Algorithmen für private Schlüssel handelt und die daran arbeitenden Teams den zusätzlichen Aufwand nicht für sinnvoll hielten. Abgesehen davon bieten die Algorithmen in SP 800-208 einen Ansatz zur Erfüllung der PQC-Signaturanforderungen, der bereits heute angewendet werden kann, anstatt auf die Veröffentlichung der NIST-Standards zu warten.
• Das NIST hat bestätigt, dass es nur einen Algorithmus jeder Art akzeptieren wird. Obwohl es ziemlich offensichtlich scheint, wo der Wettbewerb am härtesten sein wird, erinnert uns das NIST auch daran, keine voreiligen Schlüsse darüber zu ziehen, was in einem bestimmten Fall die Grenze überschreiten wird.
• Der Grund dafür, dass man nicht voreilig handeln sollte, liegt darin, dass der Wettbewerb viele neue Forschungsarbeiten hervorgebracht hat und die Arbeiten zur Bestimmung der Sicherheit von Algorithmen und deren Parametern weitergehen - es ist also definitiv noch nicht vorbei. Was heute eine gute Idee zu sein scheint, kann sich schon morgen als nicht mehr so gut erweisen, da die Forschung und Überprüfung weitergeht.

Dennoch gibt es ein paar Algorithmen, die man im Auge behalten sollte:

• Crystals und Falcon stehen beide noch auf der Signatur-Finalistenliste, und Crystals und Saber stehen auch auf der Liste für Verschlüsselungsalgorithmen. Dies sind alles gitterbasierte Algorithmen. Sie werden es nicht alle schaffen.
• Es gibt mehrere Algorithmen auf der Liste der alternativen Kandidaten, die weiterhin viel diskutiert werden, z. B. ^SPHINCS+, ein hashbasierter Algorithmus, der einige der Probleme mit XMSS und LMS löst, und Frodo, der bereits an vielen Stellen standardisiert ist.

Der Blick in die Zukunft bringt uns zu etwas, das das Team von PrimeKey gerade hinzugefügt hat Bouncy Castlebekannt als die Evidence Record Syntax (ERS) und beschrieben in RFC 4998. Evidence Records sind ein Zeitstempelformat, das entwickelt wurde, um mit den Veränderungen in der Technologie Schritt zu halten, da es auf Langlebigkeit und Aktualisierbarkeit ausgelegt ist.

ERS bietet eine komplexere Datenstruktur, die zusätzlich zu den regulären Zeitstempel-Protokollen verwendet werden kann. So bietet ERS beispielsweise Strukturen zur Verwendung von Merkle-Bäumen, so dass Sie einen einzigen ArchiveTimeStamp verwenden können, um einzelne Dokumente in einer Gruppe sowie eine ganze Gruppe von Dokumenten zu überprüfen. Darüber hinaus bietet ERS ein Protokoll zur Verlängerung der Lebensdauer eines ArchiveTimeStamps, indem es Ihnen ermöglicht, neue Algorithmen und Signaturen für Dinge wie das Auslaufen von Algorithmen und das Ersetzen von Algorithmen hinzuzufügen.

Der erste Anwendungsfall für ERS betrifft die Erneuerung von Zeitstempeln, die in der Regel bei einem Problem mit dem Hash-Algorithmus (z. B. SHA-1) oder einem Problem mit der aktuell verwendeten Signatur auftritt. 

Das ERS bietet Mechanismen für diese Situationen, indem es die Struktur des Zeitstempels ändert. Dies geschieht insbesondere durch die Archivierung der Zeitstempelsequenz, um eine Änderung der Signatur zu ermöglichen oder den Hash-Algorithmus zu ersetzen.

In seiner einfachsten Form enthält ein ArchiveTimeStamp einen klassischen Zeitstempel, wie wir ihn bereits in früheren Zeitstempelprotokollen gesehen haben. Wenn Sie mit ERS eine Gruppe von Dokumenten mit einem Zeitstempel versehen wollen, können Sie auch eine zusätzliche Datensatzstruktur namens PartialHashTree verwenden, in der die mit den Dokumenten oder Dokumentgruppen verbundenen Blattinformationen gespeichert werden. Auf diese Weise können Sie einzelne Dokumente mit Hashes verfolgen, aber dennoch die gesamte Gruppe mit einem einzigen Zeitstempel versehen.

Der Grund, warum wir einzelne Dokumente in einer Gruppe mit dem PartialHashTree verfolgen können, ist, dass die PartialHashTree-Strukturen einen Merkle-Baum darstellen. Merkle-Bäume sind eine vielseitige Struktur, die unter Sicherheitsaspekten sehr gut verstanden wird und in allen Bereichen von Blockchain bis hin zu transparenten Zertifikaten verwendet wird. 

In diesem Fall sind Merkle-Bäume nützlich, weil sie es ermöglichen, einen Wurzel-Hash zu konstruieren, der alle Daten in den Blattknoten des Baums repräsentiert. Der Hash des Wurzelknotens liefert dann die Daten, die an einen regulären Zeitstempel-Server gesendet werden können, um einen Zeitstempel zu erhalten. Das Ergebnis ist, dass Sie eine Gruppe von Dokumenten mit einem Zeitstempel versehen und später einzelne Dokumente oder die gesamte Gruppe validieren können. Tatsächlich reduziert es alles auf den Punkt, an dem Sie immer noch einen gewöhnlichen Zeitstempelserver verwenden können, um eine Signatur zur Validierung Ihres ArchiveTimeStamp zu erzeugen.

Für ein einzelnes Dokument ist der PartialHashTree eine Folge von ASN.1-Oktet-String-Primitiven. Für eine Datengruppe oder einen Satz von Dokumenten werden Sie mehrere Hashes haben (einen pro Dokument), um den PartialHashTree zu konstruieren. Im Falle einer Datengruppe wird eine Kombination einzelner Hashes in den PartialHashTree berechnet, so dass jeder Hash als Verzweigungsknoten im Merkle-Baum dargestellt wird und nicht als einfacher Blattknoten (wie es bei einem einzelnen Dokument der Fall ist).

Mit einem PartialHashTree können Sie ein einzelnes Dokument oder eine Datengruppe sowie die Integrität der Gruppe als Ganzes überprüfen, indem Sie alle zugehörigen Hashes verfügbar machen. Durch die Verwendung der partiellen Verlaufsstruktur müssen Sie außerdem nicht den gesamten Merkle-Baum speichern (was allerdings bedeutet, dass Sie den Merkle-Baum im laufenden Betrieb rekonstruieren müssen).

Glücklicherweise gibt es einen einfachen iterativen Algorithmus für die Rekonstruktion eines Merkle-Baums aus den PartialHashTrees, d. h. Sie müssen ihn nicht im Speicher speichern, wenn Sie ihn überprüfen oder Anpassungen vornehmen. Der iterative Algorithmus wird im RFC anhand mehrerer grafischer Beispiele näher erläutert, die zeigen, wie Merkle-Bäume konstruiert und dekonstruiert werden können.

Bevor wir versuchen, einen ArchiveTimeStamp zu erstellen, müssen wir zunächst ein paar Dinge klären:

• Anders als bei einem regulären Zeitstempelprotokoll benötigt ERS Zugang zu den Daten, aus denen Sie den Merkle-Baum erstellen möchten. Bei einer normalen Zeitstempelsituation können Sie einfach einen Hash ohne Quelldaten senden, aber in diesem Fall verlangt die API, dass Sie ihr die Daten tatsächlich zur Verfügung stellen, damit sie Berechnungen und Verarbeitungen damit durchführen kann.
  
• Wir haben eine Schnittstelle mit der Bezeichnung ERS Data definiert, die es Ihnen ermöglicht, die Daten nach Ihren Wünschen zu verwalten, und wir haben auch die "Datengruppe" als eine Klasse innerhalb von ERS definiert. 
• Stellen Sie eine Klasse bereit, die alle Daten und Datengruppen zusammenführt, den Merkle-Baum aufbaut und einen Hash für den Wurzelknoten berechnet. Das ist der ERS-Typ ArchiveTimeStamp-Generator.

Auf dem Weg dorthin passiert unter der Oberfläche eine ganze Menge: Bäume werden im laufenden Betrieb konstruiert, Daten werden geparst und gehasht, Hashes werden gespeichert usw. Aber aus der Sicht eines API-Benutzers ist es ein ziemlich einfacher Prozess, der sich auf ein paar Zeilen Code reduziert. Letztendlich handelt es sich um einen zweistufigen Prozess, bei dem der Zeitstempeldienst in der Mitte steht:

1. Erstellen Sie zunächst Ihre Datenobjekte und richten Sie einen Digest-Rechner ein, um den zugrunde liegenden Hash bereitzustellen, der für die Konstruktion des Merkle-Baums verwendet wird. Dann können Sie die Datenobjekte hinzufügen.
2. Zweitens müssen Sie alles abschließen, indem Sie einen Zeitstempel-Anforderungsgenerator erstellen. Dabei handelt es sich um eine gut etablierte Bouncy Castle API, die für den Zeitstempeldienst entsprechend konfiguriert ist. Von dort aus können Sie diese an den ArchiveTimeStamp-Generator übergeben, um die Zeitstempelanforderung zurückzubekommen, die den Stammknoten des Merkle-Baums kapselt. Sobald die Antwort zurückkommt, können Sie sie dem ArchiveTimeStamp-Generator hinzufügen, um das eigentliche ArchiveTimeStamp-Objekt zu erzeugen.

Hier ist der Beispielcode für den ersten Schritt bei der Erzeugung eines ArchiveTimeStamp:

ERSData h1Doc = new ERSByteData(…); // Setup
ERSData h2Doc = new ERSByteData(…);
ERSDataGroup h3Docs = new ERSDataGroup(
new ERSData[]{new ERSByteData(…), new ERSByteData(…)});

DigestCalculator digestCalculator = digestCalculatorProvider.get(
new AlgorithmIdentifier(NISTObjectIdentifiers.id_sha256));

ERSArchiveTimeStampGenerator ersGen =
new ERSArchiveTimeStampGenerator(digestCalculator); // Init

ersGen.addData(h1Doc);
ersGen.addData(h2Doc);
ersGen.addData(h3Docs);

TimeStampRequestGenerator tspReqGen =
new TimeStampRequestGenerator();

tspReqGen.setCertReq(true);

TimeStampRequest tspReq =
ersGen.generateTimeStampRequest(tspReqGen);// Req

Im zweiten Schritt nehmen wir einfach die Antwort vom Zeitstempelserver und geben sie an den Generator zurück, um den ArchiveTimeStamp zu vervollständigen.

TimeStampResponse tsResp = ... // Antwort vom TSP-Server

ERSArchivZeitstempel ats =
ersGen.generateArchiveTimeStamp(tsResp);

In einer Post-Quantum-Welt ist es wichtig, dass es sich um langfristige Zeitstempel handelt. Darüber hinaus hat PrimeKey diesem Prozess bereits Unterstützung für LMS hinzugefügt, das nun sowohl vom NIST als auch von der IETF standardisiert ist, um ArchiveTimeStamps zu erzeugen. Wir werden weitere Post-Quantum-Signaturalgorithmen zu Bouncy Castle hinzufügen, wenn der NIST-Wettbewerb zu Ende geht.

Die hier beschriebene ERS-Funktionalität wird in BC 1.70 erscheinen und ist bereits im BCFJA enthalten. Wenn Sie mehr über die genaue Funktionsweise erfahren möchten, informieren Sie sich über die neuesten Entwicklungen bei NIST's PQC und erhalten Referenzen, um mehr über langfristige Lösungen für eine Post-Quantum-Welt zu erfahren, klicken Sie hier, um sich die gesamte Diskussion der PrimeKey Tech Days mit David Hook anzusehen.