SLH-DSA matemaattisesti selitettynä

1. Mistä tässä on kyse

McGesundissa asiakkaat voivat paketeissa Arviot Premium ja Signaalit Premium valita allekirjoitustason PQ-Dual-Diversified. Tällöin jokainen QR-koodi kantaa klassisen Ed25519-allekirjoituksen lisäksi kahta kvanttiresistenttiä allekirjoitusta: ML-DSA-87 ja SLH-DSA-SHA2-256f.

Tämä kirjoitus selittää jälkimmäisen. Se on rakennettu eri tavalla kuin mikään muu, mitä käytämme.

SLH-DSA ei ole salausmenetelmä. Sisältö pysyy julkisesti luettavana. SLH-DSA todistaa alkuperän ja eheyden — kuten mikä tahansa digitaalinen allekirjoitus.

SLH-DSA tulee sanoista Stateless Hash-Based Digital Signature Algorithm. Se kehitettiin SPHINCS+:sta ja standardoitiin vuonna 2024 nimellä FIPS 205. Jo nimi paljastaa erityispiirteen: menetelmä käyttää pelkkiä tiivistefunktioita. Ei hiloja, ei elliptisiä käyriä, ei suuria alkulukuja.

---

2. Mitä tarkalleen allekirjoitetaan?

McGesundissa SLH-DSA allekirjoittaa saman tietueen, jonka myös QR-koodin Ed25519-allekirjoitus kattaa: QR-koodin payloadin. Se sisältää muun muassa tiedon siitä, mihin yritykseen koodi kuuluu (fid), minkä tyyppinen se on (typ), milloin se on myönnetty (iat) ja mihin asti se on voimassa (exp) — tiiviisti koodattuna tavujonona (CBOR).

Tämä tavujono on viestimme $M$. Jos joku muuttaa jälkikäteen yhdenkin bitin, mikään allekirjoituksista ei enää täsmää.

SLH-DSA-allekirjoitus ei ole itse QR-koodissa. Noin 49 kt:n kokoisena se on siihen aivan liian suuri. Se on erillisenä ”leimana” QR-tietueen yhteydessä McGesundin taustajärjestelmässä, ja se ladataan selaimeen, kun napsautatte ”Tarkista aitous”.

---

3. Miksi pelkistä tiivistefunktioista koostuva menetelmä?

Jokainen allekirjoitusmenetelmä perustuu tehtävään, joka on ilman salaista avainta käytännössä ratkaisematon:

Suuri kvanttitietokone murtaisi Ed25519:n. FALCONia ja ML-DSA:ta pidetään kvanttiresistentteinä — mutta molemmat nojaavat hilaongelmiin. Jos jonain päivänä löydettäisiin perustavanlaatuinen hyökkäys hiloja vastaan, se koskisi molempia yhtä aikaa.

SLH-DSA sen sijaan tarvitsee vain sen, että tiivistefunktio tekee sen, mihin se on rakennettu:

Tämä on koko kryptografian pisimpään ja perusteellisimmin tutkittu oletus. Kvanttitietokonekin auttaa tässä vain rajallisesti: Groverin algoritmi puolittaa turvallisuusbitit. Siksi variantti 256 käyttää tiivisteitä, joiden pituus on $n = 32$ tavua $= 256$ bittiä — Groverin jälkeenkin jää vielä 128 bittiä.

Juuri siksi taso on nimeltään Diversified: ML-DSA (hilat) ja SLH-DSA (tiiviste) ovat peräisin eri matematiikan perheistä. Jos toinen kaatuu, toinen kantaa.

---

4. Rakennuspalikka 1: allekirjoittaminen tiivisteketjuilla (WOTS+)

Perusajatus on yllättävän yksinkertainen. Aloitamme yhdestä ainoasta numerosta.

Ota salainen satunnaisarvo $s$ ja tiivistä se yhä uudelleen:

Ketjun loppu $p$ julkaistaan. Se on tämän yhden numeron julkinen avain.

Numeron $d$ allekirjoittamiseksi väliltä 0–15 annetaan ketjun arvo kohdassa $d$:

Se, joka haluaa todentaa, tiivistää $\sigma$:n vielä $15 - d$ kertaa. Jos tulokseksi saadaan täsmälleen $p$, allekirjoitus on aito:

Pieni esimerkki

Allekirjoitamme numeron $d = 6$:

• Allekirjoittaja julkaisee $\sigma = H^6(s)$.
• Todentaja laskee $H^{9}(\sigma) = H^{15}(s)$ ja vertaa sitä $p$:hen. Täsmää.

Väärentäjä, joka on nähnyt $\sigma$:n, voi siitä vaivatta laskea $H^7(s)$, $H^8(s)$ jne. — eli allekirjoittaa suurempia numeroita. Pienempiä hän ei voi, sillä siihen hänen pitäisi tiivistää taaksepäin.

Tarkistussumma ”ylöspäin laskemista” vastaan

Jotta kukaan ei voisi yksinkertaisesti kasvattaa numeroita, allekirjoitetaan lisäksi tarkistussumma:

Jos väärentäjä kasvattaa viestin jotakin numeroa, $C$ pienenee — ja sitä varten hänen pitäisi laskea tarkistussumman ketjussa taaksepäin. Näin molemmat suunnat on suljettu.

Skaalattuna koko tiivisteeseen

32 tavun tiivisteessä on 64 numeroa kantaluvussa 16. Niihin tulee lisäksi 3 tarkistussumman numeroa:

Tällaista allekirjoitusta kutsutaan nimellä WOTS+ (Winternitz One-Time Signature). Sen suuri koukku on nimessä: One-Time. Joka allekirjoittaa samalla avaimella kaksi eri viestiä, paljastaa niin monta ketjun arvoa, että väärennökset tulevat mahdollisiksi.

---

5. Rakennuspalikka 2: monta kertakäyttöistä avainta saman katon alla (Merkle-puu)

Jos kutakin avainta saa käyttää vain kerran, niitä tarvitaan hyvin paljon — mutta julkaista halutaan vain yksi julkinen avain.

Ratkaisu on Merkle-puu: $2^{h'}$ WOTS+-avainparin julkiset avaimet muodostavat lehdet. Kaksi naapuria tiivistetään aina yhteen, tulokset jälleen pareittain, kunnes ylimpänä on yksi ainoa juuri.

SLH-DSA-SHA2-256f:ssä jokaisen puun korkeus on $h' = 4$, eli lehtiä on $2^4 = 16$.

Osoittaakseen, että tietty lehti kuuluu puuhun, annetaan sen todennuspolku: 4 sisarsolmua matkalla ylös. Niiden avulla todentaja tiivistää tiensä lehdestä juureen. Jos tulokseksi saadaan tunnettu juuri, lehti kuuluu puuhun.

---

6. Rakennuspalikka 3: puita puiden päällä (hyperpuu)

16 kertakäyttöistä avainta ei tietenkään riitä. Siksi SLH-DSA pinoaa puita päällekkäin: puun juuri allekirjoitetaan yläpuolisen puun WOTS+-avaimella. Tätä tornia kutsutaan hyperpuuksi.

SLH-DSA-SHA2-256f:ssä on $d = 17$ kerrosta, kunkin korkeus 4:

Aivan alimpana on siten käytettävissä

lehteä. Ylimmän puun juurta kutsutaan nimellä $\text{PK.root}$ — se on varsinainen julkinen avain.

Tärkeää: kukaan ei laske näitä puita etukäteen. Kaikki salaiset arvot johdetaan tarvittaessa salaisesta lähtöarvosta $\text{SK.seed}$. Tallennetaan vain neljä arvoa, kukin 32 tavua:

Yksityinen avain koostuu kaikista neljästä (128 tavua), julkinen vain PK.seedistä ja PK.rootista (64 tavua).

---

7. Rakennuspalikka 4: metsä sattumaosumia vastaan (FORS)

Nyt varsinainen ongelma: mistä allekirjoittaja tietää, mikä $2^{68}$ lehdestä on vielä käyttämättä?

Vanhemmat tiivistepohjaiset menetelmät (XMSS, LMS) pitävät tätä varten laskuria. Sitä ei saa koskaan palauttaa taaksepäin — ei varmuuskopiolla eikä toisella palvelimella. Jos niin kuitenkin käy, kertakäyttöistä avainta käytetään kahdesti, ja menetelmä on murrettu. Tällaisia menetelmiä kutsutaan tilallisiksi.

SLH-DSA on tilaton: lehti valitaan näennäissatunnaisesti itse viestin perusteella. Silloin voi käydä niin, että kaksi viestiä osuu samaan lehteen. Siksi alimpana ei ole kertakäyttöinen allekirjoitus vaan muutaman kerran käytettävä allekirjoitus: FORS (Forest of Random Subsets).

FORS koostuu $k = 35$ pienestä Merkle-puusta, joissa kussakin on $2^a = 2^9 = 512$ lehteä. Lehdet ovat salaisia satunnaisarvoja.

Allekirjoitettaessa viestin tiiviste jaetaan 35 lukuun, kukin 9 bittiä. Kukin luku valitsee ”omasta” puustaan täsmälleen yhden lehden. Allekirjoitus sisältää jokaista puuta kohden:

• tämän lehden salaisen arvon
• sen todennuspolun (9 solmua)

Väärentäjän pitäisi toista viestiä varten osua kaikissa 35 puussa lehtiin, joiden salaisuudet on jo paljastettu. Vaikka samaa FORS-instanssia olisi käytetty muutaman kerran, se on toivotonta.

---

8. Allekirjoittamisen koko kulku

1. Satunnaiskomponentti. $\text{SK.prf}$:stä, tuoreesta satunnaisluvusta ja viestistä syntyy 32 tavun arvo $R$.
2. Viestin tiiviste.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Digestin 49 tavua jaetaan: 40 tavua valitsee 35 FORS-lehteä, loput määräävät, mitä puuta (idx_tree) ja mitä lehteä (idx_leaf) hyperpuun alimmassa kerroksessa käytetään.
3. FORS-allekirjoitus viestin yli. Siitä saadaan FORS-julkinen avain.
4. Hyperpuun allekirjoitus tämän FORS-avaimen yli: 17 WOTS+-allekirjoitusta, kullakin oma todennuspolkunsa, kerros kerrokselta ylös $\text{PK.root}$:iin asti.

Valmis allekirjoitus on yksinkertaisesti näiden peräkkäin liittäminen:

---

9. Miksi allekirjoitus on 49 856 tavun kokoinen

SLH-DSA-SHA2-256f:n parametreilla koon voi laskea tarkasti ($n = 32$ tavua tiivistettä kohti):

Vertailun vuoksi: Ed25519-allekirjoitus on 64 tavua, ML-DSA-87:n 4 627 tavua. Koko on hinta siitä, että SLH-DSA tulee toimeen pelkillä tiivistefunktioilla.

---

10. Miten selain todentaa

SLH-DSA:ssa todentaminen tarkoittaa: tiivistämistä uudelleen.

1. Lasketaan digest uudelleen $R$:stä, julkisesta avaimesta ja viestistä.
2. Lasketaan 35 paljastetusta FORS-lehdestä ja niiden poluista 35 puun juurta ja niistä FORS-julkinen avain.
3. Tiivistetään jokaisella 17 WOTS+-allekirjoituksella ketjut loppuun, muodostetaan WOTS+-julkinen avain ja tiivistetään polkua pitkin ylös puun juureen.
4. Lopuksi tulokseksi on saatava täsmälleen $\text{PK.root}$.

Siihen tarvitaan muutama tuhat tiivistekutsua — tietokoneelle pikkujuttu. Selaimessa todennus kestää meillä noin 6–12 millisekuntia.

---

11. Mitä tapahtuu, jos joku muuttaa tietuetta?

Jos viestistä $M$ muuttuu vain yksikin bitti, digest muuttuu täysin. Silloin 35 lukua osoittavat muihin FORS-lehtiin ja menetelmä toiseen paikkaan hyperpuussa.

Paljastetut salaisuudet eivät enää sovi: uudelleen lasketut juuret poikkeavat, eikä lopputuloksena ole $\text{PK.root}$. Todennus epäonnistuu.

Rakentaakseen silti kelvollisen allekirjoituksen hyökkääjän pitäisi tuntea salaisuuksia, joita ei ole koskaan julkaistu — eli laskea tiivistefunktio taaksepäin.

---

12. Miksi juuri 256f?

FIPS 205 määrittelee kaksitoista parametrijoukkoa: kaksi tiivisteperhettä (SHA-2 ja SHAKE), kolme turvallisuustasoa (128, 192, 256) ja kullekin nopea (”f”) ja pieni (”s”) variantti.

256 tarkoittaa NIST-turvallisuusluokkaa 5 — samaa tasoa kuin FALCON-1024 ja ML-DSA-87.

Valitsimme ”f”:n, koska yritykset voivat myöntää jopa 500 QR-koodia kerralla. ”s”:llä allekirjoittaminen kestäisi yli 20 minuuttia, ”f”:llä alle minuutin. Vastineeksi allekirjoitus on suurempi — koska se ei ole QR-koodissa, sen voi hyväksyä.

SHA-2 SHAKEn sijaan, koska SHA-256 ja SHA-512 ovat kiihdytettyjä käytännössä kaikessa laitteistossa.

---

13. Satunnaisuus allekirjoitettaessa

FIPS 205 sallii kaksi tapaa tuottaa $R$:

• deterministisesti: sama viesti, sama allekirjoitus
• satunnaistetusti (”hedged”): mukaan sekoitetaan tuore satunnaisluku

Käytämme satunnaistettua varianttia. Kaksi saman viestin allekirjoitusta näyttävät siksi erilaisilta — molemmat ovat kelvollisia. Tämä vaikeuttaa hyökkäyksiä, joissa laitteella tehtyjä mittauksia (virrankulutus, aika) yhdistetään toistuviin allekirjoituksiin.

---

14. Mitä McGesund tekee tällä käytännössä

Taso. PQ-Dual-Diversified on saatavilla paketeissa Arviot Premium ja Signaalit Premium. QR-koodi kantaa tällöin kolmea allekirjoitusta:

Allekirjoittaminen. Yksi SLH-DSA-allekirjoitus vie noin neljänneksen sekunnista laskenta-aikaa. Jotta palvelin pysyisi sillä välin kaikkien muiden tavoitettavissa, laskennan hoitavat erilliset taustasäikeet.

Todennus. Lukijan selain lataa molemmat leimat ja todentaa ne samalla WASM-moduulilla kuin kaikki muutkin PQ-allekirjoitukset. Me toimitamme tiedot, laskenta tapahtuu kävijän laitteella.

Vertailu NISTiin. Moduulimme läpäisee SLH-DSA-SHA2-256f:n viralliset NIST-testivektorit: NISTin lähtöarvoista syntyvät tavu tavulta samat avaimet, ja kaikki tahallisesti manipuloidut allekirjoitukset hylätään. Voitte tarkistaa tämän itse selaimessa NISTin testisivulla.

Aikaankkuri. Kuten kaikkien avainten kohdalla, SLH-DSA-avaimen sormenjälki ankkuroidaan OpenTimestampsin kautta Bitcoin-lohkoon.

---

15. SLH-DSA, ML-DSA ja FALCON rinnakkain

Lyhyesti: SLH-DSA on kolmesta menetelmästä hitain ja suurin — ja konservatiivisin. Se ei nojaa mihinkään, mitä jokainen muu allekirjoitus ei joka tapauksessa jo edellyttäisi: turvalliseen tiivistefunktioon.

---

16. Yksi lause mukaan otettavaksi

Se, jolla on salainen lähtöarvo, allekirjoittaa neljänneksessä sekunnista. Sen, jolla sitä ei ole, pitäisi laskea SHA-256 tai SHA-512 taaksepäin — myös kvanttitietokoneella.

Arvion lukijalle se tarkoittaa: vaikka kaikki hilamenetelmät jonain päivänä kaatuisivat, tämä allekirjoitus pysyy todennettavissa. Hänen ei tarvitse uskoa meitä. Hän voi laskea itse.