Die hashbasierte Kryptografie wurde im Jahr 1979 mit der Einführung des Lamport-Einmal-Signaturverfahrens von Leslie Lamport, einem US-amerikanischen Mathematiker und Informatiker, ins Leben gerufen. Die hashbasierte Kryptografie erlaubt die Umsetzung von Signaturverfahren, deren Sicherheit auf der Unumkehrbarkeit und Kollisionsresistenz einer zugrunde liegenden kryptografischen Hashfunktion basiert. Dementsprechend ist, aufgrund der Unumkehrbarkeit, das einzige Anwendungsgebiet die Erstellung von digitalen Signaturen. Bisher wurden für diese Signaturverfahren keine Angriffe gefunden, die nicht durch eine einfache Erhöhung der Sicherheitsparameter abgewehrt werden könnten - selbst nicht mithilfe von Quantencomputern. Das macht sie zu vielversprechenden Kandidaten für die Post-Quanten-Kryptografie. Die grundlegenden Einmalsignaturverfahren zeichnen sich, neben ihrer Sicherheit, besonders durch ihren geringen Rechenaufwand aus, allerdings können sie, wie der Name schon sagt, nur einmal verwendet werden. Alternativ ermöglichen modifizierte Verfahren Mehrfachsignaturen, verlangen jedoch zusätzlichen Rechenaufwand.

Eine Hashfunktion ist eine effizient berechenbare Abbildung, die eine beliebig große Eingabemenge auf eine Zielmenge mit fester Größe reduziert.

Beispielsweise könnte es eine Abbildung \(h\) geben, die als Eingabe eine beliebig lange Zeichenfolge aus Nullen und Einsen entgegennimmt und diese auf eine 16 Zeichen lange Zeichenfolge aus Nullen und Einsen abbildet. Es könnte dann gelten:

Das Lamport-Einmal-Signaturverfahren wurde erstmals 1979 von L. Lamport vorgestellt. Es gilt mit angemessenen Sicherheitsparametern weiterhin als robust gegenüber klassischen und Quanten-Algorithmen. Dennoch wird es heutzutage in seiner ursprünglichen Form nicht mehr verwendet, da es nur einmal genutzt werden kann und die resultierenden Signaturen sehr lang sind. Trotzdem bildet es eine solide Grundlage, um eine tiefere Auseinandersetzung mit der hashbasierten Kryptografie zu ermöglichen, weshalb es hier vorgestellt wird.

Zuerst wird mithilfe der Nachricht \(m\) und der kryptografischen Hashfunktion \(f\) der Hashwert \(h = f(m) \in \{0,1\}^n\) gebildet. Anschließend kann die Signatur \(S\) gebildet werden, indem aus jedem Paar in \(X\) ein Wert gewählt wird. Ist das \(i\)-te Bit in \(h\) gleich \(0\), gilt \(s_i = x_{i,0}\), handelt es sich um eine \(1\), gilt \(s_i = x_{i,1}\).

Zuerst bildet der Empfänger ebenfalls \(h = f(m) \in \{0,1\}^n\). Anschließend muss die Einwegfunktion \(g\) auf alle Komponenten der Signatur \(S\) angewendet werden, um \(V\) zu bilden:

Um die Signatur zu verifizieren, müssen die Komponenten in \(V\) ähnlich wie bei der Erstellung der Signatur mit den entsprechenden Komponenten im öffentlichen Schlüssel \(Y\) verglichen werden. Ist das \(i\)-te Bit in \(h\) gleich \(0\), muss gelten \(v_i = y_{i,0}\), handelt es sich um eine \(1\), muss gelten \(v_i = y_{i,1}\).

Zur Verbesserung der Übersichtlichkeit verwenden wir in diesem Beispiel den Sicherheitsparameter \(n = 8\). Die Zeichenfolgen aus Nullen und Einsen stellen wir in Dezimaldarstellung dar, also als ganze Zahl von \(0\) bis \(2^n-1 = 255\). Sowohl als kryptografische Hashfunktion \(f\), als auch als Einwegfunktion \(g\) nutzen wir die Hashfunktion "SHA256", eine Variante des kryptografischen Hashalgorithmus "Secure Hash Algorithm", dem der Bitstring als Eingabe übergeben wird. In diesem Fall werden aber lediglich die ersten 8-Bits der Ausgabe als Hashwerte verwendet.

Erst generiert man \(8\) Paare man aus jeweils zwei Werten aus \(\{0,...,255\}\), um den privaten Schlüssel zu erhalten:

