SLH-DSA vysvetlený matematicky

1. O čo tu ide

V McGesund si zákazníci v tarifoch Hodnotenia Premium a Signály Premium môžu zvoliť stupeň podpisu PQ-Dual-Diversified. Každý QR kód potom popri klasickom podpise Ed25519 nesie dva kvantovo odolné podpisy: ML-DSA-87 a SLH-DSA-SHA2-256f.

Tento článok vysvetľuje ten druhý. Je postavený inak než všetko ostatné, čo používame.

SLH-DSA nie je šifrovanie. Obsah zostáva verejne čitateľný. SLH-DSA dokazuje pôvod a neporušenosť — ako každý digitálny podpis.

SLH-DSA znamená v plnom znení Stateless Hash-Based Digital Signature Algorithm. Vzniklo zo SPHINCS+ a v roku 2024 bolo štandardizované ako FIPS 205. Už názov prezrádza, čo je na ňom zvláštne: schéma používa iba hašové funkcie. Žiadne mriežky, žiadne eliptické krivky, žiadne veľké prvočísla.

---

2. Čo presne sa podpisuje?

SLH-DSA v McGesund podpisuje tú istú množinu údajov, ktorú pokrýva aj podpis Ed25519 v QR kóde: payload QR kódu. Obsahuje okrem iného, ku ktorej firme kód patrí (fid), akého je druhu (typ), kedy bol vydaný (iat) a dokedy platí (exp) — ako kompaktne zakódovanú postupnosť bajtov (CBOR).

Táto postupnosť bajtov je naša správa $M$. Ak niekto dodatočne zmení jediný bit, nesedí už žiadny z podpisov.

Podpis SLH-DSA nie je uložený priamo v QR kóde. S približne 49 KB je na to príliš veľký. Leží ako samostatná „pečiatka" pri zázname QR v backende McGesund a pri kliknutí na „Overiť autenticitu" sa načíta do prehliadača.

---

3. Prečo schéma len z hašových funkcií?

Každá podpisová schéma stojí na úlohe, ktorá je bez tajného kľúča prakticky neriešiteľná:

Ed25519 by veľký kvantový počítač prelomil. FALCON a ML-DSA sa považujú za kvantovo odolné — obe sa však opierajú o mriežkové problémy. Ak by sa jedného dňa našiel zásadný útok na mriežky, zasiahol by obe naraz.

SLH-DSA naproti tomu potrebuje len to, aby hašová funkcia robila to, na čo bola vytvorená:

Je to najdlhšie a najdôkladnejšie skúmaný predpoklad celej kryptografie. Ani kvantový počítač tu nepomôže viac než obmedzene: Groverov algoritmus znižuje počet bitov bezpečnosti na polovicu. Preto variant 256 používa hašové hodnoty s $n = 32$ bajtov $= 256$ bitov — po Groverovi stále zostáva 128 bitov.

Práve preto sa stupeň volá Diversified: ML-DSA (mriežky) a SLH-DSA (haš) pochádzajú z rôznych matematických rodín. Ak padne jedna, druhá nesie ďalej.

---

4. Stavebný kameň 1: podpisovanie hašovými reťazcami (WOTS+)

Základná myšlienka je prekvapivo jednoduchá. Začneme jedinou číslicou.

Vezmite tajnú náhodnú hodnotu $s$ a hašujte ju znova a znova:

Koniec reťazca, $p$, sa zverejní. To je verejný kľúč pre túto jednu číslicu.

Na podpísanie číslice $d$ medzi 0 a 15 sa vydá hodnota reťazca na pozícii $d$:

Kto chce overovať, hašuje $\sigma$ ešte $15 - d$-krát. Ak vyjde presne $p$, podpis je pravý:

Mini-príklad

Podpisujeme číslicu $d = 6$:

• Podpisujúci zverejní $\sigma = H^6(s)$.
• Overovateľ vypočíta $H^{9}(\sigma) = H^{15}(s)$ a porovná s $p$. Sedí.

Falšovateľ, ktorý videl $\sigma$, z nej dokáže bez námahy vypočítať $H^7(s)$, $H^8(s)$ atď. — teda podpísať väčšie číslice. Menšie nedokáže, na to by musel hašovať spätne.

Kontrolný súčet proti „navyšovaniu"

Aby nikto nemohol číslice jednoducho zvyšovať, podpisuje sa navyše kontrolný súčet:

Ak falšovateľ zvýši niektorú číslicu správy, $C$ sa zmenší — a na to by musel v reťazci kontrolného súčtu počítať spätne. Oba smery sú tým zablokované.

Prepočítané na hašovú hodnotu

Hašová hodnota s 32 bajtmi má 64 číslic v základe 16. K tomu pribudnú 3 číslice kontrolného súčtu:

Takýto podpis sa nazýva WOTS+ (Winternitz One-Time Signature). Jeho veľký háčik je v názve: One-Time, teda jednorazový. Kto tým istým kľúčom podpíše dve rôzne správy, prezradí toľko hodnôt reťazcov, že falšovanie je možné.

---

5. Stavebný kameň 2: veľa jednorazových kľúčov pod jednou strechou (Merkleov strom)

Ak sa každý kľúč smie použiť len raz, treba ich veľmi veľa — no zverejniť chceme iba jeden verejný kľúč.

Riešením je Merkleov strom: verejné kľúče $2^{h'}$ párov WOTS+ tvoria listy. Vždy dvaja susedia sa zahašujú spolu, výsledky opäť po dvojiciach, až kým navrchu nezostane jediný koreň.

V SLH-DSA-SHA2-256f má každý strom výšku $h' = 4$, teda $2^4 = 16$ listov.

Aby sa ukázalo, že určitý list patrí do stromu, dodá sa autentifikačná cesta: 4 súrodenecké uzly na ceste nahor. Overovateľ sa s nimi prehašuje od listu až ku koreňu. Ak vyjde známy koreň, list do stromu patrí.

---

6. Stavebný kameň 3: stromy na stromoch (hyperstrom)

16 jednorazových kľúčov, samozrejme, nestačí. Preto SLH-DSA kladie stromy na seba: koreň stromu sa podpíše kľúčom WOTS+ stromu nad ním. Táto veža sa nazýva hyperstrom.

V SLH-DSA-SHA2-256f je $d = 17$ vrstiev, každá s výškou 4:

Úplne dole je tak k dispozícii

listov. Koreň najvyššieho stromu sa nazýva $\text{PK.root}$ — je to vlastný verejný kľúč.

Dôležité: nikto tieto stromy nepočíta vopred. Všetky tajné hodnoty sa podľa potreby odvodzujú z tajného seedu $\text{SK.seed}$. Ukladajú sa len štyri hodnoty po 32 bajtov:

Súkromný kľúč pozostáva zo všetkých štyroch (128 bajtov), verejný len z PK.seed a PK.root (64 bajtov).

---

7. Stavebný kameň 4: les proti náhodným zásahom (FORS)

Teraz vlastný problém: ako podpisujúci vie, ktorý z $2^{68}$ listov je ešte nepoužitý?

Staršie schémy založené na haši (XMSS, LMS) si na to vedú počítadlo. To sa nikdy nesmie vrátiť späť — ani zálohou, ani druhým serverom. Ak sa to predsa stane, jednorazový kľúč sa použije dvakrát a schéma je prelomená. Takéto schémy sa nazývajú stavové.

SLH-DSA je bezstavové: list sa vyberá pseudonáhodne zo samotnej správy. Potom sa môže stať, že dve správy trafia ten istý list. Preto úplne dole nevisí jednorazový podpis, ale podpis na niekoľko použití: FORS (Forest of Random Subsets).

FORS pozostáva z $k = 35$ malých Merkleových stromov, každý s $2^a = 2^9 = 512$ listami. Listy sú tajné náhodné hodnoty.

Pri podpisovaní sa haš správy rozloží na 35 čísel po 9 bitov. Každé číslo vyberie vo „svojom" strome presne jeden list. Podpis obsahuje pre každý strom:

• tajnú hodnotu tohto listu
• jeho autentifikačnú cestu (9 uzlov)

Falšovateľ by pre inú správu musel vo všetkých 35 stromoch trafiť listy, ktorých tajomstvá už boli prezradené. Aj keby bola tá istá inštancia FORS použitá niekoľkokrát, je to beznádejné.

---

8. Celý priebeh podpisovania

1. Náhodná zložka. Z $\text{SK.prf}$, čerstvého náhodného čísla a správy vznikne 32-bajtová hodnota $R$.
2. Haš správy.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 bajtov digestu sa rozdelí: 40 bajtov vyberá 35 listov FORS, zvyšok určuje, ktorý strom (idx_tree) a ktorý list (idx_leaf) úplne dole v hyperstrome sa použije.
3. Podpis FORS nad správou. Z neho vyplynie verejný kľúč FORS.
4. Podpis hyperstromu nad týmto kľúčom FORS: 17 podpisov WOTS+, každý s autentifikačnou cestou, vrstvu za vrstvou až hore k $\text{PK.root}$.

Hotový podpis je jednoducho zreťazenie:

---

9. Prečo má podpis 49 856 bajtov

S parametrami SLH-DSA-SHA2-256f sa dá veľkosť presne prepočítať ($n = 32$ bajtov na hašovú hodnotu):

Pre porovnanie: podpis Ed25519 má 64 bajtov, ML-DSA-87 má 4 627 bajtov. Veľkosť je cenou za to, že si SLH-DSA vystačí s ničím iným než hašovými funkciami.

---

10. Ako overuje prehliadač

Overovanie pri SLH-DSA znamená: znova hašovať.

1. Nanovo vypočítať digest z $R$, verejného kľúča a správy.
2. Z 35 odkrytých listov FORS a ich ciest vypočítať 35 koreňov stromov a z nich verejný kľúč FORS.
3. S každým zo 17 podpisov WOTS+ dohašovať reťazce do konca, vytvoriť verejný kľúč WOTS+ a po ceste sa prehašovať ku koreňu stromu.
4. Na konci musí vyjsť presne $\text{PK.root}$.

To je niekoľko tisíc volaní hašovej funkcie — pre počítač maličkosť. V prehliadači trvá overenie u nás približne 6 až 12 milisekúnd.

---

11. Čo sa stane, keď niekto zmení údaje?

Ak sa zmení čo i len jeden bit správy $M$, digest sa zmení úplne. Tým 35 čísel ukazuje na iné listy FORS a schéma na iné miesto v hyperstrome.

Odkryté tajomstvá už nesedia: prepočítané korene sa odlišujú a na konci nevyjde $\text{PK.root}$. Overenie zlyhá.

Aby útočník napriek tomu zostavil platný podpis, musel by poznať tajomstvá, ktoré nikdy neboli zverejnené — teda počítať hašovú funkciu spätne.

---

12. Prečo práve 256f?

FIPS 205 definuje dvanásť sád parametrov: dve hašové rodiny (SHA-2 a SHAKE), tri úrovne bezpečnosti (128, 192, 256) a pre každú rýchly („f") a malý („s") variant.

256 znamená bezpečnostnú kategóriu NIST 5 — rovnaký stupeň ako FALCON-1024 a ML-DSA-87.

„f" sme zvolili, pretože firmy môžu vydať až 500 QR kódov naraz. S „s" by podpisovanie trvalo viac ako 20 minút, s „f" menej ako minútu. Podpis je za to väčší — keďže nie je v QR kóde, dá sa to zniesť.

SHA-2 namiesto SHAKE, pretože SHA-256 a SHA-512 sú hardvérovo akcelerované prakticky na každom zariadení.

---

13. Náhoda pri podpisovaní

FIPS 205 pripúšťa dva spôsoby, ako vytvoriť $R$:

• deterministicky: rovnaká správa, rovnaký podpis
• randomizovane („hedged"): pridá sa čerstvé náhodné číslo

Používame randomizovaný variant. Dva podpisy nad tou istou správou preto vyzerajú rozdielne — oba sú platné. To sťažuje útoky, ktoré kombinujú merania na zariadení (spotreba prúdu, čas) s opakovanými podpismi.

---

14. Čo s tým McGesund konkrétne robí

Stupeň. PQ-Dual-Diversified je k dispozícii v tarifoch Hodnotenia Premium a Signály Premium. QR kód potom nesie tri podpisy:

Podpisovanie. Podpis SLH-DSA stojí približne štvrť sekundy výpočtového času. Aby server zostal medzitým dostupný pre všetkých ostatných, počítajú vlastné vlákna na pozadí.

Overenie. Prehliadač čitateľa načíta obe pečiatky a overí ich tým istým modulom WASM ako všetky ostatné PQ podpisy. My dodávame údaje, počíta sa na zariadení návštevníka.

Zhoda s NIST. Náš modul prechádza oficiálnymi testovacími vektormi NIST pre SLH-DSA-SHA2-256f: z počiatočných hodnôt NIST vznikajú bajt po bajte tie isté kľúče a všetky úmyselne zmanipulované podpisy sú odmietnuté. Môžete si to sami overiť v prehliadači na testovacej stránke NIST.

Časová kotva. Ako pri všetkých kľúčoch, aj odtlačok kľúča SLH-DSA sa cez OpenTimestamps ukotví v bloku Bitcoinu.

---

15. SLH-DSA, ML-DSA a FALCON vedľa seba

Stručne povedané: SLH-DSA je najpomalšie a najväčšie z troch schém — a najkonzervatívnejšie. Nestavia na ničom, čo by už aj tak nepredpokladal každý iný podpis: na bezpečnej hašovej funkcii.

---

16. Jedna veta na záver

Kto vlastní tajný seed, podpíše za štvrť sekundy. Kto ho nevlastní, musel by SHA-256 alebo SHA-512 počítať spätne — aj s kvantovým počítačom.

Pre čitateľa hodnotenia to znamená: aj keby jedného dňa padli všetky mriežkové schémy, tento podpis zostane overiteľný. Nemusí nám veriť. Môže si to prepočítať.