SLH-DSA spjegat matematikament

1. Dwar xiex jitkellem dan l-artiklu

F'McGesund, il-klijenti bil-pjan Reċensjonijiet Premium u Sinjali Premium jistgħu jagħżlu l-livell ta' firma PQ-Dual-Diversified. F'dak il-każ kull kodiċi QR iġorr, minbarra l-firma klassika Ed25519, żewġ firem reżistenti għall-kwanti: ML-DSA-87 u SLH-DSA-SHA2-256f.

Dan l-artiklu jispjega t-tieni waħda. Hija mibnija b'mod differenti minn kull ħaġa oħra li nużaw.

SLH-DSA mhuwiex kriptaġġ. Il-kontenut jibqa' jinqara pubblikament. SLH-DSA jipprova l-oriġini u l-integrità — bħal kull firma diġitali.

SLH-DSA b'isem sħiħ huwa Stateless Hash-Based Digital Signature Algorithm. Ġie żviluppat minn SPHINCS+ u fl-2024 ġie standardizzat bħala FIPS 205. L-isem diġà jikxef x'għandu speċjali: il-metodu juża funzjonijiet hash biss. L-ebda lattiċe, l-ebda kurva ellittika, l-ebda numri primi kbar.

---

2. X'jiġi ffirmat eżattament?

F'McGesund, SLH-DSA jiffirma l-istess sett ta' data li tkopri wkoll il-firma Ed25519 fil-kodiċi QR: il-payload tal-kodiċi QR. Dan jindika, fost l-oħrajn, għal liema kumpanija jappartjeni l-kodiċi (fid), x'tip ta' kodiċi hu (typ), meta nħareġ (iat) u sa meta huwa validu (exp) — bħala sekwenza ta' byte kodifikata b'mod kompatt (CBOR).

Din is-sekwenza ta' byte hija l-messaġġ tagħna $M$. Jekk xi ħadd aktar tard ibiddel bit wieħed biss, l-ebda waħda mill-firem ma tgħodd aktar.

Il-firma SLH-DSA ma tinsabx fil-kodiċi QR innifsu. B'madwar 49 KB hija ferm kbira wisq għal dan. Tinżamm bħala “timbru” separat mar-rekord tal-QR fil-backend ta' McGesund u tinġieb fil-browser meta tikklikkja fuq “Ivverifika l-awtentiċità”.

---

3. Għaliex metodu magħmul biss minn funzjonijiet hash?

Kull metodu ta' firma jistrieħ fuq kompitu li prattikament ma jistax jiġi solvut mingħajr iċ-ċavetta sigrieta:

Kompjuter kwantistiku kbir jikser lil Ed25519. FALCON u ML-DSA huma meqjusa reżistenti għall-kwanti — iżda t-tnejn jistrieħu fuq problemi ta' lattiċi. Jekk xi darba jinstab attakk fundamentali fuq il-lattiċi, it-tnejn ikunu milquta fl-istess ħin.

SLH-DSA, għall-kuntrarju, jeħtieġ biss li l-funzjoni hash tagħmel dak li nbniet għalih:

Din hija l-assunzjoni studjata l-aktar fit-tul u bl-aktar mod bir-reqqa fil-kriptografija kollha. Anki kompjuter kwantistiku hawn jgħin biss b'mod limitat: l-algoritmu ta' Grover inaqqas bin-nofs il-bits tas-sigurtà. Għalhekk il-varjant 256 juża valuri hash ta' $n = 32$ byte $= 256$ bit — wara Grover xorta jibqgħu 128 bit.

Eżattament għalhekk il-livell jissejjaħ Diversified: ML-DSA (lattiċi) u SLH-DSA (hash) ġejjin minn familji differenti tal-matematika. Jekk waħda taqa', l-oħra żżomm.

---

4. Blokk 1: l-iffirmar b'katini tal-hash (WOTS+)

L-idea bażika hija sempliċi b'mod sorprendenti. Nibdew b'ċifra waħda.

Ħu valur każwali sigriet $s$ u agħmel il-hash tiegħu darba wara l-oħra:

It-tarf tal-katina, $p$, jiġi ppubblikat. Din hija ċ-ċavetta pubblika għal din iċ-ċifra waħda.

Biex tiffirma ċifra $d$ bejn 0 u 15, tikxef il-valur tal-katina fil-pożizzjoni $d$:

Min irid jivverifika jagħmel il-hash ta' $\sigma$ $15 - d$ darba oħra. Jekk joħroġ eżattament $p$, il-firma hija ġenwina:

Eżempju żgħir

Niffirmaw iċ-ċifra $d = 6$:

• Il-firmatarju jippubblika $\sigma = H^6(s)$.
• Il-verifikatur jikkalkula $H^{9}(\sigma) = H^{15}(s)$ u jqabblu ma' $p$. Jaqbel.

Falsifikatur li ra $\sigma$ jista' faċilment jikkalkula minnu $H^7(s)$, $H^8(s)$ u l-bqija — jiġifieri jiffirma ċifri akbar. Ċifri iżgħar ma jistax, għax għal dan ikollu jagħmel il-hash lura.

Iċ-checksum kontra l-“għadd 'il fuq”

Biex ħadd ma jkun jista' sempliċement iżid iċ-ċifri, jiġi ffirmat ukoll checksum:

Jekk falsifikatur iżid ċifra tal-messaġġ, $C$ isir iżgħar — u għal dan ikollu jikkalkula lura fil-katina taċ-checksum. B'hekk iż-żewġ direzzjonijiet huma mblukkati.

Estiż għal valur hash sħiħ

Valur hash ta' 32 byte għandu 64 ċifra fil-bażi 16. Magħhom jiżdiedu 3 ċifri taċ-checksum:

Firma bħal din tissejjaħ WOTS+ (Winternitz One-Time Signature). Id-difett il-kbir tagħha jinsab fl-isem: One-Time, jiġifieri għal darba waħda. Min jiffirma żewġ messaġġi differenti bl-istess ċavetta jikxef tant valuri tal-katini li l-falsifikazzjonijiet isiru possibbli.

---

5. Blokk 2: ħafna ċwievet ta' darba taħt saqaf wieħed (siġra ta' Merkle)

Jekk kull ċavetta tista' tintuża darba biss, ikollok bżonn ħafna minnhom — imma trid tippubblika ċavetta pubblika waħda biss.