Anschließend kann der öffentliche Schlüssel gebildet werden, indem \(8\) Paare aus den Hashwerten der entsprechenden Werte im privaten Schlüssel mithilfe der Einwegfunktion \(g\) gebildet werden:

Dem Empfänger liegen nun die Nachricht \(m\), die Signatur \(S\) und der öffentliche Schlüssel \(Y\) vor. Darüber hinaus kennt er die kryptografische Hashfunktion \(f\) und die Einwegfunktion \(g\).

Da bei jeder Signatur die Hälfte des privaten Schlüssels veröffentlicht werden muss, lässt sich, wie der Name bereits impliziert, das Lamport-Einmal-Signaturverfahren nur einmal pro Schlüsselpaar verwenden. Dasselbe gilt für das sogenannte "Winternitz Einmalsignaturverfahren", ein weiteres grundlegendes Verfahren der hashbasierten Kryptografie (s. 4.1.). Es sind zwei Methoden bekannt, die es ermöglichen, diese Einmalsignaturverfahren zu Mehrfachsignaturverfahren zu modifizieren: Das Chaining von Nachrichten und das Merkle-Baum Signaturverfahren.

Dadurch ist es zum Verifizieren der Signatur einer Nachricht jedoch notwendig, dass dem Empfänger ebenfalls alle vorherigen Signaturen vorliegen. Diese müssen bei jeder Nachricht angehängt werden. Das bedeutet, dass die Länge der Signatur einer Nachricht mit jeder weiteren Iteration des Verfahrens linear ansteigt. Darüber hinaus steigt auch der Rechenaufwand, den der Empfänger beim Verifizieren leisten muss, da er jede einzelne Nachricht der Kette prüfen muss. Außerdem wird mit jeder Signatur zusätzliche Information veröffentlicht, nämlich wie viele Signaturen bereits erstellt wurden. Aus diesen Gründen wird auf dieses Verfahren in der Regel zugunsten des Merkle-Baum Signaturverfahrens verzichtet.

Als erstes muss eine Höhe \(H \in \mathbb{N} \geq 2\) des Binärbaumes festgelegt werden. Jedes Blatt dieses Binärbaumes entspricht einer möglichen Signatur. Bei einem Binärbaum der Höhe \(H\) sind also \(2^H\) Signaturen möglich. Zusätzlich müssen ein Einmalsignaturverfahren und eine kryptografische Hashfunktion \(f\) ausgewählt werden.

Um eine Nachricht zu signieren, wählt der Sender den nächsten unbenutzten privaten Schlüssel und bildet die Signatur mithilfe des Einmalsignaturverfahrens. Anschließend veröffentlicht er, wie immer, die Nachricht, die Signatur und den passenden öffentlichen Schlüssel zum genutzten privaten Schlüssel. Zusätzlich veröffentlicht er den Index des genutzten Blattes und die Hashwerte der Geschwisterknoten aller Knoten, die auf dem Pfad von dem genutzten Blatt zur Wurzel liegen.

Wenn wir \(X_1\) verwendet haben, liegen \(k_{2,1}\) und \(k_{1,0}\) auf dem Pfad zur Wurzel \(k_{0,0}\). Es müssen also die Werte der Geschwisterknoten von \(k_{2,1}\) und \(k_{1,0}\), also \(k_{2,0}\) und \(k_{1,1}\), mitveröffentlicht werden. Des Weiteren veröffentlichen wir den Index des Blattes, also in diesem Fall \(i = 1\).

Der Empfänger bildet den Hashwert des mitgesendeten öffentlichen Schlüssels \(Y_1\) und erhält \(k_{2,1}\). Da \(i=1\) ungerade ist, wird der erste mitgesendete Hashwert \(k_{2,0}\) vorne an \(k_{2,1}\) angehängt. Er bildet also den Hashwert \(f(k_{2,0}||k_{2,1})\) und erhält \(k_{1,0}\). Den Index dieses Knotens berechnet er mittels \(i_{Eltern} = \lfloor \frac {1}{2} \rfloor = 0\). Dann hängt er \(k_{1,1}\) hinten an den neuen Hashwert, da der neue Index gerade ist. Er bildet den Hashwert \(f(k_{1,0}||k_{1,1})\) und erhält \(k_{0,0}\). Damit gilt \(Y_1\) gültig, da \(k_{0,0}\) der übergeordnete öffentliche Schlüssel ist.