SLH-DSA paaiškintas matematiškai

1. Apie ką čia kalbama

McGesund klientai, turintys tarifą Atsiliepimai Premium ar Signalai Premium, gali pasirinkti parašo lygį PQ-Dual-Diversified. Tada kiekvienas QR kodas greta klasikinio Ed25519 parašo turi du kvantams atsparius parašus: ML-DSA-87 ir SLH-DSA-SHA2-256f.

Šis straipsnis paaiškina antrąjį. Jis sukurtas kitaip nei visa kita, ką naudojame.

SLH-DSA nėra šifravimas. Turinys lieka viešai skaitomas. SLH-DSA įrodo kilmę ir vientisumą — kaip ir bet kuris skaitmeninis parašas.

SLH-DSA visas pavadinimas — Stateless Hash-Based Digital Signature Algorithm. Jis išvystytas iš SPHINCS+ ir 2024 m. standartizuotas kaip FIPS 205. Pavadinimas jau išduoda ypatumą: algoritmas naudoja tik maišos funkcijas. Jokių gardelių, jokių elipsinių kreivių, jokių didelių pirminių skaičių.

---

2. Kas tiksliai pasirašoma?

McGesund sistemoje SLH-DSA pasirašo tą patį duomenų rinkinį, kurį apima ir Ed25519 parašas QR kode: QR kodo naudingąją apkrovą (payload). Joje, be kita ko, nurodyta, kuriai įmonei kodas priklauso (fid), kokios jis rūšies (typ), kada jis išduotas (iat) ir iki kada galioja (exp) — kaip kompaktiškai užkoduota baitų seka (CBOR).

Ši baitų seka yra mūsų pranešimas $M$. Jei kas nors vėliau pakeičia bent vieną bitą, nė vienas parašas nebetinka.

SLH-DSA parašas nėra pačiame QR kode. Būdamas maždaug 49 KB, jis tam per didelis. Jis saugomas kaip atskiras „antspaudas“ prie QR duomenų rinkinio McGesund serverinėje dalyje (backend) ir įkeliamas į naršyklę paspaudus „Patikrinti autentiškumą“.

---

3. Kodėl algoritmas vien iš maišos funkcijų?

Kiekvienas parašo algoritmas remiasi uždaviniu, kurio be slaptojo rakto praktiškai neįmanoma išspręsti:

Didelis kvantinis kompiuteris įveiktų Ed25519. FALCON ir ML-DSA laikomi atspariais kvantams — tačiau abu remiasi gardelių uždaviniais. Jei kada nors būtų rasta esminė ataka prieš gardeles, nukentėtų abu iš karto.

SLH-DSA, priešingai, tereikia, kad maišos funkcija darytų tai, kam ji sukurta:

Tai ilgiausiai ir nuodugniausiai ištirta visos kriptografijos prielaida. Net kvantinis kompiuteris čia padeda tik ribotai: Groverio algoritmas perpus sumažina saugumo bitų skaičių. Todėl 256 variantas naudoja $n = 32$ baitų $= 256$ bitų maišos reikšmes — po Groverio vis tiek lieka 128 bitai.

Būtent todėl lygis vadinamas Diversified: ML-DSA (gardelės) ir SLH-DSA (maiša) kilę iš skirtingų matematikos šeimų. Jei viena žlugtų, kita išlaiko.

---

4. 1 blokas: pasirašymas maišos grandinėmis (WOTS+)

Pagrindinė idėja stebėtinai paprasta. Pradėkime nuo vieno skaitmens.

Paimkite slaptą atsitiktinę reikšmę $s$ ir vėl ir vėl skaičiuokite jos maišą:

Grandinės pabaiga $p$ paskelbiama. Tai viešasis raktas šiam vienam skaitmeniui.

Norint pasirašyti skaitmenį $d$ nuo 0 iki 15, atskleidžiama grandinės reikšmė pozicijoje $d$:

Kas nori patikrinti, dar $15 - d$ kartų skaičiuoja $\sigma$ maišą. Jei gaunama lygiai $p$, parašas tikras:

Mažas pavyzdys

Pasirašome skaitmenį $d = 6$:

• Pasirašantysis paskelbia $\sigma = H^6(s)$.
• Tikrintojas apskaičiuoja $H^{9}(\sigma) = H^{15}(s)$ ir palygina su $p$. Sutampa.

Klastotojas, pamatęs $\sigma$, iš jo be vargo gali apskaičiuoti $H^7(s)$, $H^8(s)$ ir t. t. — vadinasi, pasirašyti didesnius skaitmenis. Mažesnių jis negali, nes tam reikėtų skaičiuoti maišą atgal.

Kontrolinė suma prieš „skaičiavimą į viršų“

Kad niekas negalėtų tiesiog padidinti skaitmenų, papildomai pasirašoma kontrolinė suma:

Jei klastotojas padidina pranešimo skaitmenį, $C$ tampa mažesnė — o tam jam tektų skaičiuoti atgal kontrolinės sumos grandinėje. Taip užblokuotos abi kryptys.

Pritaikius visai maišos reikšmei

32 baitų maišos reikšmė turi 64 skaitmenis šešioliktainėje sistemoje. Prie jų pridedami 3 kontrolinės sumos skaitmenys:

Toks parašas vadinamas WOTS+ (Winternitz One-Time Signature). Didžiausias jo trūkumas slypi pavadinime: one-time, t. y. vienkartinis. Kas tuo pačiu raktu pasirašo du skirtingus pranešimus, atskleidžia tiek grandinių reikšmių, kad tampa įmanomos klastotės.

---

5. 2 blokas: daug vienkartinių raktų po vienu stogu (Merkle medis)

Jei kiekvienas raktas gali būti naudojamas tik kartą, jų reikia labai daug — tačiau norima paskelbti tik vieną viešąjį raktą.