Is-soluzzjoni hija siġra ta' Merkle: iċ-ċwievet pubbliċi ta' $2^{h'}$ par WOTS+ jiffurmaw il-weraq. Kull żewġ ġirien jiġu hashjati flimkien, ir-riżultati għal darb'oħra f'pari, sakemm fil-quċċata jibqa' għerq wieħed biss.

F'SLH-DSA-SHA2-256f kull siġra għandha għoli ta' $h' = 4$, jiġifieri $2^4 = 16$-il werqa.

Biex turi li ċerta werqa tappartjeni lis-siġra, tagħti l-mogħdija tal-awtentikazzjoni: l-4 nodi aħwa fit-triq 'il fuq. B'dawn il-verifikatur jagħmel il-hash 'il fuq mill-werqa sal-għerq. Jekk joħroġ l-għerq magħruf, il-werqa tappartjeni lis-siġra.

---

6. Blokk 3: siġar fuq siġar (hypertree)

Naturalment 16-il ċavetta ta' darba mhumiex biżżejjed. Għalhekk SLH-DSA jpoġġi siġar waħda fuq l-oħra: l-għerq ta' siġra jiġi ffirmat b'ċavetta WOTS+ tas-siġra ta' fuqha. Dan it-torri jissejjaħ hypertree.

F'SLH-DSA-SHA2-256f hemm $d = 17$-il saff, kull wieħed b'għoli ta' 4:

Fil-qiegħ għalhekk ikun hemm disponibbli

werqa. L-għerq tas-siġra l-aktar 'il fuq jissejjaħ $\text{PK.root}$ — din hija ċ-ċavetta pubblika vera.

Importanti: ħadd ma jikkalkula dawn is-siġar minn qabel. Il-valuri sigrieti kollha jiġu derivati meta jkun meħtieġ minn valur tal-bidu sigriet $\text{SK.seed}$. Jinħażnu biss erba' valuri ta' 32 byte kull wieħed:

Iċ-ċavetta privata tikkonsisti mill-erbgħa kollha (128 byte), dik pubblika biss minn PK.seed u PK.root (64 byte).

---

7. Blokk 4: foresta kontra l-laqtiet b'kumbinazzjoni (FORS)

Issa l-problema vera: kif jaf il-firmatarju liema mill-$2^{68}$ werqa għadha ma ntużatx?

Metodi eqdem ibbażati fuq il-hash (XMSS, LMS) iżommu għal dan counter. Dan qatt ma jista' jiġi resettjat — la minn backup, u lanqas minn server ieħor. Jekk xorta jiġri, ċavetta ta' darba tintuża darbtejn u l-metodu jinkiser. Metodi bħal dawn jissejħu b'stat (stateful).

SLH-DSA huwa mingħajr stat (stateless): il-werqa tintgħażel b'mod psewdo-każwali mill-messaġġ innifsu. Allura jista' jiġri li żewġ messaġġi jolqtu l-istess werqa. Għalhekk fil-qiegħ ma hemmx firma ta' darba, iżda firma għal ftit drabi: FORS (Forest of Random Subsets).

FORS jikkonsisti minn $k = 35$ siġra ta' Merkle żgħira, kull waħda b'$2^a = 2^9 = 512$-il werqa. Il-weraq huma valuri każwali sigrieti.

Biex tiffirma, il-hash tal-messaġġ jinqasam f'35 numru ta' 9 bit kull wieħed. Kull numru jagħżel eżattament werqa waħda fis-siġra “tiegħu”. Għal kull siġra l-firma fiha:

• il-valur sigriet ta' dik il-werqa
• il-mogħdija tal-awtentikazzjoni tagħha (9 nodi)

Għal messaġġ ieħor falsifikatur ikollu jolqot f'kull waħda mill-35 siġra weraq li s-sigrieti tagħhom diġà ġew mikxufa. Anki jekk l-istess istanza FORS intużat xi ftit drabi, dan huwa bla tama.

---

8. Il-proċess kollu tal-iffirmar

1. Komponent każwali. Minn $\text{SK.prf}$, numru każwali ġdid u l-messaġġ joħroġ valur ta' 32 byte $R$.
2. Hash tal-messaġġ.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Id-49 byte tad-digest jinqasmu: 40 byte jagħżlu l-35 werqa FORS, il-bqija jiddetermina liema siġra (idx_tree) u liema werqa (idx_leaf) fil-qiegħ tal-hypertree jintużaw.
3. Firma FORS fuq il-messaġġ. Minnha toħroġ ċavetta pubblika FORS.
4. Firma tal-hypertree fuq din iċ-ċavetta FORS: 17-il firma WOTS+, kull waħda b'mogħdija tal-awtentikazzjoni, saff wara saff sa $\text{PK.root}$.

Il-firma lesta hija sempliċement il-konkatenazzjoni:

---

9. Għaliex il-firma hija ta' 49,856 byte

Bil-parametri ta' SLH-DSA-SHA2-256f id-daqs jista' jiġi kkalkulat eżattament ($n = 32$ byte għal kull valur hash):

Bħala paragun: firma Ed25519 għandha 64 byte, ML-DSA-87 għandha 4,627 byte. Id-daqs huwa l-prezz biex SLH-DSA jirnexxilu b'xejn ħlief funzjonijiet hash.

---

10. Kif jivverifika l-browser

Fil-każ ta' SLH-DSA, li tivverifika tfisser: terġa' tagħmel il-hash.

1. Erġa' kkalkula d-digest minn $R$, iċ-ċavetta pubblika u l-messaġġ.
2. Mill-35 werqa FORS mikxufa u l-mogħdijiet tagħhom, ikkalkula l-35 għerq tas-siġar u minnhom iċ-ċavetta pubblika FORS.
3. B'kull waħda mis-17-il firma WOTS+, kompli l-hash tal-katini sat-tarf, ifforma ċ-ċavetta pubblika WOTS+ u agħmel il-hash 'il fuq mal-mogħdija sal-għerq tas-siġra.
4. Fl-aħħar irid joħroġ eżattament $\text{PK.root}$.

Dawn huma xi ftit eluf ta' sejħiet tal-hash — għal kompjuter xejn ma huma. Fil-browser, għandna l-verifika tieħu madwar 6 sa 12-il millisekonda.

---

11. X'jiġri jekk xi ħadd ibiddel id-data?

Jekk jinbidel anki bit wieħed biss tal-messaġġ $M$, id-digest jinbidel kompletament. Allura l-35 numru jippuntaw lejn weraq FORS oħra u l-metodu lejn post ieħor fil-hypertree.

Is-sigrieti mikxufa ma jaqblux aktar: l-għeruq ikkalkulati mill-ġdid ikunu differenti, u fl-aħħar ma joħroġx $\text{PK.root}$. Il-verifika tfalli.

Biex xorta jibni firma valida, attakkant ikollu jkun jaf sigrieti li qatt ma ġew ippubblikati — jiġifieri jikkalkula funzjoni hash lura.

---

12. Għaliex eżattament 256f?

FIPS 205 jiddefinixxi tnax-il sett ta' parametri: żewġ familji tal-hash (SHA-2 u SHAKE), tliet livelli ta' sigurtà (128, 192, 256) u għal kull wieħed varjant mgħaġġel (“f”) u varjant żgħir (“s”).

256 tfisser il-kategorija ta' sigurtà NIST 5 — l-istess livell bħal FALCON-1024 u ML-DSA-87.

Għażilna “f” għax il-kumpaniji jistgħu joħorġu sa 500 kodiċi QR f'daqqa. B'“s” l-iffirmar jieħu aktar minn 20 minuta, b'“f” inqas minn minuta. Min-naħa l-oħra l-firma hija akbar — peress li ma tinsabx fil-kodiċi QR, dan jista' jiġi ttollerat.

SHA-2 minflok SHAKE, għax SHA-256 u SHA-512 huma aċċellerati fil-hardware prattikament fuq kull apparat.

---

13. Il-każwalità fl-iffirmar

FIPS 205 jippermetti żewġ modi kif jiġi ġġenerat $R$:

• deterministiku: l-istess messaġġ, l-istess firma
• randomizzat (“hedged”): jiddaħħal numru każwali ġdid

Aħna nużaw il-varjant randomizzat. Għalhekk żewġ firem fuq l-istess messaġġ jidhru differenti — it-tnejn huma validi. Dan jagħmel aktar diffiċli l-attakki li jgħaqqdu kejl fuq l-apparat (konsum tal-elettriku, ħin) ma' firem ripetuti.

---

14. X'tagħmel McGesund konkretament b'dan

Il-livell. PQ-Dual-Diversified huwa disponibbli f'Reċensjonijiet Premium u Sinjali Premium. Kodiċi QR imbagħad iġorr tliet firem:

L-iffirmar. Firma SLH-DSA tiswa madwar kwart ta' sekonda ħin ta' kalkolu. Biex sadanittant is-server jibqa' aċċessibbli għal kulħadd, il-kalkoli jsiru minn threads apposta fl-isfond.

Il-verifika. Il-browser tal-qarrej iġib iż-żewġ timbri u jivverifikahom bl-istess modulu WASM bħall-firem PQ l-oħra kollha. Aħna nfornu d-data; il-kalkolu jsir fuq l-apparat tal-viżitatur.

Il-qbil ma' NIST. Il-modulu tagħna jgħaddi mill-vetturi tat-test uffiċjali ta' NIST għal SLH-DSA-SHA2-256f: mill-valuri tal-bidu ta' NIST joħorġu, byte b'byte, l-istess ċwievet, u l-firem kollha mbagħbsa apposta jiġu miċħuda. Tista' tivverifika dan int stess fil-browser fuq il-paġna tat-test NIST.

L-ankra taż-żmien. Bħal fil-każ taċ-ċwievet kollha, il-marka tas-swaba' taċ-ċavetta SLH-DSA tiġi ankrata permezz ta' OpenTimestamps ġo blokk ta' Bitcoin.

---

15. SLH-DSA, ML-DSA u FALCON ħdejn xulxin

Fil-qosor: SLH-DSA huwa l-aktar bil-mod u l-akbar mit-tliet metodi — u l-aktar konservattiv. Ma jistrieħ fuq xejn li kull firma oħra ma tassumix diġà xorta waħda: funzjoni hash sigura.

---

16. Sentenza waħda biex tieħu miegħek

Min għandu l-valur tal-bidu sigriet jiffirma f'kwart ta' sekonda. Min m'għandux ikollu jikkalkula SHA-256 jew SHA-512 lura — anki b'kompjuter kwantistiku.

Għall-qarrej ta' reċensjoni dan ifisser: anki jekk xi darba jaqgħu l-metodi kollha bbażati fuq il-lattiċi, din il-firma tibqa' verifikabbli. Mhux obbligat jemminna. Jista' jikkalkula huwa stess.