SLH-DSA matemaatiliselt selgitatud

1. Millest siin jutt käib

McGesundis saavad klientid paketis Hinnangud Premium ja Signaalid Premium valida allkirjataseme PQ-Dual-Diversified. Siis kannab iga QR-kood lisaks klassikalisele Ed25519 allkirjale kaht kvantiresistentset allkirja: ML-DSA-87 ja SLH-DSA-SHA2-256f.

See artikkel selgitab neist teist. See on üles ehitatud teisiti kui kõik muu, mida me kasutame.

SLH-DSA ei ole krüpteerimine. Sisu jääb avalikult loetavaks. SLH-DSA tõendab päritolu ja terviklikkust — nagu iga digitaalallkiri.

SLH-DSA tähendab välja kirjutatuna Stateless Hash-Based Digital Signature Algorithm. See on välja arendatud SPHINCS+-ist ja standarditi 2024. aastal kui FIPS 205. Juba nimi reedab erilise: meetod kasutab ainult räsifunktsioone. Ei mingeid võresid, elliptilisi kõveraid ega suuri algarve.

---

2. Mida täpselt allkirjastatakse?

McGesundis allkirjastab SLH-DSA sama andmekirje, mida katab ka QR-koodis olev Ed25519 allkiri: QR-koodi payloadi. See sisaldab muu hulgas, millisele ettevõttele kood kuulub (fid), mis tüüpi see on (typ), millal see väljastati (iat) ja mis ajani see kehtib (exp) — kompaktselt kodeeritud baidijadana (CBOR).

See baidijada on meie sõnum $M$. Kui keegi muudab hiljem üht ainsat bitti, ei sobi ükski allkiri enam.

SLH-DSA allkiri ei asu QR-koodis endas. Umbes 49 KB-ga on see selleks liiga suur. See on McGesundi taustasüsteemis QR-kirje juures eraldi „templina“ ja laaditakse brauserisse, kui klõpsate nupul „Kontrolli autentsust“.

---

3. Miks meetod, mis koosneb ainult räsifunktsioonidest?

Iga allkirjastamismeetod põhineb ülesandel, mis on ilma salajase võtmeta praktiliselt lahendamatu:

Ed25519 murraks suur kvantarvuti. FALCONit ja ML-DSA-d peetakse kvantiresistentseks — kuid mõlemad toetuvad võreülesannetele. Kui ühel päeval leitaks võrede vastu põhimõtteline rünne, oleksid mõlemad korraga ohus.

SLH-DSA vajab seevastu vaid seda, et räsifunktsioon teeks seda, milleks see on ehitatud:

See on kogu krüptograafia kõige kauem ja põhjalikumalt uuritud eeldus. Ka kvantarvuti aitab siin vaid piiratult: Groveri algoritm poolitab turvabitid. Seepärast kasutab variant 256 räsiväärtusi pikkusega $n = 32$ baiti $= 256$ bitti — pärast Groverit jääb alles ikka veel 128 bitti.

Just seepärast nimetataksegi taset Diversified: ML-DSA (võred) ja SLH-DSA (räsi) pärinevad eri matemaatilistest perekondadest. Kui üks langeb, kannab teine edasi.

---

4. Ehitusplokk 1: allkirjastamine räsiahelatega (WOTS+)

Põhiidee on üllatavalt lihtne. Alustame ühestainsast numbrist.

Võta salajane juhuslik väärtus $s$ ja räsi seda ikka ja jälle:

Ahela lõpp $p$ avaldatakse. See on selle ühe numbri avalik võti.

Et allkirjastada number $d$ vahemikus 0 kuni 15, antakse välja ahela väärtus positsioonil $d$:

Kes tahab kontrollida, räsib $\sigma$-t veel $15 - d$ korda edasi. Kui tulemuseks on täpselt $p$, on allkiri ehtne:

Pisike näide

Allkirjastame numbri $d = 6$:

• Allkirjastaja avaldab $\sigma = H^6(s)$.
• Kontrollija arvutab $H^{9}(\sigma) = H^{15}(s)$ ja võrdleb seda $p$-ga. Sobib.

Võltsija, kes on $\sigma$-t näinud, saab sellest vaevata arvutada $H^7(s)$, $H^8(s)$ jne — ehk allkirjastada suuremaid numbreid. Väiksemaid ta ei saa, selleks peaks ta räsima tagurpidi.

Kontrollsumma „ülesloendamise“ vastu

Et keegi ei saaks numbreid lihtsalt suurendada, allkirjastatakse lisaks kontrollsumma:

Kui võltsija suurendab sõnumi mõnd numbrit, muutub $C$ väiksemaks — ja selleks peaks ta kontrollsumma ahelas tagurpidi arvutama. Sellega on mõlemad suunad suletud.

Kogu räsiväärtuse ulatuses

32-baidisel räsiväärtusel on 64 numbrit alusel 16. Neile lisanduvad 3 kontrollsumma numbrit:

Sellist allkirja nimetatakse WOTS+ (Winternitz One-Time Signature). Selle suur konks peitub nimes: One-Time. Kes allkirjastab sama võtmega kaks erinevat sõnumit, reedab nii palju ahela väärtusi, et võltsingud muutuvad võimalikuks.

---

5. Ehitusplokk 2: palju ühekordseid võtmeid ühe katuse all (Merkle-puu)

Kui iga võtit tohib kasutada vaid korra, on neid vaja väga palju — kuid avaldada tahetakse ainult üht avalikku võtit.

Lahendus on Merkle-puu: $2^{h'}$ WOTS+-võtmepaari avalikud võtmed moodustavad lehed. Kaks naabrit räsitakse alati kokku, tulemused omakorda paarikaupa, kuni üleval on üksainus juur.

SLH-DSA-SHA2-256f puhul on igal puul kõrgus $h' = 4$, seega $2^4 = 16$ lehte.

Et näidata, et teatud leht kuulub puusse, antakse autentimistee: 4 õdesõlme teel üles. Nende abil räsib kontrollija end lehelt juureni üles. Kui tulemuseks on tuntud juur, kuulub leht puusse.

---

6. Ehitusplokk 3: puud puude peal (hüperpuu)

16 ühekordsest võtmest muidugi ei piisa. Seepärast laob SLH-DSA puid üksteise peale: puu juur allkirjastatakse ülemise puu WOTS+-võtmega. Seda torni nimetatakse hüperpuuks.

SLH-DSA-SHA2-256f puhul on $d = 17$ kihti, igaüks kõrgusega 4:

Päris all on seega kasutada

lehte. Kõige ülemise puu juurt nimetatakse $\text{PK.root}$ — see ongi tegelik avalik võti.

Oluline: keegi ei arvuta neid puid ette. Kõik salajased väärtused tuletatakse vajaduse korral salajasest algväärtusest $\text{SK.seed}$. Salvestatakse ainult neli väärtust, igaüks 32 baiti:

Privaatvõti koosneb kõigist neljast (128 baiti), avalik võti ainult PK.seed-ist ja PK.root-ist (64 baiti).

---

7. Ehitusplokk 4: mets juhuslike tabamuste vastu (FORS)

Nüüd tegelik probleem: kust teab allkirjastaja, milline $2^{68}$ lehest on veel kasutamata?

Vanemad räsipõhised meetodid (XMSS, LMS) peavad selleks loendurit. Seda ei tohi kunagi lähtestada — ei varukoopia ega teise serveri kaudu. Kui see siiski juhtub, kasutatakse ühekordset võtit kaks korda ja meetod on murtud. Selliseid meetodeid nimetatakse olekupõhisteks.

SLH-DSA on olekuta: leht valitakse sõnumi enda põhjal pseudojuhuslikult. Siis võib juhtuda, et kaks sõnumit tabavad sama lehte. Seepärast ei ripu päris all mitte ühekordne allkiri, vaid mõnekordne allkiri: FORS (Forest of Random Subsets).

FORS koosneb $k = 35$ väikesest Merkle-puust, millest igaühel on $2^a = 2^9 = 512$ lehte. Lehed on salajased juhuslikud väärtused.

Allkirjastamiseks jagatakse sõnumi räsi 35 arvuks, igaüks 9 bitti. Iga arv valib „oma“ puus täpselt ühe lehe. Allkiri sisaldab iga puu kohta:

• selle lehe salajast väärtust
• selle autentimisteed (9 sõlme)

Võltsija peaks teise sõnumi jaoks tabama kõigis 35 puus lehti, mille saladused on juba reedetud. Isegi kui sama FORS-instantsi on kasutatud paar korda, on see lootusetu.

---

8. Allkirjastamise kogu kulg

1. Juhuslikkuse komponent. $\text{SK.prf}$-ist, värskest juhuslikust arvust ja sõnumist tekib 32-baidine väärtus $R$.
2. Sõnumi räsi.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Digesti 49 baiti jagatakse: 40 baiti valivad 35 FORS-lehte, ülejäänu määrab, millist puud (idx_tree) ja millist lehte (idx_leaf) hüperpuu päris all kasutatakse.
3. FORS-allkiri sõnumi üle. Sellest saadakse FORS-i avalik võti.
4. Hüperpuu allkiri selle FORS-võtme üle: 17 WOTS+-allkirja, igaühel oma autentimistee, kiht kihi haaval kuni $\text{PK.root}$-ini üles.

Valmis allkiri on lihtsalt nende järjestikku sidumine:

---

9. Miks allkiri on 49 856 baiti suur

SLH-DSA-SHA2-256f parameetritega saab suuruse täpselt järele arvutada ($n = 32$ baiti räsiväärtuse kohta):

Võrdluseks: Ed25519 allkiri on 64 baiti, ML-DSA-87 oma 4 627 baiti. Suurus on hind selle eest, et SLH-DSA saab hakkama ainult räsifunktsioonidega.

---

10. Kuidas brauser kontrollib

SLH-DSA puhul tähendab kontrollimine: uuesti räsimist.

1. Arvutada digest $R$-ist, avalikust võtmest ja sõnumist uuesti.
2. Arvutada 35 avaldatud FORS-lehest ja nende teedest 35 puu juurt ning neist FORS-i avalik võti.
3. Räsida iga 17 WOTS+-allkirjaga ahelad lõpuni, moodustada WOTS+-i avalik võti ja räsida tee kaudu puu juureni üles.
4. Lõpuks peab tulemuseks olema täpselt $\text{PK.root}$.

See on mõni tuhat räsikutset — arvuti jaoks tühiasi. Brauseris võtab kontroll meil umbes 6 kuni 12 millisekundit.

---

11. Mis juhtub, kui keegi andmekirjet muudab?

Kui muutub kas või üks bitt sõnumist $M$, muutub digest täielikult. Sellega osutavad 35 arvu teistele FORS-lehtedele ja meetod teisele kohale hüperpuus.

Avaldatud saladused ei sobi enam: järele arvutatud juured erinevad ja lõpuks ei tule välja $\text{PK.root}$. Kontroll kukub läbi.

Et sellest hoolimata kehtiv allkiri ehitada, peaks ründaja teadma saladusi, mida pole kunagi avaldatud — ehk arvutama räsifunktsiooni tagurpidi.

---

12. Miks just 256f?

FIPS 205 määratleb kaksteist parameetrikomplekti: kaks räsiperekonda (SHA-2 ja SHAKE), kolm turvataset (128, 192, 256) ning kummagi jaoks kiire („f“) ja väike („s“) variant.

256 tähendab NISTi turvakategooriat 5 — sama taset kui FALCON-1024 ja ML-DSA-87.

„f“ valisime, sest ettevõtted saavad väljastada kuni 500 QR-koodi korraga. „s“-iga kestaks allkirjastamine üle 20 minuti, „f“-iga alla minuti. Selle eest on allkiri suurem — kuna see ei ole QR-koodis, on see talutav.

SHA-2 SHAKE asemel, sest SHA-256 ja SHA-512 on praktiliselt igal riistvaral kiirendatud.

---

13. Juhuslikkus allkirjastamisel

FIPS 205 lubab $R$-i luua kahel viisil:

• deterministlikult: sama sõnum, sama allkiri
• randomiseeritult („hedged“): lisatakse värske juhuslik arv

Meie kasutame randomiseeritud varianti. Kaks sama sõnumi allkirja näevad seetõttu erinevad välja — mõlemad on kehtivad. See raskendab ründeid, mis kombineerivad seadmel tehtud mõõtmisi (voolutarve, aeg) korduvate allkirjadega.

---

14. Mida McGesund sellega konkreetselt teeb

Tase. PQ-Dual-Diversified on saadaval paketis Hinnangud Premium ja Signaalid Premium. QR-kood kannab siis kolme allkirja:

Allkirjastamine. Üks SLH-DSA allkiri võtab umbes veerand sekundit arvutusaega. Et server jääks selle ajal kõigile teistele kättesaadavaks, arvutavad eraldi taustalõimed.

Kontroll. Lugeja brauser laadib mõlemad templid ja kontrollib neid sama WASM-mooduliga nagu kõiki teisi PQ-allkirju. Meie tarnime andmed, arvutatakse külastaja seadmes.

Võrdlus NISTiga. Meie moodul läbib SLH-DSA-SHA2-256f ametlikud NISTi testvektorid: NISTi algväärtustest tekivad baidi haaval samad võtmed ja kõik meelega manipuleeritud allkirjad lükatakse tagasi. Seda saate NISTi testlehel ise brauseris kontrollida.

Ajaankur. Nagu kõigi võtmete puhul, ankurdatakse SLH-DSA võtme sõrmejälg OpenTimestampsi kaudu Bitcoini plokki.

---

15. SLH-DSA, ML-DSA ja FALCON kõrvuti

Lühidalt: SLH-DSA on kolmest meetodist kõige aeglasem ja suurem — ja kõige konservatiivsem. See ei toetu millelegi, mida iga teine allkiri niikuinii ei eeldaks: turvalisele räsifunktsioonile.

---

16. Üks lause kaasavõtmiseks

Kellel on salajane algväärtus, allkirjastab veerand sekundiga. Kellel seda ei ole, peaks SHA-256 või SHA-512 tagurpidi arvutama — ka kvantarvutiga.

Arvustuse lugeja jaoks tähendab see: isegi kui ühel päeval peaksid kõik võremeetodid langema, jääb see allkiri kontrollitavaks. Ta ei pea meid uskuma. Ta saab järele arvutada.