Az SLH-DSA matematikai magyarázata

1. Miről van szó

A McGesundnál az Értékelések Premium és a Jelzések Premium csomag ügyfelei választhatják a PQ-Dual-Diversified aláírási szintet. Ekkor minden QR-kód a klasszikus Ed25519-aláírás mellett két kvantumrezisztens aláírást is hordoz: az ML-DSA-87-et és az SLH-DSA-SHA2-256f-et.

Ez a cikk a másodikat magyarázza el. Másképp épül fel, mint bármi más, amit használunk.

Az SLH-DSA nem titkosítás. A tartalom nyilvánosan olvasható marad. Az SLH-DSA az eredetet és a sértetlenséget bizonyítja — mint minden digitális aláírás.

Az SLH-DSA kiírva Stateless Hash-Based Digital Signature Algorithm. A SPHINCS+-ból fejlesztették ki, és 2024-ben FIPS 205-ként szabványosították. Már a neve elárulja a különlegességét: az eljárás kizárólag hasítófüggvényeket használ. Se rácsok, se elliptikus görbék, se nagy prímszámok.

---

2. Mit írunk alá pontosan?

A McGesundnál az SLH-DSA ugyanazt az adatrekordot írja alá, amelyet a QR-kódban lévő Ed25519-aláírás is lefed: a QR-kód payloadját. Ez többek között tartalmazza, hogy melyik céghez tartozik a kód (fid), milyen típusú (typ), mikor állították ki (iat) és meddig érvényes (exp) — tömören kódolt bájtsorozatként (CBOR).

Ez a bájtsorozat a mi $M$ üzenetünk. Ha valaki utólag akár egyetlen bitet is megváltoztat, egyik aláírás sem illik rá többé.

Az SLH-DSA-aláírás nem magában a QR-kódban van. Mintegy 49 KB-os méretével ehhez túlságosan nagy. Különálló „bélyegzőként" a QR-rekord mellett tárolódik a McGesund backendjében, és akkor töltődik be a böngészőbe, amikor Ön a „Hitelesség ellenőrzése" gombra kattint.

---

3. Miért egy kizárólag hasítófüggvényekből álló eljárás?

Minden aláírási eljárás egy olyan feladaton alapul, amely a titkos kulcs nélkül gyakorlatilag megoldhatatlan:

Az Ed25519-et egy nagy kvantumszámítógép feltörné. A FALCON és az ML-DSA kvantumrezisztensnek számít — de mindkettő rácsproblémákra támaszkodik. Ha egy nap alapvető támadást találnának a rácsok ellen, mindkettőt egyszerre érintené.

Az SLH-DSA-nak ezzel szemben csak arra van szüksége, hogy a hasítófüggvény azt tegye, amire készült:

Ez az egész kriptográfia legrégebben és legalaposabban vizsgált feltevése. Még egy kvantumszámítógép is csak korlátozottan segít itt: a Grover-algoritmus megfelezi a biztonsági biteket. Ezért a 256-os változat $n = 32$ bájt $= 256$ bites hasítóértékeket használ — Grover után is marad még 128 bit.

Pontosan ezért hívják a szintet Diversified-nak: az ML-DSA (rácsok) és az SLH-DSA (hasítás) különböző matematikai családokból származik. Ha az egyik elbukik, a másik tart.

---

4. 1. építőelem: aláírás hasítóláncokkal (WOTS+)

Az alapötlet meglepően egyszerű. Egyetlen számjeggyel kezdünk.

Vegyen egy titkos véletlen értéket, $s$-t, és hasítsa újra meg újra:

A lánc végét, $p$-t, nyilvánosságra hozzuk. Ez az egyetlen számjegy nyilvános kulcsa.

Egy 0 és 15 közötti $d$ számjegy aláírásához a lánc $d$ pozíción lévő értékét adjuk ki:

Aki ellenőrizni akar, $\sigma$-t még $15 - d$ alkalommal tovább hasítja. Ha pontosan $p$ jön ki, az aláírás valódi:

Egy mini példa

Aláírjuk a $d = 6$ számjegyet:

• Az aláíró közzéteszi: $\sigma = H^6(s)$.
• Az ellenőrző kiszámolja $H^{9}(\sigma) = H^{15}(s)$ értékét, és összeveti $p$-vel. Egyezik.

Egy hamisító, aki látta $\sigma$-t, könnyedén kiszámíthatja belőle $H^7(s)$-t, $H^8(s)$-t stb. — vagyis nagyobb számjegyeket írhat alá. Kisebbeket nem, ahhoz visszafelé kellene hasítania.

Az ellenőrzőösszeg a „felfelé számolás" ellen

Hogy senki ne növelhesse egyszerűen a számjegyeket, egy ellenőrzőösszeget is aláírunk:

Ha egy hamisító megnöveli az üzenet egy számjegyét, $C$ kisebb lesz — ehhez pedig az ellenőrzőösszeg láncában kellene visszafelé számolnia. Így mindkét irány le van zárva.

Egy teljes hasítóértékre kivetítve

Egy 32 bájtos hasítóérték 16-os számrendszerben 64 számjegyből áll. Ehhez jön 3 ellenőrzőösszeg-számjegy:

Az ilyen aláírást WOTS+-nak (Winternitz One-Time Signature) nevezik. Nagy buktatója a nevében rejlik: One-Time, azaz egyszeri. Aki ugyanazzal a kulccsal két különböző üzenetet ír alá, annyi láncértéket fed fel, hogy hamisítások válnak lehetővé.

---

5. 2. építőelem: sok egyszer használatos kulcs egy fedél alatt (Merkle-fa)

Ha minden kulcsot csak egyszer szabad használni, nagyon sokra van szükség belőlük — nyilvánosságra viszont csak egyetlen nyilvános kulcsot szeretnénk hozni.

