SLH-DSA wyjaśniony matematycznie

1. O co tutaj chodzi

W McGesund klienci w taryfach Opinie Premium i Sygnały Premium mogą wybrać poziom podpisu PQ-Dual-Diversified. Wtedy każdy kod QR obok klasycznego podpisu Ed25519 niesie dwa podpisy odporne na ataki kwantowe: ML-DSA-87 i SLH-DSA-SHA2-256f.

Ten artykuł wyjaśnia drugi z nich. Jest zbudowany inaczej niż wszystko inne, czego używamy.

SLH-DSA nie jest szyfrowaniem. Treść pozostaje publicznie czytelna. SLH-DSA dowodzi pochodzenia i nienaruszalności — jak każdy podpis cyfrowy.

SLH-DSA to w pełnym brzmieniu Stateless Hash-Based Digital Signature Algorithm. Powstał na bazie SPHINCS+ i w 2024 roku został znormalizowany jako FIPS 205. Już nazwa zdradza, co w nim szczególnego: metoda wykorzystuje wyłącznie funkcje skrótu. Żadnych krat, żadnych krzywych eliptycznych, żadnych dużych liczb pierwszych.

---

2. Co dokładnie jest podpisywane?

W McGesund SLH-DSA podpisuje ten sam zestaw danych, który obejmuje też podpis Ed25519 w kodzie QR: payload kodu QR. Zawiera on między innymi informację, do jakiej firmy należy kod (fid), jakiego jest rodzaju (typ), kiedy został wystawiony (iat) i do kiedy jest ważny (exp) — w postaci kompaktowo zakodowanego ciągu bajtów (CBOR).

Ten ciąg bajtów jest naszą wiadomością $M$. Jeśli ktoś później zmieni choćby jeden bit, żaden z podpisów już nie pasuje.

Podpis SLH-DSA nie jest zapisany w samym kodzie QR. Przy około 49 KB jest na to o wiele za duży. Leży jako osobny „stempel” przy rekordzie QR w backendzie McGesund i jest ładowany do przeglądarki po kliknięciu „Sprawdź autentyczność”.

---

3. Dlaczego metoda oparta wyłącznie na funkcjach skrótu?

Każda metoda podpisu opiera się na zadaniu, którego bez tajnego klucza praktycznie nie da się rozwiązać:

Ed25519 złamałby duży komputer kwantowy. FALCON i ML-DSA uchodzą za odporne na ataki kwantowe — ale oba opierają się na problemach kratowych. Gdyby pewnego dnia odkryto fundamentalny atak na kraty, dotknąłby on obu jednocześnie.

SLH-DSA potrzebuje natomiast tylko tego, by funkcja skrótu robiła to, do czego została stworzona:

To najdłużej i najgruntowniej zbadane założenie w całej kryptografii. Nawet komputer kwantowy pomaga tu tylko w ograniczonym stopniu: algorytm Grovera zmniejsza o połowę liczbę bitów bezpieczeństwa. Dlatego wariant 256 używa wartości skrótu o długości $n = 32$ bajty $= 256$ bitów — po Groverze wciąż zostaje 128 bitów.

Właśnie dlatego poziom nazywa się Diversified: ML-DSA (kraty) i SLH-DSA (skróty) pochodzą z różnych rodzin matematycznych. Jeśli jedna upadnie, druga nadal niesie dowód.

---

4. Element 1: podpisywanie łańcuchami skrótów (WOTS+)

Podstawowa idea jest zaskakująco prosta. Zaczynamy od jednej cyfry.

Weź tajną wartość losową $s$ i haszuj ją raz za razem:

Koniec łańcucha, $p$, zostaje opublikowany. To klucz publiczny dla tej jednej cyfry.

Aby podpisać cyfrę $d$ z przedziału od 0 do 15, ujawnia się wartość łańcucha na pozycji $d$:

Kto chce sprawdzić podpis, haszuje $\sigma$ jeszcze $15 - d$ razy. Jeśli wyjdzie dokładnie $p$, podpis jest prawdziwy:

Mini-przykład

Podpisujemy cyfrę $d = 6$:

• Podpisujący publikuje $\sigma = H^6(s)$.
• Weryfikujący oblicza $H^{9}(\sigma) = H^{15}(s)$ i porównuje z $p$. Pasuje.

Fałszerz, który widział $\sigma$, może z niej bez trudu obliczyć $H^7(s)$, $H^8(s)$ itd. — czyli podpisać większe cyfry. Mniejszych nie może, bo musiałby haszować wstecz.

Suma kontrolna przeciw „podbijaniu”

Aby nikt nie mógł po prostu zwiększać cyfr, podpisuje się dodatkowo sumę kontrolną:

Jeśli fałszerz zwiększy jakąś cyfrę wiadomości, $C$ staje się mniejsza — a do tego musiałby liczyć wstecz w łańcuchu sumy kontrolnej. Oba kierunki są tym samym zablokowane.

W przeliczeniu na wartość skrótu

32-bajtowa wartość skrótu ma 64 cyfry przy podstawie 16. Do tego dochodzą 3 cyfry sumy kontrolnej:

Taki podpis nazywa się WOTS+ (Winternitz One-Time Signature). Jego wielki haczyk tkwi w nazwie: One-Time, czyli jednorazowy. Kto tym samym kluczem podpisze dwie różne wiadomości, zdradza tyle wartości łańcuchów, że fałszerstwa stają się możliwe.

---

5. Element 2: wiele kluczy jednorazowych pod jednym dachem (drzewo Merkle'a)

Jeśli każdego klucza wolno użyć tylko raz, potrzeba ich bardzo wielu — a chce się opublikować tylko jeden klucz publiczny.

Rozwiązaniem jest drzewo Merkle'a: klucze publiczne $2^{h'}$ par WOTS+ tworzą liście. Każdych dwóch sąsiadów haszuje się razem, wyniki znowu parami, aż na górze zostaje jeden korzeń.

W SLH-DSA-SHA2-256f każde drzewo ma wysokość $h' = 4$, czyli $2^4 = 16$ liści.

Aby pokazać, że dany liść należy do drzewa, dostarcza się ścieżkę uwierzytelniania: 4 węzły rodzeństwa na drodze w górę. Weryfikujący haszuje się z nimi od liścia aż do korzenia. Jeśli wyjdzie znany korzeń, liść należy do drzewa.

---

6. Element 3: drzewa na drzewach (hiperdrzewo)

16 kluczy jednorazowych to oczywiście za mało. Dlatego SLH-DSA układa drzewa jedno na drugim: korzeń drzewa zostaje podpisany kluczem WOTS+ drzewa powyżej. Ta wieża nazywa się hiperdrzewem.

W SLH-DSA-SHA2-256f jest $d = 17$ warstw, każda o wysokości 4:

Na samym dole jest więc do dyspozycji

liści. Korzeń najwyższego drzewa nazywa się $\text{PK.root}$ — to on jest właściwym kluczem publicznym.

Ważne: nikt nie oblicza tych drzew z góry. Wszystkie tajne wartości są w razie potrzeby wyprowadzane z tajnego seeda $\text{SK.seed}$. Zapisywane są tylko cztery wartości po 32 bajty:

Klucz prywatny składa się ze wszystkich czterech (128 bajtów), publiczny tylko z PK.seed i PK.root (64 bajty).

---

7. Element 4: las przeciw przypadkowym trafieniom (FORS)

Teraz właściwy problem: skąd podpisujący wie, który z $2^{68}$ liści jest jeszcze nieużyty?

Starsze metody oparte na skrótach (XMSS, LMS) prowadzą w tym celu licznik. Nie wolno go nigdy cofnąć — ani przez kopię zapasową, ani przez drugi serwer. Jeśli jednak do tego dojdzie, klucz jednorazowy zostaje użyty dwukrotnie i metoda jest złamana. Takie metody nazywa się stanowymi.

SLH-DSA jest bezstanowy: liść wybierany jest pseudolosowo na podstawie samej wiadomości. Może się wtedy zdarzyć, że dwie wiadomości trafią w ten sam liść. Dlatego na samym dole nie wisi podpis jednorazowy, lecz podpis kilkukrotny: FORS (Forest of Random Subsets).

FORS składa się z $k = 35$ małych drzew Merkle'a, każde z $2^a = 2^9 = 512$ liśćmi. Liście są tajnymi wartościami losowymi.

Przy podpisywaniu skrót wiadomości zostaje rozłożony na 35 liczb po 9 bitów. Każda liczba wybiera w „swoim” drzewie dokładnie jeden liść. Podpis zawiera dla każdego drzewa:

• tajną wartość tego liścia
• jego ścieżkę uwierzytelniania (9 węzłów)

Fałszerz musiałby dla innej wiadomości trafić we wszystkich 35 drzewach w liście, których sekrety zostały już ujawnione. Nawet jeśli ta sama instancja FORS została użyta kilka razy, jest to beznadziejne.

---

8. Cały przebieg podpisywania

1. Składnik losowy. Z $\text{SK.prf}$, świeżej liczby losowej i wiadomości powstaje 32-bajtowa wartość $R$.
2. Skrót wiadomości.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49 bajtów digestu zostaje podzielonych: 40 bajtów wybiera 35 liści FORS, reszta określa, które drzewo (idx_tree) i który liść (idx_leaf) na samym dole hiperdrzewa zostanie użyty.
3. Podpis FORS nad wiadomością. Wynika z niego klucz publiczny FORS.
4. Podpis hiperdrzewa nad tym kluczem FORS: 17 podpisów WOTS+, każdy ze ścieżką uwierzytelniania, warstwa po warstwie aż do $\text{PK.root}$.

Gotowy podpis to po prostu złożenie:

---

9. Dlaczego podpis ma 49 856 bajtów

Przy parametrach SLH-DSA-SHA2-256f rozmiar można dokładnie przeliczyć ($n = 32$ bajty na wartość skrótu):

Dla porównania: podpis Ed25519 ma 64 bajty, ML-DSA-87 ma 4627 bajtów. Rozmiar to cena za to, że SLH-DSA radzi sobie wyłącznie przy użyciu funkcji skrótu.

---

10. Jak sprawdza przeglądarka

Weryfikacja w SLH-DSA oznacza: ponowne haszowanie.

1. Obliczyć na nowo digest z $R$, klucza publicznego i wiadomości.
2. Z 35 ujawnionych liści FORS i ich ścieżek obliczyć 35 korzeni drzew, a z nich klucz publiczny FORS.
3. Przy każdym z 17 podpisów WOTS+ dohaszować łańcuchy do końca, utworzyć klucz publiczny WOTS+ i po ścieżce dohaszować się do korzenia drzewa.
4. Na końcu musi wyjść dokładnie $\text{PK.root}$.

To kilka tysięcy wywołań funkcji skrótu — dla komputera drobnostka. W przeglądarce weryfikacja trwa u nas około 6 do 12 milisekund.

---

11. Co się dzieje, gdy ktoś zmieni dane?

Jeśli zmieni się choćby jeden bit wiadomości $M$, digest zmienia się całkowicie. Wtedy 35 liczb wskazuje na inne liście FORS, a metoda — na inne miejsce w hiperdrzewie.

Ujawnione sekrety już nie pasują: przeliczone korzenie się różnią i na końcu nie wychodzi $\text{PK.root}$. Weryfikacja kończy się niepowodzeniem.

Aby mimo to zbudować ważny podpis, atakujący musiałby znać sekrety, które nigdy nie zostały opublikowane — czyli odwrócić funkcję skrótu.

---

12. Dlaczego właśnie 256f?

FIPS 205 definiuje dwanaście zestawów parametrów: dwie rodziny funkcji skrótu (SHA-2 i SHAKE), trzy poziomy bezpieczeństwa (128, 192, 256) i dla każdego wariant szybki („f”) oraz mały („s”).

256 oznacza kategorię bezpieczeństwa NIST 5 — ten sam poziom co FALCON-1024 i ML-DSA-87.

„f” wybraliśmy, ponieważ firmy mogą wystawić do 500 kodów QR za jednym razem. Z „s” podpisywanie trwałoby ponad 20 minut, z „f” poniżej minuty. W zamian podpis jest większy — ponieważ nie tkwi w kodzie QR, jest to do przyjęcia.

SHA-2 zamiast SHAKE, ponieważ SHA-256 i SHA-512 są sprzętowo przyspieszane praktycznie na każdym urządzeniu.

---

13. Losowość przy podpisywaniu

FIPS 205 dopuszcza dwa sposoby generowania $R$:

• deterministyczny: ta sama wiadomość, ten sam podpis
• randomizowany („hedged”): dodatkowo wchodzi świeża liczba losowa

Używamy wariantu randomizowanego. Dwa podpisy nad tą samą wiadomością wyglądają więc różnie — oba są ważne. Utrudnia to ataki, które łączą pomiary na urządzeniu (pobór prądu, czas) z wielokrotnymi podpisami.

---

14. Co konkretnie robi z tym McGesund

Poziom. PQ-Dual-Diversified jest dostępny w taryfach Opinie Premium i Sygnały Premium. Kod QR niesie wtedy trzy podpisy:

Podpisywanie. Podpis SLH-DSA kosztuje około ćwierć sekundy czasu obliczeniowego. Aby serwer w tym czasie pozostawał dostępny dla wszystkich innych, obliczenia wykonują osobne wątki w tle.

Weryfikacja. Przeglądarka czytelnika ładuje oba stemple i sprawdza je tym samym modułem WASM co wszystkie inne podpisy PQ. My dostarczamy dane, obliczenia odbywają się na urządzeniu odwiedzającego.

Zgodność z NIST. Nasz moduł przechodzi oficjalne wektory testowe NIST dla SLH-DSA-SHA2-256f: z seedów NIST powstają bajt w bajt te same klucze, a wszystkie celowo zmanipulowane podpisy są odrzucane. Mogą to Państwo sami sprawdzić w przeglądarce na stronie testowej NIST.

Kotwica czasu. Jak w przypadku wszystkich kluczy, odcisk klucza SLH-DSA zostaje zakotwiczony przez OpenTimestamps w bloku Bitcoina.

---

15. SLH-DSA, ML-DSA i FALCON obok siebie

Krótko mówiąc: SLH-DSA jest najwolniejszą i największą z trzech metod — i najbardziej konserwatywną. Nie opiera się na niczym, czego i tak nie zakłada już każdy inny podpis: na bezpiecznej funkcji skrótu.

---

16. Jedno zdanie na wynos

Kto posiada tajny seed, podpisuje w ćwierć sekundy. Kto go nie posiada, musiałby odwrócić SHA-256 lub SHA-512 — także komputerem kwantowym.

Dla czytelnika opinii oznacza to: nawet gdyby pewnego dnia upadły wszystkie metody kratowe, ten podpis pozostaje sprawdzalny. Nie musi nam wierzyć. Może przeliczyć.