SLH-DSA explicat matematic

1. Despre ce este vorba aici

La McGesund, clienții cu tarifele Evaluări Premium și Semnale Premium pot alege nivelul de semnătură PQ-Dual-Diversified. Atunci fiecare cod QR poartă, pe lângă semnătura clasică Ed25519, două semnături rezistente la calculul cuantic: ML-DSA-87 și SLH-DSA-SHA2-256f.

Acest articol o explică pe a doua. Este construită altfel decât tot ce mai folosim.

SLH-DSA nu este o criptare. Conținutul rămâne lizibil public. SLH-DSA dovedește originea și integritatea — ca orice semnătură digitală.

SLH-DSA înseamnă, în formă completă, Stateless Hash-Based Digital Signature Algorithm. A fost dezvoltat din SPHINCS+ și standardizat în 2024 ca FIPS 205. Numele dezvăluie deja particularitatea: procedeul folosește doar funcții hash. Fără rețele, fără curbe eliptice, fără numere prime mari.

---

2. Ce anume se semnează?

La McGesund, SLH-DSA semnează același set de date pe care îl acoperă și semnătura Ed25519 din codul QR: payload-ul codului QR. Acesta conține, printre altele, cărei firme îi aparține codul (fid), de ce tip este (typ), când a fost emis (iat) și până când este valabil (exp) — sub forma unui șir de octeți codificat compact (CBOR).

Acest șir de octeți este mesajul nostru $M$. Dacă cineva schimbă ulterior un singur bit, niciuna dintre semnături nu se mai potrivește.

Semnătura SLH-DSA nu se află în codul QR însuși. Cu aproximativ 49 KB este mult prea mare pentru asta. Ea stă ca „ștampilă” separată la înregistrarea QR din backendul McGesund și este încărcată în browser la clic pe „Verifică autenticitatea”.

---

3. De ce un procedeu bazat doar pe funcții hash?

Orice procedeu de semnătură se bazează pe o sarcină care, fără cheia secretă, este practic de nerezolvat:

Un calculator cuantic mare ar sparge Ed25519. FALCON și ML-DSA sunt considerate rezistente la calculul cuantic — dar ambele se sprijină pe probleme pe rețele. Dacă într-o zi s-ar descoperi un atac fundamental asupra rețelelor, ambele ar fi afectate deodată.

SLH-DSA, în schimb, are nevoie doar ca funcția hash să facă ceea ce a fost construită să facă:

Aceasta este ipoteza cel mai îndelung și mai temeinic studiată din întreaga criptografie. Nici un calculator cuantic nu ajută aici decât limitat: algoritmul Grover înjumătățește biții de securitate. De aceea, varianta 256 folosește valori hash de $n = 32$ de octeți $= 256$ de biți — după Grover rămân totuși 128 de biți.

Tocmai de aceea nivelul se numește Diversified: ML-DSA (rețele) și SLH-DSA (hash) provin din familii matematice diferite. Dacă una cade, cealaltă continuă să susțină.

---

4. Elementul 1: semnarea cu lanțuri de hash (WOTS+)

Ideea de bază este surprinzător de simplă. Începem cu o singură cifră.

Luăm o valoare aleatoare secretă $s$ și îi aplicăm hash-ul iar și iar:

Capătul lanțului, $p$, este publicat. Aceasta este cheia publică pentru această singură cifră.

Pentru a semna o cifră $d$ între 0 și 15, se dezvăluie valoarea din lanț de pe poziția $d$:

Cine vrea să verifice aplică hash-ul lui $\sigma$ încă de $15 - d$ ori. Dacă rezultă exact $p$, semnătura este autentică:

Un mini-exemplu

Semnăm cifra $d = 6$:

• Semnatarul publică $\sigma = H^6(s)$.
• Verificatorul calculează $H^{9}(\sigma) = H^{15}(s)$ și compară cu $p$. Se potrivește.

Un falsificator care a văzut $\sigma$ poate calcula din ea fără efort $H^7(s)$, $H^8(s)$ și așa mai departe — adică poate semna cifre mai mari. Cifre mai mici nu poate, pentru că ar trebui să aplice hash-ul înapoi.

Suma de control împotriva „numărării în sus”

Ca nimeni să nu poată pur și simplu mări cifrele, se semnează suplimentar o sumă de control:

Dacă un falsificator mărește o cifră a mesajului, $C$ devine mai mică — iar pentru asta ar trebui să calculeze înapoi în lanțul sumei de control. Astfel, ambele direcții sunt blocate.

Extins la o valoare hash

O valoare hash de 32 de octeți are 64 de cifre în baza 16. La acestea se adaugă 3 cifre de sumă de control:

O astfel de semnătură se numește WOTS+ (Winternitz One-Time Signature). Marele ei neajuns stă în nume: One-Time, de unică folosință. Cine semnează cu aceeași cheie două mesaje diferite dezvăluie atât de multe valori din lanțuri, încât falsurile devin posibile.

---

5. Elementul 2: multe chei de unică folosință sub un singur acoperiș (arborele Merkle)

Dacă fiecare cheie poate fi folosită o singură dată, ai nevoie de foarte multe — dar vrei să publici o singură cheie publică.

Soluția este un arbore Merkle: cheile publice a $2^{h'}$ perechi WOTS+ formează frunzele. Câte doi vecini sunt trecuți împreună prin hash, rezultatele din nou câte două, până când sus rămâne o singură rădăcină.

La SLH-DSA-SHA2-256f, fiecare arbore are înălțimea $h' = 4$, adică $2^4 = 16$ frunze.

Pentru a arăta că o anumită frunză aparține arborelui, se furnizează drumul de autentificare: cele 4 noduri-frate de pe drumul în sus. Cu ele, verificatorul urcă prin hash de la frunză până la rădăcină. Dacă rezultă rădăcina cunoscută, frunza aparține arborelui.

---

6. Elementul 3: arbori peste arbori (hiperarborele)

16 chei de unică folosință nu sunt, firește, de ajuns. De aceea SLH-DSA stivuiește arbori unii peste alții: rădăcina unui arbore este semnată cu o cheie WOTS+ a arborelui de deasupra. Acest turn se numește hiperarbore.

La SLH-DSA-SHA2-256f există $d = 17$ straturi, fiecare cu înălțimea 4:

Jos de tot stau astfel la dispoziție

frunze. Rădăcina arborelui de sus se numește $\text{PK.root}$ — ea este adevărata cheie publică.

Important: nimeni nu calculează acești arbori în avans. Toate valorile secrete sunt derivate la nevoie dintr-un seed secret $\text{SK.seed}$. Se stochează doar patru valori a câte 32 de octeți:

Cheia privată este formată din toate patru (128 de octeți), cea publică doar din PK.seed și PK.root (64 de octeți).

---

7. Elementul 4: o pădure împotriva nimeririlor întâmplătoare (FORS)

Acum problema propriu-zisă: de unde știe semnatarul care dintre cele $2^{68}$ frunze este încă nefolosită?

Procedeele mai vechi bazate pe hash (XMSS, LMS) țin pentru asta un contor. Acesta nu are voie să fie resetat niciodată — nici printr-un backup, nici printr-un al doilea server. Dacă totuși se întâmplă, o cheie de unică folosință este utilizată de două ori, iar procedeul este spart. Astfel de procedee se numesc cu stare.

SLH-DSA este fără stare: frunza este aleasă pseudoaleator din mesajul însuși. Se poate întâmpla atunci ca două mesaje să nimerească aceeași frunză. De aceea, jos de tot nu stă o semnătură de unică folosință, ci o semnătură de câteva folosiri: FORS (Forest of Random Subsets).

FORS constă din $k = 35$ arbori Merkle mici, fiecare cu $2^a = 2^9 = 512$ frunze. Frunzele sunt valori aleatoare secrete.

Pentru semnare, hash-ul mesajului este descompus în 35 de numere a câte 9 biți. Fiecare număr alege în „arborele său” exact o frunză. Semnătura conține, pentru fiecare arbore:

• valoarea secretă a acelei frunze
• drumul ei de autentificare (9 noduri)

Pentru un alt mesaj, un falsificator ar trebui să nimerească în toți cei 35 de arbori frunze ale căror secrete au fost deja dezvăluite. Chiar dacă aceeași instanță FORS a fost folosită de câteva ori, este fără șanse.

---

8. Întregul proces de semnare

1. Componenta aleatoare. Din $\text{SK.prf}$, un număr aleator proaspăt și mesaj rezultă o valoare de 32 de octeți $R$.
2. Hash-ul mesajului.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Cei 49 de octeți ai digestului sunt împărțiți: 40 de octeți aleg cele 35 de frunze FORS, restul stabilește care arbore (idx_tree) și care frunză (idx_leaf) de la baza hiperarborelui sunt folosite.
3. Semnătura FORS asupra mesajului. Din ea rezultă o cheie publică FORS.
4. Semnătura hiperarborelui asupra acestei chei FORS: 17 semnături WOTS+, fiecare cu un drum de autentificare, strat cu strat până sus la $\text{PK.root}$.

Semnătura finală este pur și simplu concatenarea:

---

9. De ce semnătura are 49.856 de octeți

Cu parametrii SLH-DSA-SHA2-256f, dimensiunea se poate recalcula exact ($n = 32$ de octeți per valoare hash):

Pentru comparație: o semnătură Ed25519 are 64 de octeți, ML-DSA-87 are 4.627 de octeți. Dimensiunea este prețul pentru faptul că SLH-DSA se descurcă doar cu funcții hash.

---

10. Cum verifică browserul

La SLH-DSA, a verifica înseamnă: a recalcula hash-urile.

1. Se recalculează digestul din $R$, cheia publică și mesaj.
2. Din cele 35 de frunze FORS dezvăluite și drumurile lor se calculează cele 35 de rădăcini de arbori și, din acestea, cheia publică FORS.
3. Cu fiecare dintre cele 17 semnături WOTS+, lanțurile sunt duse prin hash până la capăt, se formează cheia publică WOTS+ și se urcă prin hash pe drum până la rădăcina arborelui.
4. La final trebuie să rezulte exact $\text{PK.root}$.

Sunt câteva mii de apeluri hash — pentru un calculator, un fleac. În browser, verificarea durează la noi aproximativ 6 până la 12 milisecunde.

---

11. Ce se întâmplă dacă cineva modifică datele?

Dacă se schimbă fie și un singur bit din mesajul $M$, digestul se schimbă complet. Astfel, cele 35 de numere indică alte frunze FORS, iar procedeul un alt loc în hiperarbore.

Secretele dezvăluite nu se mai potrivesc: rădăcinile recalculate diferă și la final nu rezultă $\text{PK.root}$. Verificarea eșuează.

Pentru a construi totuși o semnătură validă, un atacator ar trebui să cunoască secrete care nu au fost publicate niciodată — adică să calculeze o funcție hash înapoi.

---

12. De ce tocmai 256f?

FIPS 205 definește douăsprezece seturi de parametri: două familii de hash (SHA-2 și SHAKE), trei niveluri de securitate (128, 192, 256) și pentru fiecare câte o variantă rapidă („f”) și una mică („s”).

256 înseamnă categoria de securitate NIST 5 — același nivel ca FALCON-1024 și ML-DSA-87.

Am ales „f” pentru că firmele pot emite până la 500 de coduri QR dintr-o dată. Cu „s”, semnarea ar dura peste 20 de minute, cu „f” sub un minut. În schimb, semnătura este mai mare — cum nu se află în codul QR, acest lucru este acceptabil.

SHA-2 în loc de SHAKE, pentru că SHA-256 și SHA-512 sunt accelerate hardware pe practic orice dispozitiv.

---

13. Aleatoriul la semnare

FIPS 205 permite două moduri de a genera $R$:

• determinist: același mesaj, aceeași semnătură
• randomizat („hedged”): se adaugă un număr aleator proaspăt

Folosim varianta randomizată. Două semnături asupra aceluiași mesaj arată de aceea diferit — ambele sunt valide. Acest lucru îngreunează atacurile care combină măsurători pe dispozitiv (consum de curent, timp) cu semnături repetate.

---

14. Ce face McGesund concret cu asta

Nivelul. PQ-Dual-Diversified este disponibil în Evaluări Premium și Semnale Premium. Un cod QR poartă atunci trei semnături:

Semnarea. O semnătură SLH-DSA costă aproximativ un sfert de secundă de timp de calcul. Pentru ca serverul să rămână între timp accesibil tuturor celorlalți, calculul este făcut de fire de execuție proprii, în fundal.

Verificarea. Browserul cititorului încarcă ambele ștampile și le verifică cu același modul WASM ca toate celelalte semnături PQ. Noi livrăm datele, calculul are loc pe dispozitivul vizitatorului.

Concordanța cu NIST. Modulul nostru trece vectorii de test oficiali NIST pentru SLH-DSA-SHA2-256f: din seed-urile NIST rezultă, octet cu octet, aceleași chei, iar toate semnăturile manipulate intenționat sunt respinse. Puteți verifica acest lucru chiar dumneavoastră în browser, pe pagina de test NIST.

Ancora temporală. Ca la toate cheile, amprenta cheii SLH-DSA este ancorată printr-un bloc Bitcoin, prin OpenTimestamps.

---

15. SLH-DSA, ML-DSA și FALCON, unul lângă altul

Pe scurt: SLH-DSA este cel mai lent și cel mai mare dintre cele trei procedee — și cel mai conservator. Nu se bazează pe nimic din ce nu presupune deja oricum orice altă semnătură: o funcție hash sigură.

---

16. O frază de reținut

Cine deține seed-ul secret semnează într-un sfert de secundă. Cine nu îl deține ar trebui să calculeze SHA-256 sau SHA-512 înapoi — chiar și cu un calculator cuantic.

Pentru cititorul unei recenzii, asta înseamnă: chiar dacă într-o zi toate procedeele bazate pe rețele ar cădea, această semnătură rămâne verificabilă. Nu trebuie să ne creadă. Poate să verifice singur.