SLH-DSA matematično pojasnjen

1. Za kaj gre

Pri McGesund lahko stranke v paketih Ocene Premium in Signali Premium izberejo stopnjo podpisa PQ-Dual-Diversified. Takrat vsaka koda QR poleg klasičnega podpisa Ed25519 nosi dva kvantno odporna podpisa: ML-DSA-87 in SLH-DSA-SHA2-256f.

Ta prispevek pojasnjuje drugega. Zgrajen je drugače kot vse drugo, kar uporabljamo.

SLH-DSA ni šifriranje. Vsebina ostane javno berljiva. SLH-DSA dokazuje izvor in nespremenjenost — kot vsak digitalni podpis.

SLH-DSA se v celoti glasi Stateless Hash-Based Digital Signature Algorithm. Razvit je bil iz SPHINCS+ in leta 2024 standardiziran kot FIPS 205. Že ime izdaja, kaj je pri njem posebnega: postopek uporablja samo zgoščevalne funkcije. Brez mrež, brez eliptičnih krivulj, brez velikih praštevil.

---

2. Kaj natanko se podpiše?

SLH-DSA pri McGesund podpiše isti nabor podatkov, ki ga pokriva tudi podpis Ed25519 v kodi QR: payload kode QR. Ta med drugim vsebuje, kateremu podjetju koda pripada (fid), katere vrste je (typ), kdaj je bila izdana (iat) in do kdaj velja (exp) — kot kompaktno kodirano zaporedje bajtov (CBOR).

To zaporedje bajtov je naše sporočilo $M$. Če kdo naknadno spremeni en sam bit, se ne ujema noben od podpisov več.

Podpis SLH-DSA ni shranjen v sami kodi QR. S približno 49 KB je za to precej prevelik. Shranjen je kot lasten „žig” ob zapisu QR v zaledju McGesund in se ob kliku na „Preveri pristnost” naloži v brskalnik.

---

3. Zakaj postopek samo iz zgoščevalnih funkcij?

Vsak podpisni postopek temelji na nalogi, ki je brez skrivnega ključa praktično nerešljiva:

Ed25519 bi velik kvantni računalnik zlomil. FALCON in ML-DSA veljata za kvantno odporna — a oba se opirata na mrežne probleme. Če bi nekoč odkrili temeljni napad na mreže, bi bila prizadeta oba hkrati.

SLH-DSA pa potrebuje le, da zgoščevalna funkcija počne to, za kar je bila narejena:

To je najdlje in najtemeljiteje raziskana predpostavka vse kriptografije. Tudi kvantni računalnik tu pomaga le omejeno: Groverjev algoritem razpolovi varnostne bite. Zato različica 256 uporablja zgoščene vrednosti z $n = 32$ bajti $= 256$ bitov — po Groverju jih še vedno ostane 128.

Prav zato se stopnja imenuje Diversified: ML-DSA (mreže) in SLH-DSA (zgoščevanje) izhajata iz različnih matematičnih družin. Če ena pade, druga nosi naprej.

---

4. Gradnik 1: podpisovanje z verigami zgoščevanja (WOTS+)

Osnovna zamisel je presenetljivo preprosta. Začnemo z eno samo števko.

Vzemite skrivno naključno vrednost $s$ in jo znova in znova zgostite:

Konec verige, $p$, se objavi. To je javni ključ za to eno števko.

Za podpis števke $d$ med 0 in 15 se razkrije vrednost verige na položaju $d$:

Kdor želi preveriti, $\sigma$ zgosti še $15 - d$-krat. Če pride ven natanko $p$, je podpis pristen:

Mini primer

Podpišemo števko $d = 6$:

• Podpisnik objavi $\sigma = H^6(s)$.
• Preverjevalec izračuna $H^{9}(\sigma) = H^{15}(s)$ in primerja s $p$. Ujema se.

Ponarejevalec, ki je videl $\sigma$, lahko iz nje brez težav izračuna $H^7(s)$, $H^8(s)$ itd. — torej podpiše večje števke. Manjših ne more, saj bi moral zgoščevati nazaj.

Kontrolna vsota proti „štetju navzgor”

Da nihče ne bi mogel števk preprosto povečati, se dodatno podpiše kontrolna vsota:

Če ponarejevalec poveča števko sporočila, postane $C$ manjša — za to pa bi moral v verigi kontrolne vsote računati nazaj. S tem sta obe smeri zaprti.

Preračunano na zgoščeno vrednost

Zgoščena vrednost z 32 bajti ima 64 števk v osnovi 16. Zraven pridejo še 3 števke kontrolne vsote:

Takšen podpis se imenuje WOTS+ (Winternitz One-Time Signature). Njegova velika slabost tiči v imenu: One-Time, torej enkraten. Kdor z istim ključem podpiše dve različni sporočili, razkrije toliko vrednosti verig, da postanejo ponaredbe mogoče.

---

5. Gradnik 2: veliko enkratnih ključev pod eno streho (Merklovo drevo)

Če se sme vsak ključ uporabiti le enkrat, jih potrebujemo zelo veliko — objaviti pa želimo le en javni ključ.

Rešitev je Merklovo drevo: javni ključi $2^{h'}$ parov WOTS+ tvorijo liste. Po dva soseda se zgostita skupaj, rezultati spet v parih, dokler na vrhu ne ostane en sam koren.

Pri SLH-DSA-SHA2-256f ima vsako drevo višino $h' = 4$, torej $2^4 = 16$ listov.

Da pokažemo, da določen list pripada drevesu, priložimo avtentikacijsko pot: 4 sestrska vozlišča na poti navzgor. Preverjevalec z njimi zgošča od lista vse do korena. Če pride ven znani koren, list pripada drevesu.

---

6. Gradnik 3: drevesa na drevesih (hiperdrevo)

16 enkratnih ključev seveda ni dovolj. Zato SLH-DSA drevesa zlaga drugo na drugo: koren drevesa se podpiše s ključem WOTS+ drevesa nad njim. Ta stolp se imenuje hiperdrevo.

Pri SLH-DSA-SHA2-256f je $d = 17$ plasti, vsaka z višino 4:

Čisto spodaj je tako na voljo

listov. Koren najvišjega drevesa se imenuje $\text{PK.root}$ — to je dejanski javni ključ.

Pomembno: nihče teh dreves ne izračuna vnaprej. Vse skrivne vrednosti se po potrebi izpeljejo iz skrivnega semena $\text{SK.seed}$. Shranijo se le štiri vrednosti po 32 bajtov:

Zasebni ključ sestavljajo vse štiri (128 bajtov), javnega le PK.seed in PK.root (64 bajtov).

---

7. Gradnik 4: gozd proti naključnim zadetkom (FORS)

Zdaj pravi problem: kako podpisnik ve, kateri od $2^{68}$ listov je še neuporabljen?

Starejši postopki na osnovi zgoščevanja (XMSS, LMS) za to vodijo števec. Tega nikoli ne smemo ponastaviti — ne z varnostno kopijo ne z drugim strežnikom. Če se to vseeno zgodi, se enkratni ključ uporabi dvakrat in postopek je zlomljen. Takim postopkom pravimo s stanjem.

SLH-DSA je brez stanja: list se izbere psevdonaključno iz samega sporočila. Potem se lahko zgodi, da dve sporočili zadeneta isti list. Zato čisto spodaj ne visi enkratni podpis, temveč podpis za nekajkratno uporabo: FORS (Forest of Random Subsets).

FORS sestavlja $k = 35$ majhnih Merklovih dreves, vsako z $2^a = 2^9 = 512$ listi. Listi so skrivne naključne vrednosti.

Za podpis se zgoščena vrednost sporočila razdeli na 35 števil po 9 bitov. Vsako število v „svojem” drevesu izbere natanko en list. Podpis za vsako drevo vsebuje:

• skrivno vrednost tega lista
• njegovo avtentikacijsko pot (9 vozlišč)

Ponarejevalec bi moral za drugo sporočilo v vseh 35 drevesih zadeti liste, katerih skrivnosti so že bile razkrite. Tudi če je bila ista instanca FORS uporabljena nekajkrat, je to brezupno.

---

8. Celoten potek podpisovanja

1. Naključna komponenta. Iz $\text{SK.prf}$, svežega naključnega števila in sporočila nastane 32-bajtna vrednost $R$.
2. Zgoščena vrednost sporočila.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 bajtov digesta se razdeli: 40 bajtov izbere 35 listov FORS, preostanek določa, katero drevo (idx_tree) in kateri list (idx_leaf) čisto spodaj v hiperdrevesu se uporabi.
3. Podpis FORS nad sporočilom. Iz njega izhaja javni ključ FORS.
4. Podpis hiperdrevesa nad tem ključem FORS: 17 podpisov WOTS+, vsak z avtentikacijsko potjo, plast za plastjo vse do $\text{PK.root}$.

Končni podpis je preprosto zaporedna združitev:

---

9. Zakaj je podpis velik 49.856 bajtov

S parametri SLH-DSA-SHA2-256f je mogoče velikost natančno preračunati ($n = 32$ bajtov na zgoščeno vrednost):

Za primerjavo: podpis Ed25519 ima 64 bajtov, ML-DSA-87 ima 4.627 bajtov. Velikost je cena za to, da SLH-DSA shaja z ničimer drugim kot zgoščevalnimi funkcijami.

---

10. Kako preverja brskalnik

Preverjanje pri SLH-DSA pomeni: ponovno zgoščevanje.

1. Na novo izračunati digest iz $R$, javnega ključa in sporočila.
2. Iz 35 razkritih listov FORS in njihovih poti izračunati 35 korenov dreves in iz njih javni ključ FORS.
3. Z vsakim od 17 podpisov WOTS+ verige zgostiti do konca, sestaviti javni ključ WOTS+ in po poti zgoščevati navzgor do korena drevesa.
4. Na koncu mora priti ven natanko $\text{PK.root}$.

To je nekaj tisoč klicev zgoščevalne funkcije — za računalnik malenkost. V brskalniku traja preverjanje pri nas približno 6 do 12 milisekund.

---

11. Kaj se zgodi, če kdo spremeni podatke?

Če se spremeni samo en bit sporočila $M$, se digest popolnoma spremeni. S tem 35 števil kaže na druge liste FORS, postopek pa na drugo mesto v hiperdrevesu.

Razkrite skrivnosti se ne ujemajo več: preračunani koreni odstopajo in na koncu ne pride ven $\text{PK.root}$. Preverjanje ne uspe.

Da bi napadalec kljub temu sestavil veljaven podpis, bi moral poznati skrivnosti, ki niso bile nikoli objavljene — torej zgoščevalno funkcijo izračunati nazaj.

---

12. Zakaj prav 256f?

FIPS 205 določa dvanajst naborov parametrov: dve družini zgoščevalnih funkcij (SHA-2 in SHAKE), tri varnostne stopnje (128, 192, 256) in za vsako hitro („f”) in majhno („s”) različico.

256 pomeni varnostno kategorijo NIST 5 — isto stopnjo kot FALCON-1024 in ML-DSA-87.

„f” smo izbrali, ker lahko podjetja naenkrat izdajo do 500 kod QR. S „s” bi podpisovanje trajalo več kot 20 minut, s „f” manj kot minuto. V zameno je podpis večji — ker ni v kodi QR, je to sprejemljivo.

SHA-2 namesto SHAKE, ker sta SHA-256 in SHA-512 praktično na vsaki napravi strojno pospešena.

---

13. Naključnost pri podpisovanju

FIPS 205 dovoljuje dva načina za tvorjenje $R$:

• deterministično: enako sporočilo, enak podpis
• randomizirano („hedged”): zraven se vključi sveže naključno število

Uporabljamo randomizirano različico. Dva podpisa nad istim sporočilom sta zato videti različno — oba sta veljavna. To otežuje napade, ki meritve na napravi (poraba toka, čas) kombinirajo s ponovljenimi podpisi.

---

14. Kaj McGesund konkretno počne s tem

Stopnja. PQ-Dual-Diversified je na voljo v paketih Ocene Premium in Signali Premium. Koda QR takrat nosi tri podpise:

Podpisovanje. Podpis SLH-DSA stane približno četrt sekunde računskega časa. Da strežnik medtem ostane dosegljiv za vse druge, računajo lastne niti v ozadju.

Preverjanje. Brskalnik bralca naloži oba žiga in ju preveri z istim modulom WASM kot vse druge podpise PQ. Mi dostavimo podatke, računa se na napravi obiskovalca.

Uskladitev z NIST. Naš modul prestane uradne testne vektorje NIST za SLH-DSA-SHA2-256f: iz semen NIST nastanejo bajt za bajtom isti ključi, vsi namenoma spremenjeni podpisi pa so zavrnjeni. To lahko sami preverite v brskalniku na testni strani NIST.

Časovno sidro. Kot pri vseh ključih se prstni odtis ključa SLH-DSA prek OpenTimestamps zasidra v blok Bitcoin.

---

15. SLH-DSA, ML-DSA in FALCON drug ob drugem

Na kratko: SLH-DSA je najpočasnejši in največji od treh postopkov — in najbolj konzervativen. Ne stavi na nič, česar ne predpostavlja že tako ali tako vsak drug podpis: varne zgoščevalne funkcije.

---

16. En stavek za s seboj

Kdor ima skrivno seme, podpiše v četrt sekunde. Kdor ga nima, bi moral SHA-256 ali SHA-512 izračunati nazaj — tudi s kvantnim računalnikom.

Za bralca ocene to pomeni: tudi če bi nekoč padli vsi mrežni postopki, ta podpis ostane preverljiv. Ni nam treba verjeti. Lahko preračuna sam.