SLH-DSA matematički objašnjen

1. O čemu je riječ

Na McGesundu korisnici u tarifama Recenzije Premium i Signali Premium mogu odabrati razinu potpisa PQ-Dual-Diversified. Tada svaki QR kod uz klasični Ed25519 potpis nosi i dva kvantno otporna potpisa: ML-DSA-87 i SLH-DSA-SHA2-256f.

Ovaj članak objašnjava drugi od njih. Građen je drukčije od svega ostaloga što koristimo.

SLH-DSA nije šifriranje. Sadržaj ostaje javno čitljiv. SLH-DSA dokazuje podrijetlo i cjelovitost — kao i svaki digitalni potpis.

SLH-DSA u punom obliku glasi Stateless Hash-Based Digital Signature Algorithm. Razvijen je iz SPHINCS+ i standardiziran 2024. kao FIPS 205. Već naziv otkriva što je posebno: postupak koristi samo hash-funkcije. Nema rešetki, nema eliptičkih krivulja, nema velikih prostih brojeva.

---

2. Što se točno potpisuje?

Na McGesundu SLH-DSA potpisuje isti skup podataka koji pokriva i Ed25519 potpis u QR kodu: payload QR koda. On među ostalim sadrži kojem poduzeću kod pripada (fid), koje je vrste (typ), kada je izdan (iat) i do kada vrijedi (exp) — kao kompaktno kodiran niz bajtova (CBOR).

Taj niz bajtova naša je poruka $M$. Promijeni li netko naknadno jedan jedini bit, nijedan potpis više ne odgovara.

SLH-DSA potpis nije u samom QR kodu. S oko 49 KB za to je daleko prevelik. Nalazi se kao zaseban „pečat" uz zapis QR koda u McGesundovu backendu i učitava se u preglednik kada kliknete „Provjeri autentičnost".

---

3. Zašto postupak samo od hash-funkcija?

Svaki postupak potpisivanja počiva na zadatku koji je bez tajnog ključa praktički nerješiv:

Ed25519 bi slomilo veliko kvantno računalo. FALCON i ML-DSA smatraju se kvantno otpornima — ali oba se oslanjaju na probleme rešetki. Kad bi se jednoga dana pronašao temeljni napad na rešetke, oba bi bila pogođena istodobno.

SLH-DSA, naprotiv, treba samo to da hash-funkcija radi ono za što je izgrađena:

To je najdulje i najtemeljitije istražena pretpostavka cijele kriptografije. Ni kvantno računalo ovdje ne pomaže mnogo: Groverov algoritam prepolovljuje sigurnosne bitove. Zato varijanta 256 koristi hash-vrijednosti od $n = 32$ bajta $= 256$ bitova — nakon Grovera i dalje ostaje 128 bitova.

Upravo se zato razina zove Diversified: ML-DSA (rešetke) i SLH-DSA (hash) potječu iz različitih matematičkih obitelji. Padne li jedna, druga nosi.

---

4. Građevni blok 1: potpisivanje hash-lancima (WOTS+)

Osnovna je ideja iznenađujuće jednostavna. Počinjemo s jednom jedinom znamenkom.

Uzmite tajnu slučajnu vrijednost $s$ i hashirajte je iznova i iznova:

Kraj lanca, $p$, objavljuje se. To je javni ključ za tu jednu znamenku.

Da bi se potpisala znamenka $d$ između 0 i 15, otkriva se vrijednost lanca na poziciji $d$:

Tko želi provjeriti, hashira $\sigma$ još $15 - d$ puta. Ako izađe točno $p$, potpis je pravi:

Mali primjer

Potpisujemo znamenku $d = 6$:

• Potpisnik objavljuje $\sigma = H^6(s)$.
• Provjeritelj računa $H^{9}(\sigma) = H^{15}(s)$ i uspoređuje s $p$. Odgovara.

Krivotvoritelj koji je vidio $\sigma$ može iz nje bez muke izračunati $H^7(s)$, $H^8(s)$ itd. — dakle potpisati veće znamenke. Manje ne može, za to bi morao hashirati unatrag.

Kontrolni zbroj protiv „brojanja prema gore"

Da nitko ne bi mogao naprosto povećavati znamenke, dodatno se potpisuje kontrolni zbroj:

Poveća li krivotvoritelj neku znamenku poruke, $C$ postaje manji — a za to bi morao računati unatrag u lancu kontrolnog zbroja. Time su oba smjera zatvorena.

Preračunato na cijelu hash-vrijednost

Hash-vrijednost od 32 bajta ima 64 znamenke u bazi 16. Tome se dodaju 3 znamenke kontrolnog zbroja:

Takav se potpis zove WOTS+ (Winternitz One-Time Signature). Njegova velika kvaka krije se u nazivu: One-Time. Tko istim ključem potpiše dvije različite poruke, otkriva toliko vrijednosti lanaca da krivotvorine postaju moguće.

---

5. Građevni blok 2: mnogo jednokratnih ključeva pod jednim krovom (Merkleovo stablo)

Ako se svaki ključ smije upotrijebiti samo jednom, potrebno ih je jako mnogo — ali objaviti se želi samo jedan javni ključ.

Rješenje je Merkleovo stablo: javni ključevi $2^{h'}$ WOTS+ parova čine listove. Po dva susjeda hashiraju se zajedno, rezultati opet u parovima, sve dok na vrhu ne ostane jedan jedini korijen.

Kod SLH-DSA-SHA2-256f svako stablo ima visinu $h' = 4$, dakle $2^4 = 16$ listova.

Da bi se pokazalo da određeni list pripada stablu, isporučuje se autentikacijski put: 4 sestrinska čvora na putu prema gore. S njima provjeritelj hashira od lista do korijena. Ako izađe poznati korijen, list pripada stablu.

---

6. Građevni blok 3: stabla na stablima (hiperstablo)

16 jednokratnih ključeva naravno nije dovoljno. Zato SLH-DSA slaže stabla jedno na drugo: korijen jednog stabla potpisuje se WOTS+ ključem stabla iznad njega. Taj se toranj zove hiperstablo.

Kod SLH-DSA-SHA2-256f postoji $d = 17$ slojeva, svaki visine 4:

Sasvim dolje time je na raspolaganju

listova. Korijen najvišeg stabla zove se $\text{PK.root}$ — on je pravi javni ključ.

Važno: nitko ta stabla ne izračunava unaprijed. Sve se tajne vrijednosti po potrebi izvode iz tajne početne vrijednosti $\text{SK.seed}$. Pohranjuju se samo četiri vrijednosti od po 32 bajta:

Privatni ključ sastoji se od sve četiri (128 bajtova), javni samo od PK.seed i PK.root (64 bajta).

---

7. Građevni blok 4: šuma protiv slučajnih pogodaka (FORS)

Sada pravi problem: kako potpisnik zna koji je od $2^{68}$ listova još neiskorišten?

Stariji postupci temeljeni na hashu (XMSS, LMS) za to vode brojač. On se nikada ne smije vratiti unatrag — ni sigurnosnom kopijom, ni drugim poslužiteljem. Dogodi li se to ipak, jednokratni se ključ upotrijebi dvaput i postupak je slomljen. Takvi se postupci nazivaju postupcima sa stanjem.

SLH-DSA je bez stanja: list se bira pseudoslučajno iz same poruke. Tada se može dogoditi da dvije poruke pogode isti list. Zato sasvim dolje ne visi jednokratni potpis, nego potpis za nekoliko uporaba: FORS (Forest of Random Subsets).

FORS se sastoji od $k = 35$ malih Merkleovih stabala s po $2^a = 2^9 = 512$ listova. Listovi su tajne slučajne vrijednosti.

Za potpisivanje se hash poruke rastavlja na 35 brojeva od po 9 bitova. Svaki broj u „svojem" stablu bira točno jedan list. Potpis za svako stablo sadrži:

• tajnu vrijednost tog lista
• njegov autentikacijski put (9 čvorova)

Krivotvoritelj bi za drugu poruku morao u svih 35 stabala pogoditi listove čije su tajne već otkrivene. Čak i ako je ista FORS instanca upotrijebljena nekoliko puta, to je beznadno.

---

8. Cijeli tijek potpisivanja

1. Slučajna komponenta. Iz $\text{SK.prf}$, svježeg slučajnog broja i poruke nastaje vrijednost $R$ od 32 bajta.
2. Hash poruke.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 bajtova digesta dijeli se: 40 bajtova bira 35 FORS listova, ostatak određuje koje stablo (idx_tree) i koji list (idx_leaf) sasvim dolje u hiperstablu se koristi.
3. FORS potpis nad porukom. Iz njega proizlazi FORS javni ključ.
4. Potpis hiperstabla nad tim FORS ključem: 17 WOTS+ potpisa, svaki s autentikacijskim putem, sloj po sloj sve do $\text{PK.root}$.

Gotov potpis jednostavno je njihovo nadovezivanje:

---

9. Zašto je potpis velik 49.856 bajtova

S parametrima SLH-DSA-SHA2-256f veličina se može točno izračunati ($n = 32$ bajta po hash-vrijednosti):

Za usporedbu: Ed25519 potpis ima 64 bajta, ML-DSA-87 ima 4.627 bajtova. Veličina je cijena toga što SLH-DSA izlazi na kraj samo s hash-funkcijama.

---

10. Kako preglednik provjerava

Provjera kod SLH-DSA znači: ponovno hashiranje.

1. Ponovno izračunati digest iz $R$, javnog ključa i poruke.
2. Iz 35 otkrivenih FORS listova i njihovih putova izračunati 35 korijena stabala, a iz njih FORS javni ključ.
3. Sa svakim od 17 WOTS+ potpisa hashirati lance do kraja, oblikovati WOTS+ javni ključ i preko puta hashirati prema gore do korijena stabla.
4. Na kraju mora izaći točno $\text{PK.root}$.

To je nekoliko tisuća hash-poziva — za računalo sitnica. U pregledniku provjera kod nas traje oko 6 do 12 milisekundi.

---

11. Što se događa ako netko promijeni skup podataka?

Promijeni li se samo jedan bit poruke $M$, digest se potpuno mijenja. Time 35 brojeva pokazuje na druge FORS listove, a postupak na drugo mjesto u hiperstablu.

Otkrivene tajne više ne odgovaraju: ponovno izračunati korijeni odstupaju i na kraju ne izlazi $\text{PK.root}$. Provjera ne uspijeva.

Da bi ipak sagradio valjan potpis, napadač bi morao poznavati tajne koje nikada nisu objavljene — dakle računati hash-funkciju unatrag.

---

12. Zašto baš 256f?

FIPS 205 definira dvanaest skupova parametara: dvije hash-obitelji (SHA-2 i SHAKE), tri sigurnosne razine (128, 192, 256) i za svaku po jednu brzu („f") i jednu malu („s") varijantu.

256 znači NIST sigurnosnu kategoriju 5 — istu razinu kao FALCON-1024 i ML-DSA-87.

„f" smo odabrali jer poduzeća mogu izdati do 500 QR kodova odjednom. S „s" bi potpisivanje trajalo više od 20 minuta, s „f" manje od minute. Zauzvrat je potpis veći — budući da nije u QR kodu, to je podnošljivo.

SHA-2 umjesto SHAKE jer su SHA-256 i SHA-512 ubrzani na praktički svakom hardveru.

---

13. Slučajnost pri potpisivanju

FIPS 205 dopušta dva načina stvaranja $R$:

• deterministički: ista poruka, isti potpis
• randomizirano („hedged"): uključuje se svjež slučajan broj

Mi koristimo randomiziranu varijantu. Dva potpisa nad istom porukom zato izgledaju različito — oba su valjana. To otežava napade koji mjerenja na uređaju (potrošnja struje, vrijeme) kombiniraju s ponovljenim potpisima.

---

14. Što McGesund konkretno radi s time

Razina. PQ-Dual-Diversified dostupna je u tarifama Recenzije Premium i Signali Premium. QR kod tada nosi tri potpisa:

Potpisivanje. Jedan SLH-DSA potpis stoji oko četvrtine sekunde računalnog vremena. Da bi poslužitelj u međuvremenu ostao dostupan svima ostalima, računaju zasebne pozadinske niti.

Provjera. Preglednik čitatelja učitava oba pečata i provjerava ih istim WASM modulom kao i sve ostale PQ potpise. Mi isporučujemo podatke, računa se na uređaju posjetitelja.

Usklađenost s NIST-om. Naš modul prolazi službene NIST testne vektore za SLH-DSA-SHA2-256f: iz NIST-ovih početnih vrijednosti nastaju bajt po bajt isti ključevi, a svi namjerno manipulirani potpisi bivaju odbijeni. To možete sami provjeriti u pregledniku na NIST testnoj stranici.

Vremensko sidro. Kao i kod svih ključeva, otisak SLH-DSA ključa sidri se preko OpenTimestampsa u jednom Bitcoin bloku.

---

15. SLH-DSA, ML-DSA i FALCON jedan uz drugoga

Ukratko: SLH-DSA je najsporiji i najveći od tri postupka — i najkonzervativniji. Ne oslanja se ni na što što svaki drugi potpis ionako već ne pretpostavlja: sigurnu hash-funkciju.

---

16. Jedna rečenica za kraj

Tko posjeduje tajnu početnu vrijednost, potpisuje za četvrtinu sekunde. Tko je ne posjeduje, morao bi SHA-256 ili SHA-512 računati unatrag — pa i s kvantnim računalom.

Za čitatelja recenzije to znači: čak i ako jednoga dana padnu svi postupci temeljeni na rešetkama, ovaj potpis ostaje provjerljiv. Ne mora nam vjerovati. Može preračunati.