SLH-DSA, обяснен математически

1. За какво става дума

В McGesund клиентите с тарифите Оценки Premium и Сигнали Premium могат да изберат нивото на подпис PQ-Dual-Diversified. Тогава всеки QR код носи освен класическия подпис Ed25519 и два квантово устойчиви подписа: ML-DSA-87 и SLH-DSA-SHA2-256f.

Тази статия обяснява втория. Той е устроен различно от всичко друго, което използваме.

SLH-DSA не е криптиране. Съдържанието остава публично четимо. SLH-DSA доказва произход и цялост — както всеки цифров подпис.

SLH-DSA означава Stateless Hash-Based Digital Signature Algorithm. Разработен е от SPHINCS+ и през 2024 г. е стандартизиран като FIPS 205. Името вече издава особеното: схемата използва само хеш функции. Никакви решетки, никакви елиптични криви, никакви големи прости числа.

---

2. Какво точно се подписва?

В McGesund SLH-DSA подписва същия набор от данни, който покрива и подписът Ed25519 в QR кода: полезния товар на QR кода. Той съдържа, наред с другото, към коя фирма принадлежи кодът (fid), от какъв вид е (typ), кога е издаден (iat) и до кога е валиден (exp) — като компактно кодирана последователност от байтове (CBOR).

Тази последователност от байтове е нашето съобщение $M$. Ако някой впоследствие промени дори един-единствен бит, нито един от подписите вече не пасва.

Подписът SLH-DSA не се намира в самия QR код. С около 49 KB той е твърде голям за това. Съхранява се като отделен „печат“ към записа на QR кода в бекенда на McGesund и се зарежда в браузъра при щракване върху „Проверка на автентичността“.

---

3. Защо схема, изградена само от хеш функции?

Всяка схема за подпис почива на задача, която без тайния ключ е практически нерешима:

Ed25519 би бил разбит от голям квантов компютър. FALCON и ML-DSA се смятат за квантово устойчиви — но и двата се опират на решетъчни задачи. Ако един ден бъде открита фундаментална атака срещу решетките, и двата биха били засегнати едновременно.

SLH-DSA, напротив, има нужда само хеш функцията да прави онова, за което е създадена:

Това е най-дълго и най-задълбочено изследваното допускане в цялата криптография. Дори квантов компютър помага тук само ограничено: алгоритъмът на Гроувър намалява наполовина битовете на сигурност. Затова вариантът 256 използва хеш стойности с $n = 32$ байта $= 256$ бита — след Гроувър остават все още 128 бита.

Точно затова нивото се нарича Diversified: ML-DSA (решетки) и SLH-DSA (хеш) произхождат от различни математически семейства. Ако едното падне, другото продължава да носи.

---

4. Градивен елемент 1: подписване с хеш вериги (WOTS+)

Основната идея е изненадващо проста. Започваме с една-единствена цифра.

Вземете тайна случайна стойност $s$ и я хеширайте отново и отново:

Краят на веригата, $p$, се публикува. Това е публичният ключ за тази една цифра.

За да се подпише цифра $d$ между 0 и 15, се разкрива стойността на веригата на позиция $d$:

Който иска да провери, хешира $\sigma$ още $15 - d$ пъти. Ако се получи точно $p$, подписът е истински:

Мини пример

Подписваме цифрата $d = 6$:

• Подписващият публикува $\sigma = H^6(s)$.
• Проверяващият изчислява $H^{9}(\sigma) = H^{15}(s)$ и сравнява с $p$. Съвпада.

Фалшификатор, който е видял $\sigma$, може без усилие да изчисли от нея $H^7(s)$, $H^8(s)$ и т.н. — т.е. да подпише по-големи цифри. По-малки не може — за целта би трябвало да хешира назад.

Контролната сума срещу „броене нагоре“

За да не може никой просто да увеличава цифри, допълнително се подписва контролна сума:

Ако фалшификаторът увеличи цифра от съобщението, $C$ става по-малка — а за това той би трябвало да смята назад във веригата на контролната сума. Така и двете посоки са блокирани.

Пренесено върху цяла хеш стойност

Хеш стойност от 32 байта има 64 цифри в основа 16. Към тях се добавят 3 цифри контролна сума:

Такъв подпис се нарича WOTS+ (Winternitz One-Time Signature). Голямата му уловка е в името: One-Time — еднократен. Който подпише две различни съобщения с един и същ ключ, разкрива толкова много стойности от веригите, че фалшификациите стават възможни.

---

5. Градивен елемент 2: много еднократни ключове под един покрив (дърво на Меркъл)

Ако всеки ключ може да се използва само веднъж, нужни са ни много от тях — но искаме да публикуваме само един публичен ключ.

Решението е дърво на Меркъл: публичните ключове на $2^{h'}$ двойки WOTS+ образуват листата. Всеки два съседа се хешират заедно, резултатите — отново по двойки, докато най-горе остане един-единствен корен.

При SLH-DSA-SHA2-256f всяко дърво има височина $h' = 4$, т.е. $2^4 = 16$ листа.

За да се покаже, че определено листо принадлежи на дървото, се предоставя пътят за автентикация: 4-те съседни възела по пътя нагоре. С тях проверяващият хешира от листото до корена. Ако се получи познатият корен, листото принадлежи на дървото.

---

6. Градивен елемент 3: дървета върху дървета (хипердърво)

16 еднократни ключа, разбира се, не стигат. Затова SLH-DSA подрежда дърветата едно върху друго: коренът на едно дърво се подписва с ключ WOTS+ на дървото над него. Тази кула се нарича хипердърво.

При SLH-DSA-SHA2-256f има $d = 17$ слоя с височина 4 всеки:

Най-отдолу така са на разположение

листа. Коренът на най-горното дърво се нарича $\text{PK.root}$ — той е същинският публичен ключ.

Важно: никой не изчислява тези дървета предварително. Всички тайни стойности се извеждат при нужда от тайна начална стойност $\text{SK.seed}$. Съхраняват се само четири стойности по 32 байта:

Частният ключ се състои от всичките четири (128 байта), публичният — само от PK.seed и PK.root (64 байта).

---

7. Градивен елемент 4: гора срещу случайни попадения (FORS)

Сега истинският проблем: откъде подписващият знае кое от $2^{68}$-те листа е още неизползвано?

По-старите схеми, основани на хеш (XMSS, LMS), водят за целта брояч. Той никога не бива да бъде нулиран — нито от резервно копие, нито от втори сървър. Ако това все пак се случи, един еднократен ключ се използва два пъти и схемата е разбита. Такива схеми се наричат със състояние.

SLH-DSA е без състояние: листото се избира псевдослучайно от самото съобщение. Тогава може да се случи две съобщения да попаднат на едно и също листо. Затова най-отдолу виси не еднократен подпис, а подпис за малко на брой употреби: FORS (Forest of Random Subsets).

FORS се състои от $k = 35$ малки дървета на Меркъл с по $2^a = 2^9 = 512$ листа. Листата са тайни случайни стойности.

За подписване хешът на съобщението се разделя на 35 числа по 9 бита. Всяко число избира в „своето“ дърво точно едно листо. Подписът съдържа за всяко дърво:

• тайната стойност на това листо
• неговия път за автентикация (9 възела)

За друго съобщение фалшификаторът би трябвало във всичките 35 дървета да уцели листа, чиито тайни вече са разкрити. Дори ако една и съща инстанция на FORS е използвана няколко пъти, това е безнадеждно.

---

8. Целият процес на подписване

1. Случаен компонент. От $\text{SK.prf}$, свежо случайно число и съобщението се получава 32-байтова стойност $R$.
2. Хеш на съобщението.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   49-те байта на дайджеста се разпределят: 40 байта избират 35-те листа на FORS, а останалото определя кое дърво (idx_tree) и кое листо (idx_leaf) най-отдолу в хипердървото се използват.
3. Подпис FORS върху съобщението. От него се получава публичен ключ на FORS.
4. Подпис на хипердървото върху този ключ на FORS: 17 подписа WOTS+, всеки с път за автентикация, слой по слой чак до $\text{PK.root}$.

Готовият подпис е просто последователното им свързване:

---

9. Защо подписът е голям 49 856 байта

С параметрите на SLH-DSA-SHA2-256f размерът може да се пресметне точно ($n = 32$ байта на хеш стойност):

За сравнение: подписът Ed25519 е 64 байта, ML-DSA-87 — 4627 байта. Размерът е цената за това, че SLH-DSA се справя единствено с хеш функции.

---

10. Как проверява браузърът

При SLH-DSA проверката означава: повторно хеширане.

1. Дайджестът се изчислява наново от $R$, публичния ключ и съобщението.
2. От 35-те разкрити листа на FORS и техните пътища се изчисляват 35-те корена на дърветата, а от тях — публичният ключ на FORS.
3. С всеки от 17-те подписа WOTS+ веригите се дохешират до края, образува се публичният ключ WOTS+ и по пътя се хешира нагоре до корена на дървото.
4. Накрая трябва да се получи точно $\text{PK.root}$.

Това са няколко хиляди извиквания на хеш функцията — дреболия за един компютър. В браузъра проверката при нас отнема около 6 до 12 милисекунди.

---

11. Какво става, ако някой промени набора от данни?

Ако се промени дори един бит от съобщението $M$, дайджестът се променя изцяло. Така 35-те числа сочат към други листа на FORS, а схемата — към друго място в хипердървото.

Разкритите тайни вече не пасват: преизчислените корени се различават и накрая не се получава $\text{PK.root}$. Проверката е неуспешна.

За да състави въпреки това валиден подпис, нападателят би трябвало да знае тайни, които никога не са били публикувани — т.е. да изчисли хеш функция назад.

---

12. Защо точно 256f?

FIPS 205 определя дванадесет набора от параметри: две хеш семейства (SHA-2 и SHAKE), три нива на сигурност (128, 192, 256) и за всяко по един бърз („f“) и един малък („s“) вариант.

256 означава категория 5 за сигурност на NIST — същото ниво като FALCON-1024 и ML-DSA-87.

„f“ избрахме, защото фирмите могат да издават до 500 QR кода наведнъж. С „s“ подписването би отнело над 20 минути, с „f“ — под минута. За сметка на това подписът е по-голям — но понеже не е в QR кода, това е поносимо.

SHA-2 вместо SHAKE, защото SHA-256 и SHA-512 са хардуерно ускорени на практически всяко устройство.

---

13. Случайност при подписването

FIPS 205 допуска два начина за генериране на $R$:

• детерминистично: едно и също съобщение, един и същ подпис
• рандомизирано („hedged“): включва се и свежо случайно число

Ние използваме рандомизирания вариант. Затова два подписа върху едно и също съобщение изглеждат различно — и двата са валидни. Това затруднява атаки, които съчетават измервания на устройството (консумация на ток, време) с повторни подписвания.

---

14. Какво прави McGesund конкретно с това

Нивото. PQ-Dual-Diversified се предлага в Оценки Premium и Сигнали Premium. Тогава един QR код носи три подписа:

Подписването. Един подпис SLH-DSA струва около четвърт секунда изчислително време. За да остане сървърът междувременно достъпен за всички останали, изчисленията се извършват в отделни фонови нишки.

Проверката. Браузърът на читателя зарежда двата печата и ги проверява със същия модул WASM като всички останали PQ подписи. Ние доставяме данните; пресмятането става на устройството на посетителя.

Сверката с NIST. Нашият модул преминава официалните тестови вектори на NIST за SLH-DSA-SHA2-256f: от началните стойности на NIST се получават байт по байт същите ключове, а всички умишлено манипулирани подписи биват отхвърлени. Можете сами да проверите това в браузъра на тестовата страница на NIST.

Времевата котва. Както при всички ключове, отпечатъкът на ключа SLH-DSA се закотвя чрез OpenTimestamps в блок на Bitcoin.

---

15. SLH-DSA, ML-DSA и FALCON едно до друго

Накратко: SLH-DSA е най-бавната и най-обемната от трите схеми — и най-консервативната. Тя не разчита на нищо, което всеки друг подпис и без това не предполага: сигурна хеш функция.

---

16. Едно изречение за накрая

Който притежава тайната начална стойност, подписва за четвърт секунда. Който не я притежава, би трябвало да изчисли SHA-256 или SHA-512 назад — дори с квантов компютър.

За читателя на един отзив това означава: дори ако един ден всички решетъчни схеми паднат, този подпис остава проверим. Той не трябва да ни вярва. Може да провери сам.