Sprendimas — Merkle medis: $2^{h'}$ WOTS+ porų viešieji raktai sudaro lapus. Kas du kaimynai kartu sumaišomi, rezultatai vėl poromis, kol viršuje lieka viena šaknis.

SLH-DSA-SHA2-256f kiekvieno medžio aukštis $h' = 4$, taigi $2^4 = 16$ lapų.

Norint parodyti, kad tam tikras lapas priklauso medžiui, pateikiamas autentifikavimo kelias: 4 gretimi (seseriniai) mazgai kelyje į viršų. Su jais tikrintojas, skaičiuodamas maišas, kyla nuo lapo iki šaknies. Jei gaunama žinoma šaknis, lapas priklauso medžiui.

---

6. 3 blokas: medžiai ant medžių (hipermedis)

16 vienkartinių raktų, žinoma, nepakanka. Todėl SLH-DSA krauna medžius vieną ant kito: medžio šaknis pasirašoma aukščiau esančio medžio WOTS+ raktu. Šis bokštas vadinamas hipermedžiu (hypertree).

SLH-DSA-SHA2-256f turi $d = 17$ sluoksnių, kiekvieno aukštis 4:

Taigi pačioje apačioje yra

lapų. Aukščiausiojo medžio šaknis vadinama $\text{PK.root}$ — tai ir yra tikrasis viešasis raktas.

Svarbu: niekas šių medžių neapskaičiuoja iš anksto. Visos slaptos reikšmės prireikus išvedamos iš slaptos pradinės reikšmės $\text{SK.seed}$. Saugomos tik keturios reikšmės po 32 baitus:

Privatųjį raktą sudaro visos keturios (128 baitai), viešąjį — tik PK.seed ir PK.root (64 baitai).

---

7. 4 blokas: miškas prieš atsitiktinius sutapimus (FORS)

Dabar tikroji problema: iš kur pasirašantysis žino, kuris iš $2^{68}$ lapų dar nepanaudotas?

Senesni maiša grįsti algoritmai (XMSS, LMS) tam veda skaitiklį. Jo niekada negalima atstatyti atgal — nei iš atsarginės kopijos, nei antru serveriu. Jei taip vis dėlto nutinka, vienkartinis raktas panaudojamas du kartus, ir algoritmas palaužiamas. Tokie algoritmai vadinami būseniniais.

SLH-DSA yra bebūsenis: lapas pseudoatsitiktinai parenkamas iš paties pranešimo. Tada gali atsitikti, kad du pranešimai pataiko į tą patį lapą. Todėl pačioje apačioje kabo ne vienkartinis, o kelių kartų parašas: FORS (Forest of Random Subsets).

FORS sudaro $k = 35$ maži Merkle medžiai, kurių kiekvienas turi $2^a = 2^9 = 512$ lapų. Lapai yra slaptos atsitiktinės reikšmės.

Pasirašant pranešimo maiša suskaidoma į 35 skaičius po 9 bitus. Kiekvienas skaičius „savo“ medyje parenka lygiai vieną lapą. Kiekvienam medžiui parašas turi:

• to lapo slaptą reikšmę
• jo autentifikavimo kelią (9 mazgai)

Kitam pranešimui klastotojas turėtų visuose 35 medžiuose pataikyti į lapus, kurių paslaptys jau atskleistos. Net jei tas pats FORS egzempliorius buvo panaudotas kelis kartus, tai beviltiška.

---

8. Visa pasirašymo eiga

1. Atsitiktinis komponentas. Iš $\text{SK.prf}$, naujo atsitiktinio skaičiaus ir pranešimo gaunama 32 baitų reikšmė $R$.
2. Pranešimo maiša.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 santraukos (digest) baitai padalijami: 40 baitų parenka 35 FORS lapus, likusi dalis nustato, kuris medis (idx_tree) ir kuris lapas (idx_leaf) pačioje hipermedžio apačioje naudojami.
3. FORS parašas pranešimui. Iš jo gaunamas FORS viešasis raktas.
4. Hipermedžio parašas šiam FORS raktui: 17 WOTS+ parašų, kiekvienas su autentifikavimo keliu, sluoksnis po sluoksnio iki pat $\text{PK.root}$.

Galutinis parašas yra tiesiog sujungimas:

---

9. Kodėl parašas užima 49 856 baitus

Su SLH-DSA-SHA2-256f parametrais dydį galima tiksliai perskaičiuoti ($n = 32$ baitai vienai maišos reikšmei):

Palyginimui: Ed25519 parašas užima 64 baitus, ML-DSA-87 — 4 627 baitus. Dydis yra kaina už tai, kad SLH-DSA apsieina vien maišos funkcijomis.

---

10. Kaip tikrina naršyklė

Tikrinti SLH-DSA atveju reiškia perskaičiuoti maišas.

1. Iš naujo apskaičiuoti santrauką iš $R$, viešojo rakto ir pranešimo.
2. Iš 35 atskleistų FORS lapų ir jų kelių apskaičiuoti 35 medžių šaknis, o iš jų — FORS viešąjį raktą.
3. Su kiekvienu iš 17 WOTS+ parašų baigti skaičiuoti grandinių maišas, sudaryti WOTS+ viešąjį raktą ir keliu pakilti iki medžio šaknies.
4. Pabaigoje turi gautis lygiai $\text{PK.root}$.

Tai keli tūkstančiai maišos funkcijos iškvietimų — kompiuteriui menkniekis. Mūsų naršyklėje patikra trunka maždaug nuo 6 iki 12 milisekundžių.

---

11. Kas nutinka, jei kas nors pakeičia duomenis?

Jei pasikeičia bent vienas pranešimo $M$ bitas, santrauka pasikeičia visiškai. Tada 35 skaičiai rodo į kitus FORS lapus, o algoritmas — į kitą vietą hipermedyje.

Atskleistos paslaptys nebetinka: perskaičiuotos šaknys skiriasi, ir pabaigoje negaunama $\text{PK.root}$. Patikra nepavyksta.

Kad vis tiek sukurtų galiojantį parašą, užpuolikas turėtų žinoti niekada neskelbtas paslaptis — t. y. apskaičiuoti maišos funkciją atgal.

---

12. Kodėl būtent 256f?

FIPS 205 apibrėžia dvylika parametrų rinkinių: dvi maišos funkcijų šeimas (SHA-2 ir SHAKE), tris saugumo lygius (128, 192, 256) ir kiekvienam po greitą („f“) ir mažą („s“) variantą.

256 reiškia NIST 5 saugumo kategoriją — tą patį lygį kaip FALCON-1024 ir ML-DSA-87.

„f“ pasirinkome todėl, kad įmonės vienu kartu gali išduoti iki 500 QR kodų. Su „s“ pasirašymas truktų daugiau nei 20 minučių, su „f“ — mažiau nei minutę. Užtat parašas didesnis — kadangi jis nėra QR kode, tai pakeliama.

SHA-2, o ne SHAKE, nes SHA-256 ir SHA-512 aparatiškai spartinami praktiškai bet kurioje įrangoje.

---

13. Atsitiktinumas pasirašant

FIPS 205 leidžia du $R$ generavimo būdus:

• deterministinį: tas pats pranešimas, tas pats parašas
• atsitiktinį („hedged“): įmaišomas naujas atsitiktinis skaičius

Mes naudojame atsitiktinį variantą. Todėl du to paties pranešimo parašai atrodo skirtingai — abu galioja. Tai apsunkina atakas, derinančias matavimus įrenginyje (energijos sąnaudas, laiką) su pakartotiniais parašais.

---

14. Ką konkrečiai su tuo daro McGesund

Lygis. PQ-Dual-Diversified galimas tarifuose Atsiliepimai Premium ir Signalai Premium. Tada QR kodas turi tris parašus:

Pasirašymas. Vienas SLH-DSA parašas kainuoja maždaug ketvirtį sekundės skaičiavimo laiko. Kad serveris tuo metu liktų pasiekiamas visiems kitiems, skaičiuoja atskiros foninės gijos.

Patikra. Skaitytojo naršyklė įkelia abu antspaudus ir patikrina juos tuo pačiu WASM moduliu kaip ir visus kitus PQ parašus. Mes pateikiame duomenis, o skaičiuojama lankytojo įrenginyje.

Sutikrinimas su NIST. Mūsų modulis išlaiko oficialius NIST testinius vektorius SLH-DSA-SHA2-256f algoritmui: iš NIST pradinių reikšmių baitas į baitą gaunami tie patys raktai, o visi tyčia pakeisti parašai atmetami. Tai galite patys patikrinti naršyklėje NIST testų puslapyje.

Laiko inkaras. Kaip ir visų raktų atveju, SLH-DSA rakto kontrolinis atspaudas per OpenTimestamps įtvirtinamas Bitcoin bloke.

---

15. SLH-DSA, ML-DSA ir FALCON greta

Trumpai tariant: SLH-DSA yra lėčiausias ir didžiausias iš trijų algoritmų — ir konservatyviausias. Jis nesiremia niekuo, ko ir taip jau nereikalautų bet kuris kitas parašas: saugia maišos funkcija.

---

16. Vienas sakinys įsidėmėti

Kas turi slaptąją pradinę reikšmę, pasirašo per ketvirtį sekundės. Kas jos neturi, turėtų skaičiuoti SHA-256 ar SHA-512 atgal — net ir su kvantiniu kompiuteriu.

Atsiliepimo skaitytojui tai reiškia: net jei kada nors žlugtų visi gardelėmis grįsti algoritmai, šis parašas liktų patikrinamas. Jam nereikia mumis tikėti. Jis gali perskaičiuoti.