A megoldás a Merkle-fa: $2^{h'}$ WOTS+-kulcspár nyilvános kulcsai alkotják a leveleket. Két-két szomszédot összehasítunk, az eredményeket ismét párosával, amíg a csúcson egyetlen gyökér nem marad.

Az SLH-DSA-SHA2-256f-ben minden fa magassága $h' = 4$, tehát $2^4 = 16$ levele van.

Annak igazolására, hogy egy adott levél a fához tartozik, megadjuk a hitelesítési útvonalát: a felfelé vezető úton lévő 4 testvércsomópontot. Ezekkel az ellenőrző a levéltől a gyökérig felhasít. Ha az ismert gyökér jön ki, a levél a fához tartozik.

---

6. 3. építőelem: fák a fákon (hiperfa)

16 egyszer használatos kulcs természetesen nem elég. Ezért az SLH-DSA egymásra halmozza a fákat: egy fa gyökerét a fölötte lévő fa egy WOTS+-kulcsával írja alá. Ezt a tornyot hiperfának nevezik.

Az SLH-DSA-SHA2-256f-ben $d = 17$ réteg van, mindegyik 4 magas:

A legalsó szinten így

levél áll rendelkezésre. A legfelső fa gyökerét $\text{PK.root}$-nak nevezik — ez a tényleges nyilvános kulcs.

Fontos: ezeket a fákat senki sem számolja ki előre. Minden titkos érték szükség szerint egy titkos kezdőértékből, $\text{SK.seed}$-ből származtatható. Mindössze négy, egyenként 32 bájtos értéket tárolunk:

A titkos kulcs mind a négyből áll (128 bájt), a nyilvános csak a PK.seedből és a PK.rootból (64 bájt).

---

7. 4. építőelem: erdő a véletlen találatok ellen (FORS)

Most jön a valódi probléma: honnan tudja az aláíró, hogy a $2^{68}$ levél közül melyik használatlan még?

A régebbi hasításalapú eljárások (XMSS, LMS) ehhez számlálót vezetnek. Ezt soha nem szabad visszaállítani — sem biztonsági mentéssel, sem egy második szerverrel. Ha mégis megtörténik, egy egyszer használatos kulcsot kétszer használnak fel, és az eljárás feltört. Az ilyen eljárásokat állapottartónak nevezik.

Az SLH-DSA állapotmentes: a levelet magából az üzenetből választja ki álvéletlenszerűen. Ekkor előfordulhat, hogy két üzenet ugyanazt a levelet találja el. Ezért a legalján nem egyszeri, hanem néhányszor használható aláírás áll: a FORS (Forest of Random Subsets).

A FORS $k = 35$ kis Merkle-fából áll, mindegyikben $2^a = 2^9 = 512$ levéllel. A levelek titkos véletlen értékek.

Aláíráskor az üzenet hasítóértékét 35, egyenként 9 bites számra bontjuk. Minden szám a „saját" fájában pontosan egy levelet választ ki. Az aláírás minden fához tartalmazza:

• az adott levél titkos értékét
• a hitelesítési útvonalát (9 csomópont)

Egy másik üzenethez a hamisítónak mind a 35 fában olyan leveleket kellene eltalálnia, amelyek titkait már felfedték. Még ha ugyanazt a FORS-példányt néhányszor használták is, ez reménytelen.

---

8. Az aláírás teljes menete

1. Véletlen komponens. Az $\text{SK.prf}$-ből, egy friss véletlen számból és az üzenetből egy 32 bájtos $R$ érték keletkezik.
2. Az üzenet hasítóértéke.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   A digest 49 bájtját felosztjuk: 40 bájt választja ki a 35 FORS-levelet, a maradék határozza meg, hogy a hiperfa legalján melyik fát (idx_tree) és melyik levelet (idx_leaf) használjuk.
3. FORS-aláírás az üzenet felett. Ebből egy FORS-nyilvános kulcs adódik.
4. Hiperfa-aláírás e FORS-kulcs felett: 17 WOTS+-aláírás, mindegyik egy-egy hitelesítési útvonallal, rétegről rétegre egészen $\text{PK.root}$-ig.

A kész aláírás egyszerűen ezek egymás után fűzése:

---

9. Miért 49 856 bájt az aláírás

Az SLH-DSA-SHA2-256f paramétereivel a méret pontosan kiszámolható ($n = 32$ bájt hasítóértékenként):

Összehasonlításképp: egy Ed25519-aláírás 64 bájt, az ML-DSA-87-é 4627 bájt. A méret az ára annak, hogy az SLH-DSA semmi mással nem, csak hasítófüggvényekkel boldogul.

---

10. Hogyan ellenőriz a böngésző

Az SLH-DSA-nál az ellenőrzés azt jelenti: újrahasítás.

1. A digest újraszámolása $R$-ből, a nyilvános kulcsból és az üzenetből.
2. A 35 felfedett FORS-levélből és útvonalaikból a 35 fagyökér kiszámítása, majd ezekből a FORS-nyilvános kulcsé.
3. Mind a 17 WOTS+-aláírással a láncok végighasítása, a WOTS+-nyilvános kulcs képzése, majd az útvonalon felhasítás a fa gyökeréig.
4. A végén pontosan $\text{PK.root}$-nak kell kijönnie.

Ez néhány ezer hasítófüggvény-hívás — egy számítógépnek apróság. A böngészőben az ellenőrzés nálunk körülbelül 6–12 ezredmásodpercig tart.

---

11. Mi történik, ha valaki megváltoztatja az adatrekordot?

Ha az $M$ üzenetnek akár csak egyetlen bitje is megváltozik, a digest teljesen megváltozik. Így a 35 szám más FORS-levelekre, az eljárás pedig a hiperfa egy másik helyére mutat.

A felfedett titkok már nem illenek: az újraszámolt gyökerek eltérnek, és a végén nem $\text{PK.root}$ jön ki. Az ellenőrzés sikertelen.

Ahhoz, hogy mégis érvényes aláírást építsen, a támadónak olyan titkokat kellene ismernie, amelyeket soha nem tettek közzé — vagyis egy hasítófüggvényt kellene visszafelé kiszámolnia.

---

12. Miért éppen a 256f?

A FIPS 205 tizenkét paraméterkészletet határoz meg: két hasítócsaládot (SHA-2 és SHAKE), három biztonsági szintet (128, 192, 256), és mindegyikhez egy gyors („f") és egy kicsi („s") változatot.

A 256 az 5. NIST-biztonsági kategóriát jelenti — ugyanazt a szintet, mint a FALCON-1024 és az ML-DSA-87.

Az „f"-et azért választottuk, mert a cégek egyszerre akár 500 QR-kódot is kiállíthatnak. Az „s"-sel az aláírás több mint 20 percig tartana, az „f"-fel kevesebb mint egy percig. Cserébe az aláírás nagyobb — mivel nincs benne a QR-kódban, ez elviselhető.

SHA-2 a SHAKE helyett, mert az SHA-256 és az SHA-512 gyakorlatilag minden hardveren gyorsított.

---

13. Véletlen az aláírásnál

A FIPS 205 kétféle módot enged meg $R$ előállítására:

• determinisztikus: ugyanaz az üzenet, ugyanaz az aláírás
• randomizált („hedged"): egy friss véletlen szám is belekerül

Mi a randomizált változatot használjuk. Ugyanannak az üzenetnek két aláírása ezért különbözőnek látszik — mindkettő érvényes. Ez megnehezíti azokat a támadásokat, amelyek az eszközön végzett méréseket (áramfogyasztás, idő) ismételt aláírásokkal kombinálják.

---

14. Mit kezd ezzel konkrétan a McGesund

A szint. A PQ-Dual-Diversified az Értékelések Premium és a Jelzések Premium csomagban érhető el. Egy QR-kód ekkor három aláírást hordoz:

Az aláírás. Egy SLH-DSA-aláírás körülbelül negyed másodperc számítási időbe kerül. Hogy a szerver eközben mindenki más számára elérhető maradjon, külön háttérszálak végzik a számítást.

Az ellenőrzés. Az olvasó böngészője mindkét bélyegzőt betölti, és ugyanazzal a WASM-modullal ellenőrzi, mint az összes többi PQ-aláírást. Mi az adatokat szállítjuk, a számítás a látogató eszközén történik.

Az egyeztetés a NIST-tel. Modulunk átmegy az SLH-DSA-SHA2-256f hivatalos NIST-tesztvektorain: a NIST kezdőértékeiből bájtról bájtra ugyanazok a kulcsok keletkeznek, és a modul minden szándékosan manipulált aláírást elutasít. Ezt Ön is ellenőrizheti a böngészőben a NIST-tesztoldalon.

Az időhorgony. Mint minden kulcsnál, az SLH-DSA-kulcs ujjlenyomatát is az OpenTimestamps segítségével egy Bitcoin-blokkban rögzítjük.

---

15. Az SLH-DSA, az ML-DSA és a FALCON egymás mellett

Röviden: az SLH-DSA a három eljárás közül a leglassabb és a legnagyobb — és a legkonzervatívabb. Semmire sem épít, amit ne feltételezne amúgy is minden más aláírás: egy biztonságos hasítófüggvényre.

---

16. Egy mondat, amit érdemes megjegyezni

Aki birtokolja a titkos kezdőértéket, negyed másodperc alatt ír alá. Aki nem birtokolja, annak az SHA-256-ot vagy az SHA-512-t kellene visszafelé kiszámolnia — kvantumszámítógéppel is.

Egy értékelés olvasója számára ez azt jelenti: még ha egy nap az összes rácsalapú eljárás el is bukna, ez az aláírás ellenőrizhető marad. Nem kell hinnie nekünk. Utánaszámolhat.