SLH-DSA forklaret matematisk

1. Hvad det handler om

Hos McGesund kan kunder i abonnementerne Anmeldelser Premium og Signaler Premium vælge signaturniveauet PQ-Dual-Diversified. Så bærer hver QR-kode ud over den klassiske Ed25519-signatur to kvanteresistente signaturer: ML-DSA-87 og SLH-DSA-SHA2-256f.

Dette indlæg forklarer den anden. Den er bygget anderledes end alt andet, vi bruger.

SLH-DSA er ikke kryptering. Indholdet forbliver offentligt læsbart. SLH-DSA beviser oprindelse og uforanderlighed — som enhver digital signatur.

SLH-DSA står for Stateless Hash-Based Digital Signature Algorithm. Den er udviklet ud fra SPHINCS+ og blev i 2024 standardiseret som FIPS 205. Navnet afslører allerede det særlige: Metoden bruger kun hashfunktioner. Ingen gitre, ingen elliptiske kurver, ingen store primtal.

---

2. Hvad bliver præcist signeret?

Hos McGesund signerer SLH-DSA det samme datasæt, som Ed25519-signaturen i QR-koden også dækker: QR-kodens payload. Den indeholder blandt andet, hvilken virksomhed koden hører til (fid), hvilken slags kode det er (typ), hvornår den blev udstedt (iat), og hvor længe den gælder (exp) — som en kompakt kodet bytefølge (CBOR).

Denne bytefølge er vores besked $M$. Ændrer nogen bagefter en eneste bit, passer ingen af signaturerne længere.

SLH-DSA-signaturen sidder ikke i selve QR-koden. Med omkring 49 KB er den alt for stor til det. Den ligger som et selvstændigt „stempel“ ved QR-datasættet i McGesund-backend og hentes ind i browseren, når man klikker på „Tjek ægthed“.

---

3. Hvorfor en metode udelukkende af hashfunktioner?

Enhver signaturmetode bygger på en opgave, der praktisk talt er uløselig uden den hemmelige nøgle:

Ed25519 ville en stor kvantecomputer bryde. FALCON og ML-DSA anses for kvanteresistente — men begge støtter sig til gitterproblemer. Skulle der en dag blive fundet et grundlæggende angreb på gitre, ville begge blive ramt på én gang.

SLH-DSA behøver derimod kun, at hashfunktionen gør det, den er bygget til:

Det er den længst og grundigst undersøgte antagelse i hele kryptografien. Selv en kvantecomputer hjælper her kun begrænset: Grover-algoritmen halverer sikkerhedsbittene. Derfor bruger 256-varianten hashværdier på $n = 32$ byte $= 256$ bit — efter Grover er der stadig 128 bit tilbage.

Netop derfor hedder niveauet Diversified: ML-DSA (gitre) og SLH-DSA (hash) stammer fra forskellige matematiske familier. Falder den ene, bærer den anden.

---

4. Byggesten 1: at underskrive med hashkæder (WOTS+)

Grundidéen er overraskende enkel. Vi begynder med et enkelt ciffer.

Tag en hemmelig tilfældig værdi $s$, og hash den igen og igen:

Enden af kæden, $p$, bliver offentliggjort. Det er den offentlige nøgle for netop dette ene ciffer.

For at underskrive et ciffer $d$ mellem 0 og 15 udleverer man kædeværdien på position $d$:

Den, der vil verificere, hasher $\sigma$ yderligere $15 - d$ gange. Kommer der præcis $p$ ud, er signaturen ægte:

Et mini-eksempel

Vi underskriver cifferet $d = 6$:

• Underskriveren offentliggør $\sigma = H^6(s)$.
• Verifikatoren beregner $H^{9}(\sigma) = H^{15}(s)$ og sammenligner med $p$. Det passer.

En forfalsker, der har set $\sigma$, kan ud fra den uden besvær beregne $H^7(s)$, $H^8(s)$ osv. — altså underskrive større cifre. Mindre kan han ikke, for så skulle han hashe baglæns.

Kontrolsummen mod „optælling“

For at ingen blot kan forhøje cifre, underskrives der desuden en kontrolsum:

Forhøjer en forfalsker et ciffer i beskeden, bliver $C$ mindre — og så skulle han regne baglæns i kontrolsummens kæde. Dermed er begge retninger spærret.

Opskaleret til en hashværdi

En hashværdi på 32 byte har 64 cifre i base 16. Dertil kommer 3 cifre kontrolsum:

En sådan signatur hedder WOTS+ (Winternitz One-Time Signature). Dens store hage ligger i navnet: One-Time — engangsbrug. Den, der underskriver to forskellige beskeder med samme nøgle, afslører så mange kædeværdier, at forfalskninger bliver mulige.

---

5. Byggesten 2: mange engangsnøgler under ét tag (Merkle-træ)

Når hver nøgle kun må bruges én gang, har man brug for rigtig mange af dem — men man vil kun offentliggøre én offentlig nøgle.

Løsningen er et Merkle-træ: De offentlige nøgler fra $2^{h'}$ WOTS+-par udgør bladene. To naboer ad gangen hashes sammen, resultaterne igen parvis, indtil der øverst står en enkelt rod.

I SLH-DSA-SHA2-256f har hvert træ højden $h' = 4$, altså $2^4 = 16$ blade.

For at vise, at et bestemt blad hører til træet, leverer man autentificeringsstien: de 4 søskendeknuder på vejen opad. Med dem hasher verifikatoren sig fra bladet op til roden. Kommer den kendte rod ud, hører bladet med.

---

6. Byggesten 3: træer oven på træer (hypertræ)

16 engangsnøgler rækker selvfølgelig ikke. Derfor stabler SLH-DSA træer oven på hinanden: Roden af et træ underskrives med en WOTS+-nøgle fra træet ovenover. Dette tårn kaldes hypertræet.

I SLH-DSA-SHA2-256f er der $d = 17$ lag, hvert med højden 4:

Helt nederst står der dermed

blade til rådighed. Roden af det øverste træ hedder $\text{PK.root}$ — den er den egentlige offentlige nøgle.

Vigtigt: Ingen beregner disse træer på forhånd. Alle hemmelige værdier afledes efter behov fra en hemmelig startværdi $\text{SK.seed}$. Der gemmes kun fire værdier på hver 32 byte:

Den private nøgle består af alle fire (128 byte), den offentlige kun af PK.seed og PK.root (64 byte).

---

7. Byggesten 4: en skov mod tilfældige træffere (FORS)

Nu det egentlige problem: Hvordan ved underskriveren, hvilket af de $2^{68}$ blade der stadig er ubrugt?

Ældre hashbaserede metoder (XMSS, LMS) fører til det formål en tæller. Den må aldrig nulstilles — hverken af en backup eller af en anden server. Sker det alligevel, bliver en engangsnøgle brugt to gange, og metoden er brudt. Sådanne metoder kaldes tilstandsbehæftede.

SLH-DSA er tilstandsløs: Bladet vælges pseudotilfældigt ud fra selve beskeden. Så kan det ske, at to beskeder rammer det samme blad. Derfor hænger der helt nederst ikke en engangssignatur, men en få-gangssignatur: FORS (Forest of Random Subsets).

FORS består af $k = 35$ små Merkle-træer med hver $2^a = 2^9 = 512$ blade. Bladene er hemmelige tilfældige værdier.

For at underskrive deles beskedens hash op i 35 tal på hver 9 bit. Hvert tal vælger præcis ét blad i „sit“ træ. Signaturen indeholder for hvert træ:

• den hemmelige værdi for dette blad
• dets autentificeringssti (9 knuder)

En forfalsker skulle for en anden besked ramme blade i alle 35 træer, hvis hemmeligheder allerede er blevet afsløret. Selv hvis den samme FORS-instans er blevet brugt et par gange, er det håbløst.

---

8. Hele forløbet ved underskrivning

1. Tilfældig komponent. Ud fra $\text{SK.prf}$, et frisk tilfældigt tal og beskeden opstår en 32-byte-værdi $R$.
2. Beskedens hash.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Digestens 49 byte fordeles: 40 byte vælger de 35 FORS-blade, resten bestemmer, hvilket træ (idx_tree) og hvilket blad (idx_leaf) helt nederst i hypertræet der bruges.
3. FORS-signatur over beskeden. Ud af den fremkommer en offentlig FORS-nøgle.
4. Hypertræ-signatur over denne FORS-nøgle: 17 WOTS+-signaturer med hver sin autentificeringssti, lag for lag helt op til $\text{PK.root}$.

Den færdige signatur er simpelthen sammenkædningen:

---

9. Hvorfor signaturen fylder 49.856 byte

Med parametrene for SLH-DSA-SHA2-256f kan størrelsen regnes nøjagtigt efter ($n = 32$ byte pr. hashværdi):

Til sammenligning: En Ed25519-signatur fylder 64 byte, ML-DSA-87 fylder 4.627 byte. Størrelsen er prisen for, at SLH-DSA klarer sig med intet andet end hashfunktioner.

---

10. Sådan verificerer browseren

At verificere betyder ved SLH-DSA: at hashe efter.

1. Beregn digesten igen ud fra $R$, den offentlige nøgle og beskeden.
2. Beregn ud fra de 35 afslørede FORS-blade og deres stier de 35 trærødder og ud fra dem den offentlige FORS-nøgle.
3. Hash med hver af de 17 WOTS+-signaturer kæderne til ende, dan den offentlige WOTS+-nøgle, og hash dig via stien op til træets rod.
4. Til sidst skal der komme præcis $\text{PK.root}$ ud.

Det er nogle tusind hashkald — en bagatel for en computer. I browseren tager verifikationen hos os omkring 6 til 12 millisekunder.

---

11. Hvad sker der, hvis nogen ændrer datasættet?

Ændrer blot én bit af beskeden $M$ sig, ændrer digesten sig fuldstændigt. Dermed peger de 35 tal på andre FORS-blade og metoden på en anden plads i hypertræet.

De afslørede hemmeligheder passer ikke længere: De efterregnede rødder afviger, og til sidst kommer der ikke $\text{PK.root}$ ud. Verifikationen mislykkes.

For alligevel at bygge en gyldig signatur skulle en angriber kende hemmeligheder, der aldrig er blevet offentliggjort — altså regne en hashfunktion baglæns.

---

12. Hvorfor netop 256f?

FIPS 205 definerer tolv parametersæt: to hashfamilier (SHA-2 og SHAKE), tre sikkerhedsniveauer (128, 192, 256) og for hver en hurtig („f“) og en lille („s“) variant.

256 betyder NIST-sikkerhedskategori 5 — samme niveau som FALCON-1024 og ML-DSA-87.

„f“ har vi valgt, fordi virksomheder kan udstede op til 500 QR-koder i ét hug. Med „s“ ville underskrivningen tage over 20 minutter, med „f“ under et minut. Til gengæld er signaturen større — men da den ikke sidder i QR-koden, er det til at leve med.

SHA-2 i stedet for SHAKE, fordi SHA-256 og SHA-512 er hardwareaccelereret på praktisk talt al hardware.

---

13. Tilfældighed ved underskrivning

FIPS 205 tillader to måder at danne $R$ på:

• deterministisk: samme besked, samme signatur
• randomiseret („hedged“): et frisk tilfældigt tal indgår

Vi bruger den randomiserede variant. To signaturer over den samme besked ser derfor forskellige ud — begge er gyldige. Det gør angreb sværere, der kombinerer målinger på enheden (strømforbrug, tid) med gentagne signaturer.

---

14. Hvad McGesund konkret bruger det til

Niveauet. PQ-Dual-Diversified findes i Anmeldelser Premium og Signaler Premium. En QR-kode bærer så tre signaturer:

Underskrivningen. En SLH-DSA-signatur koster omkring et kvart sekunds regnetid. For at serveren i mellemtiden forbliver tilgængelig for alle andre, regner egne baggrundstråde.

Verifikationen. Læserens browser henter begge stempler og verificerer dem med det samme WASM-modul som alle andre PQ-signaturer. Vi leverer data; regnearbejdet sker på den besøgendes enhed.

Afstemningen med NIST. Vores modul består de officielle NIST-testvektorer for SLH-DSA-SHA2-256f: Ud fra NIST's startværdier opstår byte for byte de samme nøgler, og alle bevidst manipulerede signaturer bliver afvist. Det kan du selv efterprøve i browseren på NIST-testsiden.

Tidsankeret. Som for alle nøgler forankres SLH-DSA-nøglens fingeraftryk via OpenTimestamps i en Bitcoin-blok.

---

15. SLH-DSA, ML-DSA og FALCON side om side

Kort sagt: SLH-DSA er den langsomste og største af de tre metoder — og den mest konservative. Den bygger ikke på noget, som enhver anden signatur ikke allerede forudsætter: en sikker hashfunktion.

---

16. En sætning at tage med

Den, der besidder den hemmelige startværdi, underskriver på et kvart sekund. Den, der ikke besidder den, skulle regne SHA-256 eller SHA-512 baglæns — også med en kvantecomputer.

For den, der læser en anmeldelse, betyder det: Selv hvis alle gittermetoder en dag skulle falde, kan denne signatur stadig verificeres. Han behøver ikke tro på os. Han kan regne efter.