SLH-DSA vysvětlený matematicky

1. O co tu jde

Na McGesund si zákazníci v tarifech Hodnocení Premium a Signály Premium mohou zvolit stupeň podpisu PQ-Dual-Diversified. Každý QR kód pak vedle klasického podpisu Ed25519 nese dva kvantově odolné podpisy: ML-DSA-87 a SLH-DSA-SHA2-256f.

Tento článek vysvětluje ten druhý. Je postavený jinak než všechno ostatní, co používáme.

SLH-DSA není šifrování. Obsah zůstává veřejně čitelný. SLH-DSA dokazuje původ a neporušenost — jako každý digitální podpis.

SLH-DSA znamená v plném znění Stateless Hash-Based Digital Signature Algorithm. Vzniklo ze SPHINCS+ a v roce 2024 bylo standardizováno jako FIPS 205. Už název prozrazuje, v čem je zvláštní: schéma používá pouze hashovací funkce. Žádné mřížky, žádné eliptické křivky, žádná velká prvočísla.

---

2. Co přesně se podepisuje?

SLH-DSA na McGesund podepisuje tentýž datový záznam, který pokrývá i podpis Ed25519 v QR kódu: payload QR kódu. Obsahuje mimo jiné, ke které firmě kód patří (fid), jakého je druhu (typ), kdy byl vystaven (iat) a do kdy platí (exp) — jako kompaktně zakódovanou posloupnost bajtů (CBOR).

Tato posloupnost bajtů je naše zpráva $M$. Změní-li někdo dodatečně jediný bit, nesedí už žádný z podpisů.

Podpis SLH-DSA není uložen v samotném QR kódu. S přibližně 49 KB je na to příliš velký. Leží jako samostatné „razítko“ u záznamu QR v backendu McGesund a po kliknutí na „Ověřit pravost“ se načte do prohlížeče.

---

3. Proč schéma postavené jen na hashovacích funkcích?

Každé podpisové schéma stojí na úloze, která je bez tajného klíče prakticky neřešitelná:

Ed25519 by velký kvantový počítač prolomil. FALCON a ML-DSA platí za kvantově odolné — obě se však opírají o mřížkové problémy. Kdyby se jednoho dne našel zásadní útok na mřížky, byly by zasaženy obě zároveň.

SLH-DSA naproti tomu potřebuje jen to, aby hashovací funkce dělala to, k čemu je postavená:

To je nejdéle a nejdůkladněji zkoumaný předpoklad celé kryptografie. Ani kvantový počítač tu nepomůže víc než omezeně: Groverův algoritmus zmenšuje bezpečnostní bity na polovinu. Proto varianta 256 používá hashe o délce $n = 32$ bajtů $= 256$ bitů — po Groverovi stále zbývá 128 bitů.

Právě proto se stupeň jmenuje Diversified: ML-DSA (mřížky) a SLH-DSA (hash) pocházejí z různých matematických rodin. Padne-li jedna, nese druhá.

---

4. Stavební kámen 1: podepisování hashovacími řetězci (WOTS+)

Základní myšlenka je překvapivě jednoduchá. Začneme jedinou číslicí.

Vezměte tajnou náhodnou hodnotu $s$ a hashujte ji znovu a znovu:

Konec řetězce, $p$, se zveřejní. To je veřejný klíč pro tuto jedinou číslici.

K podepsání číslice $d$ mezi 0 a 15 se vydá hodnota řetězce na pozici $d$:

Kdo chce ověřovat, hashuje $\sigma$ ještě $15 - d$krát dál. Vyjde-li přesně $p$, je podpis pravý:

Malý příklad

Podepíšeme číslici $d = 6$:

• Podepisující zveřejní $\sigma = H^6(s)$.
• Ověřovatel spočítá $H^{9}(\sigma) = H^{15}(s)$ a porovná s $p$. Sedí.

Padělatel, který $\sigma$ viděl, z ní snadno spočítá $H^7(s)$, $H^8(s)$ atd. — tedy podepíše větší číslice. Menší nedokáže, k tomu by musel hashovat pozpátku.

Kontrolní součet proti „přičítání“

Aby nikdo nemohl číslice jednoduše zvýšit, podepisuje se navíc kontrolní součet:

Zvýší-li padělatel některou číslici zprávy, $C$ se zmenší — a k tomu by musel v řetězci kontrolního součtu počítat pozpátku. Oba směry jsou tím zablokované.

Přepočteno na celý hash

Hash o 32 bajtech má 64 číslic v soustavě o základu 16. K tomu přibudou 3 číslice kontrolního součtu:

Takový podpis se nazývá WOTS+ (Winternitz One-Time Signature). Jeho velký háček je skrytý v názvu: One-Time, tedy jednorázový. Kdo stejným klíčem podepíše dvě různé zprávy, prozradí tolik hodnot řetězců, že se padělky stanou možnými.

---

5. Stavební kámen 2: mnoho jednorázových klíčů pod jednou střechou (Merkleův strom)

Smí-li se každý klíč použít jen jednou, je jich potřeba velmi mnoho — ale zveřejnit chceme jen jeden veřejný klíč.

Řešením je Merkleův strom: veřejné klíče $2^{h'}$ párů WOTS+ tvoří listy. Vždy dva sousedé se zahashují dohromady, výsledky znovu po dvojicích, až nahoře zůstane jediný kořen.

U SLH-DSA-SHA2-256f má každý strom výšku $h' = 4$, tedy $2^4 = 16$ listů.

Aby se ukázalo, že určitý list do stromu patří, dodá se autentizační cesta: 4 sourozenecké uzly na cestě nahoru. Ověřovatel s nimi hashuje od listu až ke kořeni. Vyjde-li známý kořen, list do stromu patří.

---

6. Stavební kámen 3: stromy na stromech (hyperstrom)

16 jednorázových klíčů samozřejmě nestačí. SLH-DSA proto skládá stromy na sebe: kořen jednoho stromu se podepíše klíčem WOTS+ stromu nad ním. Této věži se říká hyperstrom.

U SLH-DSA-SHA2-256f je $d = 17$ vrstev, každá o výšce 4:

Úplně dole je tak k dispozici

listů. Kořen nejvyššího stromu se nazývá $\text{PK.root}$ — to je vlastní veřejný klíč.

Důležité: Nikdo tyto stromy nepočítá předem. Všechny tajné hodnoty se podle potřeby odvozují z tajné výchozí hodnoty $\text{SK.seed}$. Ukládají se jen čtyři hodnoty po 32 bajtech:

Soukromý klíč se skládá ze všech čtyř (128 bajtů), veřejný jen z PK.seed a PK.root (64 bajtů).

---

7. Stavební kámen 4: les proti náhodným zásahům (FORS)

Teď vlastní problém: Jak podepisující ví, který z $2^{68}$ listů je ještě nepoužitý?

Starší schémata založená na hashích (XMSS, LMS) si k tomu vedou čítač. Ten se nesmí nikdy vrátit zpět — ani zálohou, ani druhým serverem. Stane-li se to přesto, použije se jednorázový klíč dvakrát a schéma je prolomené. Takovým schématům se říká stavová.

SLH-DSA je bezstavové: list se volí pseudonáhodně ze samotné zprávy. Pak se může stát, že dvě zprávy trefí tentýž list. Proto úplně dole nevisí jednorázový podpis, nýbrž podpis pro několik použití: FORS (Forest of Random Subsets).

FORS se skládá z $k = 35$ malých Merkleových stromů, každý s $2^a = 2^9 = 512$ listy. Listy jsou tajné náhodné hodnoty.

K podepsání se hash zprávy rozloží na 35 čísel po 9 bitech. Každé číslo vybere ve „svém“ stromu právě jeden list. Podpis obsahuje pro každý strom:

• tajnou hodnotu tohoto listu
• jeho autentizační cestu (9 uzlů)

Padělatel by pro jinou zprávu musel ve všech 35 stromech trefit listy, jejichž tajemství už byla prozrazena. I kdyby byla tatáž instance FORS použita několikrát, je to beznadějné.

---

8. Celý průběh podepisování

1. Náhodná složka. Z $\text{SK.prf}$, čerstvého náhodného čísla a zprávy vznikne 32bajtová hodnota $R$.
2. Hash zprávy.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 bajtů digestu se rozdělí: 40 bajtů vybere 35 listů FORS, zbytek určí, který strom (idx_tree) a který list (idx_leaf) úplně dole v hyperstromu se použije.
3. Podpis FORS nad zprávou. Z něj vyplyne veřejný klíč FORS.
4. Podpis hyperstromu nad tímto klíčem FORS: 17 podpisů WOTS+, každý s autentizační cestou, vrstvu po vrstvě až nahoru k $\text{PK.root}$.

Hotový podpis je prostě zřetězení:

---

9. Proč má podpis 49 856 bajtů

S parametry SLH-DSA-SHA2-256f lze velikost přesně přepočítat ($n = 32$ bajtů na hash):

Pro srovnání: podpis Ed25519 má 64 bajtů, ML-DSA-87 má 4 627 bajtů. Velikost je cenou za to, že si SLH-DSA vystačí s ničím jiným než hashovacími funkcemi.

---

10. Jak ověřuje prohlížeč

Ověřovat znamená u SLH-DSA: přehashovat.

1. Znovu spočítat digest z $R$, veřejného klíče a zprávy.
2. Z 35 odkrytých listů FORS a jejich cest spočítat 35 kořenů stromů a z nich veřejný klíč FORS.
3. S každým ze 17 podpisů WOTS+ dohashovat řetězce do konce, sestavit veřejný klíč WOTS+ a po cestě jej vyhashovat nahoru ke kořeni stromu.
4. Na konci musí vyjít přesně $\text{PK.root}$.

To je několik tisíc volání hashovací funkce — pro počítač maličkost. V prohlížeči trvá ověření u nás zhruba 6 až 12 milisekund.

---

11. Co se stane, když někdo datový záznam změní?

Změní-li se byť jen jeden bit zprávy $M$, změní se digest úplně. Tím ukazuje 35 čísel na jiné listy FORS a schéma na jiné místo v hyperstromu.

Odkrytá tajemství už nesedí: přepočítané kořeny se odchylují a na konci nevyjde $\text{PK.root}$. Ověření selže.

Aby útočník přesto sestavil platný podpis, musel by znát tajemství, která nikdy nebyla zveřejněna — tedy spočítat hashovací funkci pozpátku.

---

12. Proč zrovna 256f?

FIPS 205 definuje dvanáct sad parametrů: dvě rodiny hashovacích funkcí (SHA-2 a SHAKE), tři stupně bezpečnosti (128, 192, 256) a pro každý jednu rychlou („f“) a jednu malou („s“) variantu.

256 znamená bezpečnostní kategorii 5 podle NIST — stejný stupeň jako FALCON-1024 a ML-DSA-87.

„f“ jsme zvolili, protože firmy mohou vystavit až 500 QR kódů najednou. S „s“ by podepisování trvalo přes 20 minut, s „f“ méně než minutu. Podpis je za to větší — protože ale nevězí v QR kódu, dá se to unést.

SHA-2 místo SHAKE, protože SHA-256 a SHA-512 jsou hardwarově akcelerované prakticky na každém zařízení.

---

13. Náhoda při podepisování

FIPS 205 dovoluje dva způsoby, jak vytvořit $R$:

• deterministicky: stejná zpráva, stejný podpis
• randomizovaně („hedged“): přimíchá se čerstvé náhodné číslo

Používáme randomizovanou variantu. Dva podpisy nad stejnou zprávou proto vypadají různě — oba jsou platné. To ztěžuje útoky, které kombinují měření na zařízení (spotřeba proudu, čas) s opakovanými podpisy.

---

14. Co s tím McGesund konkrétně dělá

Stupeň. PQ-Dual-Diversified je k dispozici v tarifech Hodnocení Premium a Signály Premium. QR kód pak nese tři podpisy:

Podepisování. Jeden podpis SLH-DSA stojí zhruba čtvrt sekundy výpočetního času. Aby server mezitím zůstal dostupný pro všechny ostatní, počítají vlastní vlákna na pozadí.

Ověření. Prohlížeč čtenáře načte obě razítka a ověří je stejným modulem WASM jako všechny ostatní PQ podpisy. My dodáváme data; počítá se na zařízení návštěvníka.

Porovnání s NIST. Náš modul prochází oficiálními testovacími vektory NIST pro SLH-DSA-SHA2-256f: z výchozích hodnot NIST vzniknou bajt po bajtu tytéž klíče a všechny úmyslně zmanipulované podpisy jsou odmítnuty. To si můžete sami ověřit v prohlížeči na testovací stránce NIST.

Časová kotva. Jako u všech klíčů je otisk klíče SLH-DSA přes OpenTimestamps zakotven v bloku Bitcoinu.

---

15. SLH-DSA, ML-DSA a FALCON vedle sebe

Krátce řečeno: SLH-DSA je nejpomalejší a největší ze tří schémat — a nejkonzervativnější. Nesází na nic, co by stejně nepředpokládal každý jiný podpis: bezpečnou hashovací funkci.

---

16. Jedna věta na závěr

Kdo tajnou výchozí hodnotu vlastní, podepisuje za čtvrt sekundy. Kdo ji nevlastní, musel by počítat SHA-256 nebo SHA-512 pozpátku — i s kvantovým počítačem.

Pro čtenáře hodnocení to znamená: I kdyby jednoho dne padla všechna mřížková schémata, zůstane tento podpis ověřitelný. Nemusí nám věřit. Může si to přepočítat.