SLH-DSA matemātiski izskaidrots

1. Par ko šeit ir runa

McGesund klienti ar tarifu Novērtējumi Premium un Signāli Premium var izvēlēties paraksta līmeni PQ-Dual-Diversified. Tad katrs QR kods līdzās klasiskajam Ed25519 parakstam nes divus kvantu izturīgus parakstus: ML-DSA-87 un SLH-DSA-SHA2-256f.

Šis raksts skaidro otro. Tas ir uzbūvēts citādi nekā viss pārējais, ko mēs izmantojam.

SLH-DSA nav šifrēšana. Saturs paliek publiski lasāms. SLH-DSA pierāda izcelsmi un neskartību — kā jebkurš ciparparaksts.

SLH-DSA pilnā nosaukumā ir Stateless Hash-Based Digital Signature Algorithm. Tas izstrādāts no SPHINCS+ un 2024. gadā standartizēts kā FIPS 205. Nosaukums jau atklāj tā īpatnību: algoritms izmanto tikai jaucējfunkcijas. Nekādu režģu, nekādu eliptisko līkņu, nekādu lielu pirmskaitļu.

---

2. Kas tieši tiek parakstīts?

McGesund vietnē SLH-DSA paraksta to pašu datu kopu, ko aptver arī Ed25519 paraksts QR kodā: QR koda lietderīgo slodzi (payload). Tajā cita starpā norādīts, kuram uzņēmumam kods pieder (fid), kāda veida tas ir (typ), kad tas izsniegts (iat) un līdz kuram brīdim tas ir derīgs (exp) — kā kompakti kodēta baitu virkne (CBOR).

Šī baitu virkne ir mūsu ziņojums $M$. Ja kāds vēlāk izmaina kaut vienu bitu, neviens no parakstiem vairs neatbilst.

SLH-DSA paraksts neatrodas pašā QR kodā. Ar aptuveni 49 KB tas tam ir pārāk liels. Tas glabājas kā atsevišķs „zīmogs“ pie QR datu ieraksta McGesund aizmugursistēmā (backend) un tiek ielādēts pārlūkprogrammā, noklikšķinot uz „Pārbaudīt autentiskumu“.

---

3. Kāpēc algoritms tikai no jaucējfunkcijām?

Katrs parakstu algoritms balstās uz uzdevumu, kas bez slepenās atslēgas praktiski nav atrisināms:

Liels kvantu dators uzlauztu Ed25519. FALCON un ML-DSA tiek uzskatīti par kvantu izturīgiem — taču abi balstās uz režģu problēmām. Ja kādreiz tiktu atrasts fundamentāls uzbrukums režģiem, tas skartu abus vienlaikus.

SLH-DSA turpretī vajag tikai to, lai jaucējfunkcija darītu to, kam tā radīta:

Tas ir visilgāk un visrūpīgāk pētītais pieņēmums visā kriptogrāfijā. Arī kvantu dators šeit palīdz tikai ierobežoti: Grovera algoritms uz pusi samazina drošības bitus. Tāpēc variants 256 izmanto jaucējvērtības ar $n = 32$ baitiem $= 256$ bitiem — pēc Grovera joprojām paliek 128 biti.

Tieši tāpēc līmenis saucas Diversified: ML-DSA (režģi) un SLH-DSA (jaucējfunkcijas) nāk no dažādām matemātikas saimēm. Ja viena krīt, otra turpina nest.

---

4. 1. būvbloks: parakstīšana ar jaucējķēdēm (WOTS+)

Pamatideja ir pārsteidzoši vienkārša. Sāksim ar vienu vienīgu ciparu.

Ņemiet slepenu nejaušu vērtību $s$ un jauciet to atkal un atkal:

Ķēdes gals $p$ tiek publicēts. Tā ir publiskā atslēga šim vienam ciparam.

Lai parakstītu ciparu $d$ no 0 līdz 15, atklāj ķēdes vērtību pozīcijā $d$:

Kas vēlas pārbaudīt, jauc $\sigma$ vēl $15 - d$ reizes. Ja iznāk tieši $p$, paraksts ir īsts:

Mini piemērs

Parakstām ciparu $d = 6$:

• Parakstītājs publicē $\sigma = H^6(s)$.
• Pārbaudītājs aprēķina $H^{9}(\sigma) = H^{15}(s)$ un salīdzina ar $p$. Sakrīt.

Viltotājs, kurš redzējis $\sigma$, no tā bez pūlēm var aprēķināt $H^7(s)$, $H^8(s)$ utt. — tātad parakstīt lielākus ciparus. Mazākus viņš nevar, jo tam būtu jājauc atpakaļ.

Kontrolsumma pret „uzskaitīšanu uz augšu“

Lai neviens nevarētu ciparus vienkārši palielināt, papildus tiek parakstīta kontrolsumma:

Ja viltotājs palielina kādu ziņojuma ciparu, $C$ kļūst mazāka — un tam viņam kontrolsummas ķēdē būtu jārēķina atpakaļ. Tādējādi abi virzieni ir bloķēti.

Pārnests uz veselu jaucējvērtību

32 baitu jaucējvērtībai ir 64 cipari sešpadsmitnieku sistēmā. Klāt nāk 3 kontrolsummas cipari:

Šādu parakstu sauc par WOTS+ (Winternitz One-Time Signature). Tā lielais āķis slēpjas nosaukumā: One-Time — vienreizējs. Kas ar vienu un to pašu atslēgu paraksta divus dažādus ziņojumus, atklāj tik daudz ķēžu vērtību, ka kļūst iespējami viltojumi.

---

5. 2. būvbloks: daudz vienreizējo atslēgu zem viena jumta (Merkle koks)

Ja katru atslēgu drīkst izmantot tikai vienu reizi, to vajag ļoti daudz — taču publicēt gribas tikai vienu publisko atslēgu.

