Was ist hashbasierte Kryptografie?

Definition: Die hashbasierte Kryptografie wurde erstmals Ende der 1970er Jahre von Leslie Lamport und Ralph Merkle entwickelt. Bei der hashbasierten Kryptografie werden Algorithmen für digitale Signaturen erstellt, deren Sicherheit mathematisch auf der Sicherheit einer ausgewählten kryptografischen Hashfunktion beruht.

Erläuterungen zur hashbasierten Kryptografie

Eine Hashfunktion ist ein eindeutiger Identifikator für einen bestimmten Inhalt. Sie ist auch ein Verfahren, das Klartextdaten beliebiger Größe in einen eindeutigen Chiffretext einer bestimmten Länge umwandelt. Hashfunktionen nehmen eine Eingabezeichenkette (normalerweise oder von beliebiger Länge) und geben einen „Digest“ fester Größe als Ausgabe zurück. Gängige kryptografische Hashfunktionen wie SHA2, SHA3 oder Blake2 erzeugen Digests im Bereich von 256 Bit bis 512 Bit.

Ein hashbasiertes Signaturschema geht von einem einmaligen Signaturschema (OTS) aus, einem Signaturschema, bei dem ein Schlüsselpaar nur zum Signieren einer einzigen Nachricht verwendet werden muss. Wenn ein OTS-Schlüsselpaar zum Signieren von zwei verschiedenen Nachrichten verwendet wird, kann ein Angreifer die Signaturen leicht fälschen.

Merkle schlug jedoch einen Weg vor, um die Fähigkeit, n verschiedene Nachrichten zu signieren, beizubehalten:

1. Zuerst werden n separate Lamport-Schlüsselpaare erzeugt. Ein Beispiel könnte (PK_1, SK_1), \dots, (PK_N, SK_N) sein

2. Anschließend wird jeder öffentliche Schlüssel einem Blatt eines Hash-Baums (siehe unten) zugeordnet und die Wurzel des Baums berechnet. Diese Wurzel dient als öffentlicher „Master“-Schlüssel der neuen Merkle-Signatur.

3. Der Unterzeichner behält alle öffentlichen und geheimen Lamport-Schlüssel zur Verwendung beim Signieren.

Ein Merkle-Baum (oder Hash-Baum) ist eine Datenstruktur, die als Baum dargestellt wird. Jeder Blattknoten wird durch den kryptografischen Hashwert eines Datenblocks und jeder Nicht-Blattknoten durch den kryptografischen Hashwert der Labels seiner Kindknoten identifiziert. Hash-Bäume ermöglichen eine effiziente und sichere Überprüfung des Inhalts großer Datenstrukturen.

Jede Blockebene im obigen Hash-Baum spiegelt eine höhere Hash-Ordnung wider, die aus einer Transaktion (T0-T7) stammt. Der nachfolgende Hashwert (H) durchläuft für jede Blockebene oberhalb der ursprünglichen Transaktion eine Hashfunktion, bis er die höchste Blockebene erreicht, die als Summe aller vorhergehenden Hashwerte (H01234567) dargestellt wird.

Die Hashwerte der untersten Ebene werden als Blätter bezeichnet und enthalten den Hashwert der mit dem Blatt verknüpften Transaktion (T). Die Ebenen 3 und 4 sind die Ergebnisse der Hashwerte der Blätter und ihrer nachfolgenden Hashwerte (oder Knoten). Die Merkle-Wurzel schließlich, die oberste Ebene des Blocks, enthält die Zusammenfassung aller Transaktionsdaten in einem einzigen Wert.

Seit dem ursprünglichen Ansatz von Merkle wurden zahlreiche hashbasierte Signaturverfahren mit verbesserter Leistung entwickelt. Aktuelle Beispiele sind die Verfahren XMSS, Leighton-Micali (LMS), SPHINCS und BPQS. Im Gegensatz zu typischen digitalen Signaturverfahren sind die meisten hashbasierten Signaturverfahren zustandsbehaftet, was bedeutet, dass die Signatur eine Aktualisierung des geheimen Schlüssels erfordert.

Beim Signieren mit zustandsbehafteten hashbasierten Signaturverfahren müssen die verwendeten Einmalschlüssel zurückverfolgt und sichergestellt werden, dass sie niemals wiederholt werden. Die Verfahren XMSS, LMS und BPQS sind zustandsbehaftet, während das Verfahren SPHINCS zustandslos ist. Die Signaturen bei SPHINCS sind größer als bei XMSS und LMS. BPQS wurde im Hinblick auf Blockchain-Systeme entwickelt. Zusätzlich zum WOTS+ Einmal-Signaturverfahren verwendet SPHINCS das HORST-Verfahren für (hashbasierte) Mehrmal-Signaturen. HORST ist eine Weiterentwicklung eines älteren Mehrmal-Signaturverfahrens (Hash to Obtain Random Subset).

Die drei vom NIST zu standardisierenden digitalen Signaturalgorithmen* (basierend auf strukturierten Gittern) für quantensichere digitale Signaturen sind: