SLH-DSA mathematisch erklärt

1. Worum es hier geht

Bei McGesund können Kunden im Tarif Bewertungen Premium und Signale Premium die Signaturstufe PQ-Dual-Diversified wählen. Dann trägt jeder QR-Code neben der klassischen Ed25519-Unterschrift zwei quantenresistente Unterschriften: ML-DSA-87 und SLH-DSA-SHA2-256f.

Dieser Beitrag erklärt die zweite. Sie ist anders gebaut als alles andere, was wir einsetzen.

SLH-DSA ist keine Verschlüsselung. Der Inhalt bleibt öffentlich lesbar. SLH-DSA beweist Herkunft und Unversehrtheit — wie jede digitale Signatur.

SLH-DSA heißt ausgeschrieben Stateless Hash-Based Digital Signature Algorithm. Es wurde aus SPHINCS+ entwickelt und 2024 als FIPS 205 standardisiert. Der Name verrät schon das Besondere: Das Verfahren verwendet nur Hashfunktionen. Keine Gitter, keine elliptischen Kurven, keine großen Primzahlen.

---

2. Was genau wird signiert?

SLH-DSA unterschreibt bei McGesund denselben Datensatz, den auch die Ed25519-Unterschrift im QR-Code abdeckt: den Payload des QR-Codes. Er enthält unter anderem, zu welchem Unternehmen der Code gehört (fid), welcher Art er ist (typ), wann er ausgestellt wurde (iat) und bis wann er gilt (exp) — als kompakt kodierte Bytefolge (CBOR).

Diese Bytefolge ist unsere Nachricht $M$. Ändert jemand nachträglich ein einziges Bit, passt keine der Unterschriften mehr.

Die SLH-DSA-Unterschrift steckt nicht im QR-Code selbst. Sie ist mit rund 49 KB viel zu groß dafür. Sie liegt als eigener „Stempel“ am QR-Datensatz im McGesund-Backend und wird beim Klick auf „Authentizität prüfen“ in den Browser geladen.

---

3. Warum ein Verfahren nur aus Hashfunktionen?

Jedes Signaturverfahren beruht auf einer Aufgabe, die ohne den geheimen Schlüssel praktisch unlösbar ist:

Ed25519 würde ein großer Quantencomputer brechen. FALCON und ML-DSA gelten als quantenresistent — aber beide stützen sich auf Gitterprobleme. Sollte eines Tages ein grundlegender Angriff auf Gitter gefunden werden, wären beide zugleich betroffen.

SLH-DSA braucht dagegen nur, dass die Hashfunktion das tut, wofür sie gebaut ist:

Das ist die am längsten und gründlichsten untersuchte Annahme der ganzen Kryptografie. Auch ein Quantencomputer hilft hier nur begrenzt: Der Grover-Algorithmus halbiert die Sicherheitsbits. Deshalb nutzt die Variante 256 Hashwerte mit $n = 32$ Byte $= 256$ Bit — nach Grover bleiben immer noch 128 Bit.

Genau darum heißt die Stufe Diversified: ML-DSA (Gitter) und SLH-DSA (Hash) stammen aus verschiedenen Mathematik-Familien. Fällt eine, trägt die andere.

---

4. Baustein 1: Unterschreiben mit Hashketten (WOTS+)

Die Grundidee ist überraschend einfach. Wir beginnen mit einer einzigen Ziffer.

Nimm einen geheimen Zufallswert $s$ und hashe ihn immer wieder:

Das Ende der Kette, $p$, wird veröffentlicht. Das ist der öffentliche Schlüssel für diese eine Ziffer.

Um eine Ziffer $d$ zwischen 0 und 15 zu unterschreiben, gibt man den Kettenwert an Position $d$ heraus:

Wer prüfen will, hasht $\sigma$ noch $15 - d$ Mal weiter. Kommt genau $p$ heraus, ist die Unterschrift echt:

Ein Mini-Beispiel

Wir unterschreiben die Ziffer $d = 6$:

• Der Unterzeichner veröffentlicht $\sigma = H^6(s)$.
• Der Prüfer rechnet $H^{9}(\sigma) = H^{15}(s)$ und vergleicht mit $p$. Passt.

Ein Fälscher, der $\sigma$ gesehen hat, kann daraus mühelos $H^7(s)$, $H^8(s)$ usw. berechnen — also größere Ziffern unterschreiben. Kleinere kann er nicht, dafür müsste er rückwärts hashen.

Die Prüfsumme gegen „Hochzählen“

Damit niemand Ziffern einfach erhöht, wird zusätzlich eine Prüfsumme unterschrieben:

Erhöht ein Fälscher eine Ziffer der Nachricht, wird $C$ kleiner — und dafür müsste er in der Prüfsummen-Kette rückwärts rechnen. Beide Richtungen sind damit gesperrt.

Hochgerechnet auf einen Hashwert

Ein Hashwert von 32 Byte hat 64 Ziffern zur Basis 16. Dazu kommen 3 Ziffern Prüfsumme:

Eine solche Unterschrift heißt WOTS+ (Winternitz One-Time Signature). Ihr großer Haken steckt im Namen: One-Time. Wer mit demselben Schlüssel zwei verschiedene Nachrichten unterschreibt, verrät so viele Kettenwerte, dass Fälschungen möglich werden.

---

5. Baustein 2: Viele Einmal-Schlüssel unter einem Dach (Merkle-Baum)

Wenn jeder Schlüssel nur einmal benutzt werden darf, braucht man sehr viele davon — aber man will nur einen öffentlichen Schlüssel veröffentlichen.

Die Lösung ist ein Merkle-Baum: Die öffentlichen Schlüssel von $2^{h'}$ WOTS+-Paaren bilden die Blätter. Je zwei Nachbarn werden zusammen gehasht, die Ergebnisse wieder paarweise, bis oben eine einzige Wurzel steht.

Bei SLH-DSA-SHA2-256f hat jeder Baum die Höhe $h' = 4$, also $2^4 = 16$ Blätter.

Um zu zeigen, dass ein bestimmtes Blatt zum Baum gehört, liefert man den Authentifizierungspfad: die 4 Geschwisterknoten auf dem Weg nach oben. Der Prüfer hasht sich damit vom Blatt bis zur Wurzel hoch. Kommt die bekannte Wurzel heraus, gehört das Blatt dazu.

---

6. Baustein 3: Bäume auf Bäumen (Hypertree)

16 Einmal-Schlüssel reichen natürlich nicht. Deshalb stapelt SLH-DSA Bäume übereinander: Die Wurzel eines Baums wird mit einem WOTS+-Schlüssel des Baums darüber unterschrieben. Dieser Turm heißt Hypertree.

Bei SLH-DSA-SHA2-256f gibt es $d = 17$ Lagen mit je Höhe 4:

Ganz unten stehen damit

Blätter zur Verfügung. Die Wurzel des obersten Baums heißt $\text{PK.root}$ — sie ist der eigentliche öffentliche Schlüssel.

Wichtig: Niemand berechnet diese Bäume vorab. Alle geheimen Werte werden bei Bedarf aus einem geheimen Startwert $\text{SK.seed}$ abgeleitet. Gespeichert werden nur vier Werte zu je 32 Byte:

Der private Schlüssel besteht aus allen vier (128 Byte), der öffentliche nur aus PK.seed und PK.root (64 Byte).

---

7. Baustein 4: Ein Wald gegen Zufallstreffer (FORS)

Jetzt das eigentliche Problem: Woher weiß der Unterzeichner, welches der $2^{68}$ Blätter noch unbenutzt ist?

Ältere hash-basierte Verfahren (XMSS, LMS) führen dafür einen Zähler. Der darf nie zurückgesetzt werden — nicht durch ein Backup, nicht durch einen zweiten Server. Passiert es doch, wird ein Einmal-Schlüssel doppelt benutzt, und das Verfahren ist gebrochen. Solche Verfahren heißen zustandsbehaftet.

SLH-DSA ist zustandslos: Das Blatt wird aus der Nachricht selbst pseudozufällig gewählt. Dann kann es vorkommen, dass zwei Nachrichten dasselbe Blatt treffen. Deshalb hängt ganz unten keine Einmal-Signatur, sondern eine Wenige-Mal-Signatur: FORS (Forest of Random Subsets).

FORS besteht aus $k = 35$ kleinen Merkle-Bäumen mit je $2^a = 2^9 = 512$ Blättern. Die Blätter sind geheime Zufallswerte.

Zum Unterschreiben wird der Nachrichten-Hash in 35 Zahlen zu je 9 Bit zerlegt. Jede Zahl wählt in „ihrem“ Baum genau ein Blatt. Die Unterschrift enthält für jeden Baum:

• den geheimen Wert dieses Blatts
• seinen Authentifizierungspfad (9 Knoten)

Ein Fälscher müsste für eine andere Nachricht in allen 35 Bäumen Blätter treffen, deren Geheimnisse schon verraten wurden. Selbst wenn dieselbe FORS-Instanz ein paar Mal benutzt wurde, ist das aussichtslos.

---

8. Der ganze Ablauf beim Unterschreiben

1. Zufallskomponente. Aus $\text{SK.prf}$, einer frischen Zufallszahl und der Nachricht entsteht ein 32-Byte-Wert $R$.
2. Nachrichten-Hash.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Die 49 Byte des Digests werden aufgeteilt: 40 Byte wählen die 35 FORS-Blätter, der Rest bestimmt, welcher Baum (idx_tree) und welches Blatt (idx_leaf) ganz unten im Hypertree benutzt wird.
3. FORS-Unterschrift über die Nachricht. Daraus ergibt sich ein FORS-öffentlicher Schlüssel.
4. Hypertree-Unterschrift über diesen FORS-Schlüssel: 17 WOTS+-Unterschriften mit je einem Authentifizierungspfad, Lage für Lage bis hinauf zu $\text{PK.root}$.

Die fertige Unterschrift ist einfach die Aneinanderreihung:

---

9. Warum die Unterschrift 49 856 Byte groß ist

Mit den Parametern von SLH-DSA-SHA2-256f lässt sich die Größe exakt nachrechnen ($n = 32$ Byte je Hashwert):

Zum Vergleich: Eine Ed25519-Unterschrift hat 64 Byte, ML-DSA-87 hat 4 627 Byte. Die Größe ist der Preis dafür, dass SLH-DSA mit nichts als Hashfunktionen auskommt.

---

10. Wie der Browser prüft

Prüfen heißt bei SLH-DSA: nachhashen.

1. Den Digest aus $R$, öffentlichem Schlüssel und Nachricht neu berechnen.
2. Aus den 35 aufgedeckten FORS-Blättern und ihren Pfaden die 35 Baumwurzeln berechnen und daraus den FORS-öffentlichen Schlüssel.
3. Mit jeder der 17 WOTS+-Unterschriften die Ketten zu Ende hashen, den öffentlichen WOTS+-Schlüssel bilden und über den Pfad zur Baumwurzel hochhashen.
4. Am Ende muss exakt $\text{PK.root}$ herauskommen.

Das sind einige tausend Hash-Aufrufe — für einen Computer eine Kleinigkeit. Im Browser dauert die Prüfung bei uns rund 6 bis 12 Millisekunden.

---

11. Was passiert, wenn jemand den Datensatz ändert?

Ändert sich auch nur ein Bit der Nachricht $M$, ändert sich der Digest vollständig. Damit zeigen die 35 Zahlen auf andere FORS-Blätter und das Verfahren auf einen anderen Platz im Hypertree.

Die aufgedeckten Geheimnisse passen nicht mehr: Die nachgerechneten Wurzeln weichen ab, und am Ende kommt nicht $\text{PK.root}$ heraus. Die Prüfung schlägt fehl.

Um trotzdem eine gültige Unterschrift zu bauen, müsste ein Angreifer Geheimnisse kennen, die nie veröffentlicht wurden — also eine Hashfunktion rückwärts rechnen.

---

12. Warum gerade 256f?

FIPS 205 definiert zwölf Parametersätze: zwei Hashfamilien (SHA-2 und SHAKE), drei Sicherheitsstufen (128, 192, 256) und je eine schnelle („f“) und eine kleine („s“) Variante.

256 heißt NIST-Sicherheitskategorie 5 — dieselbe Stufe wie FALCON-1024 und ML-DSA-87.

„f“ haben wir gewählt, weil Unternehmen bis zu 500 QR-Codes in einem Rutsch ausstellen können. Mit „s“ würde das Unterschreiben über 20 Minuten dauern, mit „f“ unter einer Minute. Dafür ist die Unterschrift größer — da sie nicht im QR-Code steckt, ist das verkraftbar.

SHA-2 statt SHAKE, weil SHA-256 und SHA-512 auf praktisch jeder Hardware beschleunigt sind.

---

13. Zufall beim Unterschreiben

FIPS 205 erlaubt zwei Arten, $R$ zu erzeugen:

• deterministisch: gleiche Nachricht, gleiche Unterschrift
• randomisiert („hedged“): eine frische Zufallszahl fließt mit ein

Wir verwenden die randomisierte Variante. Zwei Unterschriften über dieselbe Nachricht sehen deshalb verschieden aus — beide sind gültig. Das erschwert Angriffe, die Messungen am Gerät (Stromverbrauch, Zeit) mit wiederholten Unterschriften kombinieren.

---

14. Was McGesund konkret damit macht

Die Stufe. PQ-Dual-Diversified gibt es in Bewertungen Premium und Signale Premium. Ein QR-Code trägt dann drei Unterschriften:

Das Unterschreiben. Eine SLH-DSA-Unterschrift kostet rund eine Viertelsekunde Rechenzeit. Damit der Server währenddessen für alle anderen erreichbar bleibt, rechnen eigene Hintergrund-Threads.

Die Prüfung. Der Browser des Lesers lädt beide Stempel und prüft sie mit demselben WASM-Modul wie alle anderen PQ-Unterschriften. Wir liefern die Daten, gerechnet wird auf dem Gerät des Besuchers.

Der Abgleich mit NIST. Unser Modul besteht die offiziellen NIST-Testvektoren für SLH-DSA-SHA2-256f: Aus NISTs Startwerten entstehen Byte für Byte dieselben Schlüssel, und alle absichtlich manipulierten Signaturen werden abgelehnt. Das können Sie auf der NIST-Testseite selbst im Browser nachprüfen.

Der Zeitanker. Wie bei allen Schlüsseln wird der Fingerabdruck des SLH-DSA-Schlüssels über OpenTimestamps in einem Bitcoin-Block verankert.

---

15. SLH-DSA, ML-DSA und FALCON nebeneinander

Kurz gesagt: SLH-DSA ist das langsamste und größte der drei Verfahren — und das konservativste. Es setzt auf nichts, was nicht schon jede andere Signatur ohnehin voraussetzt: eine sichere Hashfunktion.

---

16. Ein Satz zum Mitnehmen

Wer den geheimen Startwert besitzt, unterschreibt in einer Viertelsekunde. Wer ihn nicht besitzt, müsste SHA-256 oder SHA-512 rückwärts rechnen — auch mit einem Quantencomputer.

Für den Leser einer Bewertung heißt das: Selbst wenn eines Tages alle Gitterverfahren fallen sollten, bleibt diese Unterschrift prüfbar. Er muss uns nicht glauben. Er kann nachrechnen.