Risinājums ir Merkle koks: $2^{h'}$ WOTS+ pāru publiskās atslēgas veido lapas. Katri divi kaimiņi tiek sajaukti kopā, rezultāti atkal pa pāriem, līdz augšā paliek viena vienīga sakne.

SLH-DSA-SHA2-256f katram kokam ir augstums $h' = 4$, tātad $2^4 = 16$ lapas.

Lai parādītu, ka noteikta lapa pieder kokam, sniedz autentifikācijas ceļu: 4 māsu mezglus ceļā uz augšu. Ar tiem pārbaudītājs, jaucot, paceļas no lapas līdz saknei. Ja iznāk zināmā sakne, lapa pieder kokam.

---

6. 3. būvbloks: koki uz kokiem (hiperkoks)

16 vienreizējo atslēgu, protams, nepietiek. Tāpēc SLH-DSA krauj kokus vienu virs otra: koka sakne tiek parakstīta ar virs tā esošā koka WOTS+ atslēgu. Šo torni sauc par hiperkoku (hypertree).

SLH-DSA-SHA2-256f ir $d = 17$ slāņi, katrs ar augstumu 4:

Pašā apakšā tādējādi ir pieejamas

lapas. Augšējā koka sakni sauc par $\text{PK.root}$ — tā ir īstā publiskā atslēga.

Svarīgi: neviens šos kokus neaprēķina iepriekš. Visas slepenās vērtības pēc vajadzības tiek atvasinātas no slepenas sākuma vērtības $\text{SK.seed}$. Glabātas tiek tikai četras vērtības pa 32 baitiem katra:

Privāto atslēgu veido visas četras (128 baiti), publisko — tikai PK.seed un PK.root (64 baiti).

---

7. 4. būvbloks: mežs pret nejaušiem trāpījumiem (FORS)

Tagad īstā problēma: kā parakstītājs zina, kura no $2^{68}$ lapām vēl nav izmantota?

Vecāki uz jaucējfunkcijām balstīti algoritmi (XMSS, LMS) šim nolūkam uztur skaitītāju. To nekad nedrīkst atiestatīt — ne ar rezerves kopiju, ne ar otru serveri. Ja tas tomēr notiek, vienreizējā atslēga tiek izmantota divreiz, un algoritms ir uzlauzts. Šādus algoritmus sauc par stāvokli saturošiem.

SLH-DSA ir bezstāvokļa: lapa tiek pseidonejauši izvēlēta no paša ziņojuma. Tad var gadīties, ka divi ziņojumi trāpa vienā un tajā pašā lapā. Tāpēc pašā apakšā karājas nevis vienreizējs paraksts, bet dažreizējs paraksts: FORS (Forest of Random Subsets).

FORS sastāv no $k = 35$ maziem Merkle kokiem, katrā $2^a = 2^9 = 512$ lapas. Lapas ir slepenas nejaušas vērtības.

Parakstot ziņojuma jaucējvērtība tiek sadalīta 35 skaitļos pa 9 bitiem katrā. Katrs skaitlis „savā“ kokā izvēlas tieši vienu lapu. Paraksts katram kokam satur:

• šīs lapas slepeno vērtību
• tās autentifikācijas ceļu (9 mezgli)

Citam ziņojumam viltotājam būtu visos 35 kokos jātrāpa lapās, kuru noslēpumi jau ir atklāti. Pat ja viena un tā pati FORS instance izmantota dažas reizes, tas ir bezcerīgi.

---

8. Visa parakstīšanas gaita

1. Nejaušā komponente. No $\text{SK.prf}$, svaiga nejauša skaitļa un ziņojuma rodas 32 baitu vērtība $R$.
2. Ziņojuma jaucējvērtība.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Digesta 49 baiti tiek sadalīti: 40 baiti izvēlas 35 FORS lapas, atlikums nosaka, kurš koks (idx_tree) un kura lapa (idx_leaf) pašā hiperkoka apakšā tiek izmantoti.
3. FORS paraksts ziņojumam. No tā izriet FORS publiskā atslēga.
4. Hiperkoka paraksts šai FORS atslēgai: 17 WOTS+ paraksti, katrs ar autentifikācijas ceļu, slāni pa slānim līdz pat $\text{PK.root}$.

Gatavais paraksts ir vienkārši savirknējums:

---

9. Kāpēc paraksts ir 49 856 baitus liels

Ar SLH-DSA-SHA2-256f parametriem izmēru var precīzi pārrēķināt ($n = 32$ baiti katrai jaucējvērtībai):

Salīdzinājumam: Ed25519 paraksts aizņem 64 baitus, ML-DSA-87 — 4627 baitus. Izmērs ir cena par to, ka SLH-DSA iztiek ar neko citu kā jaucējfunkcijām.

---

10. Kā pārbauda pārlūkprogramma

Pārbaudīt SLH-DSA gadījumā nozīmē: pārjaukt.

1. No jauna aprēķināt digestu no $R$, publiskās atslēgas un ziņojuma.
2. No 35 atklātajām FORS lapām un to ceļiem aprēķināt 35 koku saknes un no tām — FORS publisko atslēgu.
3. Ar katru no 17 WOTS+ parakstiem pabeigt ķēžu jaukšanu, izveidot WOTS+ publisko atslēgu un pa ceļu pacelties līdz koka saknei.
4. Beigās jāiznāk tieši $\text{PK.root}$.

Tie ir daži tūkstoši jaucējfunkcijas izsaukumu — datoram sīkums. Pārlūkprogrammā pārbaude pie mums ilgst aptuveni 6 līdz 12 milisekundes.

---

11. Kas notiek, ja kāds izmaina datu ierakstu?

Ja izmainās kaut viens ziņojuma $M$ bits, digests izmainās pilnībā. Tad 35 skaitļi norāda uz citām FORS lapām, bet algoritms — uz citu vietu hiperkokā.

Atklātie noslēpumi vairs neatbilst: pārrēķinātās saknes atšķiras, un beigās neiznāk $\text{PK.root}$. Pārbaude neizdodas.

Lai tomēr izveidotu derīgu parakstu, uzbrucējam būtu jāzina noslēpumi, kas nekad nav publicēti — tātad jārēķina jaucējfunkcija atpakaļ.

---

12. Kāpēc tieši 256f?

FIPS 205 definē divpadsmit parametru kopas: divas jaucējfunkciju saimes (SHA-2 un SHAKE), trīs drošības līmeņus (128, 192, 256) un katram pa ātram („f“) un mazam („s“) variantam.

256 nozīmē NIST drošības kategoriju 5 — to pašu līmeni kā FALCON-1024 un ML-DSA-87.

„f“ mēs izvēlējāmies, jo uzņēmumi vienā piegājienā var izsniegt līdz 500 QR kodiem. Ar „s“ parakstīšana ilgtu vairāk nekā 20 minūtes, ar „f“ — mazāk nekā minūti. Toties paraksts ir lielāks — tā kā tas neatrodas QR kodā, tas ir paciešami.

SHA-2, nevis SHAKE, jo SHA-256 un SHA-512 praktiski jebkurā aparatūrā ir paātrināti.

---

13. Nejaušība parakstīšanā

FIPS 205 atļauj divus $R$ ģenerēšanas veidus:

• deterministisku: vienāds ziņojums, vienāds paraksts
• randomizētu („hedged“): tiek iejaukts svaigs nejaušs skaitlis

Mēs izmantojam randomizēto variantu. Tāpēc divi viena un tā paša ziņojuma paraksti izskatās atšķirīgi — abi ir derīgi. Tas apgrūtina uzbrukumus, kas apvieno mērījumus ierīcē (strāvas patēriņu, laiku) ar atkārtotiem parakstiem.

---

14. Ko McGesund ar to konkrēti dara

Līmenis. PQ-Dual-Diversified ir pieejams tarifos Novērtējumi Premium un Signāli Premium. Tad QR kods nes trīs parakstus:

Parakstīšana. Viens SLH-DSA paraksts prasa aptuveni ceturtdaļsekundi skaitļošanas laika. Lai serveris pa to laiku paliktu sasniedzams visiem pārējiem, rēķina atsevišķi fona pavedieni.

Pārbaude. Lasītāja pārlūkprogramma ielādē abus zīmogus un pārbauda tos ar to pašu WASM moduli kā visus pārējos PQ parakstus. Mēs piegādājam datus, rēķināts tiek apmeklētāja ierīcē.

Salīdzināšana ar NIST. Mūsu modulis iztur oficiālos NIST testa vektorus algoritmam SLH-DSA-SHA2-256f: no NIST sākuma vērtībām baitu pa baitam rodas tās pašas atslēgas, un visi apzināti manipulētie paraksti tiek noraidīti. To Jūs varat paši pārbaudīt pārlūkprogrammā NIST testa lapā.

Laika enkurs. Tāpat kā visām atslēgām, SLH-DSA atslēgas nospiedums caur OpenTimestamps tiek noenkurots Bitcoin blokā.

---

15. SLH-DSA, ML-DSA un FALCON blakus

Īsi sakot: SLH-DSA ir lēnākais un lielākais no trim algoritmiem — un konservatīvākais. Tas nepaļaujas ne uz ko tādu, ko jau tāpat nepieņemtu jebkurš cits paraksts: drošu jaucējfunkciju.

---

16. Viens teikums līdzņemšanai

Kam pieder slepenā sākuma vērtība, tas paraksta ceturtdaļsekundē. Kam tās nav, tam būtu jārēķina SHA-256 vai SHA-512 atpakaļ — arī ar kvantu datoru.

Atsauksmes lasītājam tas nozīmē: pat ja kādreiz kristu visi režģu algoritmi, šis paraksts paliek pārbaudāms. Viņam mums nav jātic. Viņš var pārrēķināt.