SLH-DSA matematiskt förklarat

1. Vad det handlar om

Hos McGesund kan kunder med abonnemangen Omdömen Premium och Signaler Premium välja signaturnivån PQ-Dual-Diversified. Då bär varje QR-kod, utöver den klassiska Ed25519-signaturen, två kvantresistenta signaturer: ML-DSA-87 och SLH-DSA-SHA2-256f.

Denna artikel förklarar den andra. Den är uppbyggd annorlunda än allt annat vi använder.

SLH-DSA är ingen kryptering. Innehållet förblir offentligt läsbart. SLH-DSA bevisar ursprung och oförändrat innehåll — som varje digital signatur.

SLH-DSA står utskrivet för Stateless Hash-Based Digital Signature Algorithm. Den utvecklades ur SPHINCS+ och standardiserades 2024 som FIPS 205. Namnet avslöjar redan det särskilda: metoden använder enbart hashfunktioner. Inga gitter, inga elliptiska kurvor, inga stora primtal.

---

2. Vad är det exakt som signeras?

Hos McGesund signerar SLH-DSA samma datapost som Ed25519-signaturen i QR-koden också täcker: QR-kodens payload. Den anger bland annat vilket företag koden hör till (fid), vilken typ den är (typ), när den utfärdades (iat) och hur länge den gäller (exp) — som en kompakt kodad bytesekvens (CBOR).

Denna bytesekvens är vårt meddelande $M$. Ändrar någon i efterhand en enda bit, stämmer ingen av signaturerna längre.

SLH-DSA-signaturen ligger inte i själva QR-koden. Med omkring 49 KB är den alldeles för stor för det. Den ligger som en egen ”stämpel” vid QR-posten i McGesunds backend och laddas in i webbläsaren när man klickar på ”Verifiera äkthet”.

---

3. Varför en metod som bara bygger på hashfunktioner?

Varje signaturmetod vilar på en uppgift som utan den hemliga nyckeln är praktiskt taget olöslig:

En stor kvantdator skulle knäcka Ed25519. FALCON och ML-DSA anses vara kvantresistenta — men båda stöder sig på gitterproblem. Skulle man en dag hitta en grundläggande attack mot gitter, skulle båda drabbas samtidigt.

SLH-DSA behöver däremot bara att hashfunktionen gör det den är byggd för:

Detta är det längst och grundligast undersökta antagandet i hela kryptografin. Även en kvantdator hjälper här bara begränsat: Grovers algoritm halverar säkerhetsbitarna. Därför använder varianten 256 hashvärden med $n = 32$ byte $= 256$ bitar — efter Grover återstår fortfarande 128 bitar.

Det är just därför nivån heter Diversified: ML-DSA (gitter) och SLH-DSA (hash) kommer från olika matematiska familjer. Faller den ena, bär den andra.

---

4. Byggsten 1: signera med hashkedjor (WOTS+)

Grundidén är förvånansvärt enkel. Vi börjar med en enda siffra.

Ta ett hemligt slumpvärde $s$ och hasha det om och om igen:

Kedjans slut, $p$, publiceras. Det är den offentliga nyckeln för just denna siffra.

För att signera en siffra $d$ mellan 0 och 15 lämnar man ut kedjevärdet på position $d$:

Den som vill verifiera hashar $\sigma$ ytterligare $15 - d$ gånger. Kommer exakt $p$ ut, är signaturen äkta:

Ett minimiexempel

Vi signerar siffran $d = 6$:

• Undertecknaren publicerar $\sigma = H^6(s)$.
• Verifieraren räknar ut $H^{9}(\sigma) = H^{15}(s)$ och jämför med $p$. Det stämmer.

En förfalskare som har sett $\sigma$ kan utan ansträngning räkna fram $H^7(s)$, $H^8(s)$ och så vidare — alltså signera större siffror. Mindre kan hen inte, för då skulle hen behöva hasha baklänges.

Kontrollsumman mot ”uppräkning”

För att ingen helt enkelt ska kunna öka siffror signeras dessutom en kontrollsumma:

Ökar en förfalskare en siffra i meddelandet blir $C$ mindre — och för det skulle hen behöva räkna baklänges i kontrollsummans kedja. Därmed är båda riktningarna spärrade.

Uppskalat till ett hashvärde

Ett hashvärde på 32 byte har 64 siffror i bas 16. Till det kommer 3 siffror kontrollsumma:

En sådan signatur kallas WOTS+ (Winternitz One-Time Signature). Dess stora hake finns i namnet: One-Time, engångs. Den som signerar två olika meddelanden med samma nyckel avslöjar så många kedjevärden att förfalskningar blir möjliga.

---

5. Byggsten 2: många engångsnycklar under samma tak (Merkleträd)

Om varje nyckel bara får användas en gång behöver man väldigt många av dem — men man vill bara publicera en offentlig nyckel.

Lösningen är ett Merkleträd: de offentliga nycklarna för $2^{h'}$ WOTS+-par bildar löven. Två grannar i taget hashas samman, resultaten åter parvis, tills en enda rot står överst.

I SLH-DSA-SHA2-256f har varje träd höjden $h' = 4$, alltså $2^4 = 16$ löv.

För att visa att ett visst löv hör till trädet levererar man autentiseringsvägen: de 4 syskonnoderna på vägen uppåt. Med dem hashar verifieraren sig från lövet ända upp till roten. Kommer den kända roten ut, hör lövet till trädet.

---

6. Byggsten 3: träd på träd (hyperträd)

16 engångsnycklar räcker förstås inte. Därför staplar SLH-DSA träd på varandra: roten i ett träd signeras med en WOTS+-nyckel i trädet ovanför. Detta torn kallas hyperträd.

I SLH-DSA-SHA2-256f finns $d = 17$ lager, vart och ett med höjden 4:

Längst ner står därmed

löv till förfogande. Roten i det översta trädet heter $\text{PK.root}$ — den är den egentliga offentliga nyckeln.

Viktigt: ingen räknar ut dessa träd i förväg. Alla hemliga värden härleds vid behov ur en hemlig seed $\text{SK.seed}$. Endast fyra värden på vardera 32 byte lagras:

Den privata nyckeln består av alla fyra (128 byte), den offentliga bara av PK.seed och PK.root (64 byte).

---

7. Byggsten 4: en skog mot slumpträffar (FORS)

Nu det egentliga problemet: hur vet undertecknaren vilket av de $2^{68}$ löven som fortfarande är oanvänt?

Äldre hashbaserade metoder (XMSS, LMS) håller för detta en räknare. Den får aldrig återställas — varken genom en säkerhetskopia eller genom en andra server. Händer det ändå används en engångsnyckel två gånger, och metoden är knäckt. Sådana metoder kallas tillståndsbaserade.

SLH-DSA är tillståndslös: lövet väljs pseudoslumpmässigt ur själva meddelandet. Då kan det hända att två meddelanden träffar samma löv. Därför hänger längst ner ingen engångssignatur, utan en fåtalsgångssignatur: FORS (Forest of Random Subsets).

FORS består av $k = 35$ små Merkleträd med vardera $2^a = 2^9 = 512$ löv. Löven är hemliga slumpvärden.

För att signera delas meddelandets hash upp i 35 tal om vardera 9 bitar. Varje tal väljer exakt ett löv i ”sitt” träd. Signaturen innehåller för varje träd:

• det hemliga värdet för detta löv
• dess autentiseringsväg (9 noder)

En förfalskare skulle för ett annat meddelande behöva träffa löv i alla 35 träd vars hemligheter redan har avslöjats. Även om samma FORS-instans har använts några gånger är det hopplöst.

---

8. Hela förloppet vid signering

1. Slumpkomponent. Ur $\text{SK.prf}$, ett nytt slumptal och meddelandet uppstår ett 32-bytevärde $R$.
2. Meddelandehash.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Digestens 49 byte delas upp: 40 byte väljer de 35 FORS-löven, resten bestämmer vilket träd (idx_tree) och vilket löv (idx_leaf) längst ner i hyperträdet som används.
3. FORS-signatur över meddelandet. Ur den fås en offentlig FORS-nyckel.
4. Hyperträdssignatur över denna FORS-nyckel: 17 WOTS+-signaturer med vardera en autentiseringsväg, lager för lager ända upp till $\text{PK.root}$.

Den färdiga signaturen är helt enkelt sammanfogningen:

---

9. Varför signaturen är 49 856 byte stor

Med parametrarna för SLH-DSA-SHA2-256f kan storleken räknas ut exakt ($n = 32$ byte per hashvärde):

Som jämförelse: en Ed25519-signatur är 64 byte, ML-DSA-87 är 4 627 byte. Storleken är priset för att SLH-DSA klarar sig med ingenting annat än hashfunktioner.

---

10. Hur webbläsaren verifierar

Att verifiera innebär hos SLH-DSA: att hasha om.

1. Räkna ut digesten på nytt ur $R$, den offentliga nyckeln och meddelandet.
2. Ur de 35 avslöjade FORS-löven och deras vägar räkna ut de 35 trädrötterna och ur dem den offentliga FORS-nyckeln.
3. Med var och en av de 17 WOTS+-signaturerna hasha kedjorna till slutet, bilda den offentliga WOTS+-nyckeln och hasha uppför vägen till trädroten.
4. I slutet måste exakt $\text{PK.root}$ komma ut.

Det är några tusen hashanrop — för en dator en bagatell. I webbläsaren tar verifieringen hos oss omkring 6 till 12 millisekunder.

---

11. Vad händer om någon ändrar dataposten?

Ändras ens en enda bit i meddelandet $M$, ändras digesten fullständigt. Därmed pekar de 35 talen på andra FORS-löv och metoden på en annan plats i hyperträdet.

De avslöjade hemligheterna passar inte längre: de omräknade rötterna avviker, och i slutet kommer inte $\text{PK.root}$ ut. Verifieringen misslyckas.

För att ändå bygga en giltig signatur skulle en angripare behöva känna till hemligheter som aldrig har publicerats — alltså räkna en hashfunktion baklänges.

---

12. Varför just 256f?

FIPS 205 definierar tolv parameteruppsättningar: två hashfamiljer (SHA-2 och SHAKE), tre säkerhetsnivåer (128, 192, 256) och för varje en snabb (”f”) och en liten (”s”) variant.

256 betyder NIST-säkerhetskategori 5 — samma nivå som FALCON-1024 och ML-DSA-87.

”f” valde vi eftersom företag kan utfärda upp till 500 QR-koder i ett svep. Med ”s” skulle signeringen ta över 20 minuter, med ”f” under en minut. I gengäld är signaturen större — eftersom den inte sitter i QR-koden går det att leva med.

SHA-2 i stället för SHAKE, eftersom SHA-256 och SHA-512 är hårdvaruaccelererade på praktiskt taget varje enhet.

---

13. Slump vid signering

FIPS 205 tillåter två sätt att generera $R$:

• deterministiskt: samma meddelande, samma signatur
• randomiserat (”hedged”): ett nytt slumptal vävs in

Vi använder den randomiserade varianten. Två signaturer över samma meddelande ser därför olika ut — båda är giltiga. Det försvårar attacker som kombinerar mätningar på enheten (strömförbrukning, tid) med upprepade signaturer.

---

14. Vad McGesund konkret gör med detta

Nivån. PQ-Dual-Diversified finns i Omdömen Premium och Signaler Premium. En QR-kod bär då tre signaturer:

Signeringen. En SLH-DSA-signatur kostar omkring en kvarts sekund beräkningstid. För att servern under tiden ska förbli tillgänglig för alla andra räknar egna bakgrundstrådar.

Verifieringen. Läsarens webbläsare laddar båda stämplarna och kontrollerar dem med samma WASM-modul som alla andra PQ-signaturer. Vi levererar data, beräkningen sker på besökarens enhet.

Avstämningen mot NIST. Vår modul klarar NIST:s officiella testvektorer för SLH-DSA-SHA2-256f: ur NIST:s seeds uppstår byte för byte samma nycklar, och alla avsiktligt manipulerade signaturer avvisas. Det kan du själv kontrollera i webbläsaren på NIST-testsidan.

Tidsankaret. Som för alla nycklar förankras SLH-DSA-nyckelns fingeravtryck via OpenTimestamps i ett Bitcoin-block.

---

15. SLH-DSA, ML-DSA och FALCON sida vid sida

Kort sagt: SLH-DSA är den långsammaste och största av de tre metoderna — och den mest konservativa. Den bygger inte på något som inte varje annan signatur ändå redan förutsätter: en säker hashfunktion.

---

16. En mening att ta med sig

Den som äger den hemliga seeden signerar på en kvarts sekund. Den som inte äger den skulle behöva räkna SHA-256 eller SHA-512 baklänges — även med en kvantdator.

För läsaren av ett omdöme betyder det: även om alla gittermetoder en dag skulle falla förblir denna signatur verifierbar. Han behöver inte tro oss. Han kan räkna efter.