Kryptografie odolná kvantovým počítačům - digitální podpis

V minulém článku byly rozebírané algoritmy pro domluvu na klíčích. V tomto se chci zaměřit na digitální podpisy, které jsou v současnosti nejenom jednou z forem ochrany integrity, ale využívají se i pro autentizaci nebo jako důkaz vůle. Práce s těmito podpisy je u klasických algoritmů jako jsou DSA, ECDSA/EdDSA a RSA dobře pochopitelné. Ve zkratce jde o tvorbu hashe textu, která je následně zašifrována daným algoritmem. Příjemce pak tuto hodnotu dešifruje a ověří, zda hash souhlasí. Uvedený postup platí pro RSA, u DSA/ECDSA/EdDSA je odlišný. Pro zjednodušení lze s touto představou počítat. Jaká je ale situace u podpisů pomocí kvantově odolných algoritmů. Následující článek není matematickým popisem, ale pokusem o vysvětlení principů, proto se opět uchyluje ke zjednušením a příměrům.

Merklovy stromy

Jedná se o stromy hashí, nikoliv okrasné dřeviny. Tento strom roste od listů, kde každé dva listy se zahashují a vznikne větvička. Následně se zahashují dvě větvičky a vznikne větev ... a takto to pokračuje až do definované hloubky. Posledním záznamem je kořen. Působí to podivně, ale Merklovy stromy se léta používají například v některých kryptoměnách. Používají se i na dalších místech, třeba v pamětech počítačů jako kontrolní mechanismus, který je rychlejší než ECC (v tomto případě se jedná o Error Correction Code, nikoliv Eliptic Curve Cryptography). A dalo by se pokračovat.

WOTS podpisy

Jedním ze základních stavebních kamenů kvantově odolných kvantových algoritmů je v současnosti takzvaný WOTS podpis (Winternitz One-Time Signature). Je postaven nad hash funkcemi, jeho princip spočívá v opětovném hashování nějakých dat. V modelovém příkladu bude použit jednorázový podpis a celá situace je značně zjednodušena.
Na začátku vygeneruji privátní klíč, který se sestává z několika bloků dat. Každý blok dat má šířku výstupu odpovídající šířce hash funkce. V tomto případě bude příkladem SHA256 s šířkou bloku 32B. Protože i podepisovaný text bude mít tuto šířku výstupu hash funkce, musíme mít odpovídající počet, tedy 32 bloků. Na základě těchto nastavení bude každý jeden blok opakovaně hashován. Po 256 hashováních každého bloku je vytvořen veřejný klíč. Jak ale vytvořit a ověřit podpis?
Když spočítáme hash textu, každý bajt určuje kolikrát budeme hashovat privátní klíč (vždy jeden z 32 bloků). Jakmile je vytvořen celý podpis (32x32B=1024B), můžeme ho připojit k dokumentu. Dle současných možností neumíme zjistit, z jakých dat se hash počítal. Na druhou stranu ale můžeme vzít hash textu a zjistit podle rozdílu hodnoty daného bajtu, kolikrát ještě musíme daný blok hashovat. A pokud výsledek odpovídá veřejnému klíči, je podpis v pořádku. Problémem je pouze velikost. Privátní klíč i veřejný klíč má za těchto podmínek velikost 1KB. Pro každý B zprávy jsme použili jeden 32B řetězec. Na druhou stranu, můžeme jako čítač použít stejně dobře libovolný jiný počet bitů. Dle současných poznatků je tak tento mechanismus bezpečný.
U schémat založených na stromech hashí se používá buď klasický WOTS podpis, nebo WOTS+. Oba tyto podpisy jsou definované v RFC, ale důležitý je rozdíl. WOTS je pomalejší a má větší klíče, s tím samozřejmě i podpisy. WOTS+ má klíče menší, je rychlejší a navíc chrání proti některým typům útoku na WOTS. Ochrana je v tomto případě zajištěna maskováním výstupů mezi jednotlivými koly.

Stavové a bezstavové digitální podpisy

Digitální podpisy pomocí kvantově odolných algoritmů mohou být postaveny nad různými principy a jejich kombinacemi. Dnes jsou široce akceptované mřížkové algoritmy a algoritmy využívající hash funkce. Na rozdíl od klasické asymetrické kryptografie se v této oblasti objevila výrazná změna. A s tou je nutné počítat už v návrhu systému. Jedná se o problém stavových a bezstavových podpisů. Co to vlastně znamená?
Stavové podpisy jsou skupinou algoritmů, které potřebují už při návrhu definovat, kolikrát je možné je použít. Tím se odlišují od prostředků používaných v současnosti a vytváří problém s údržbou. Vlastník klíčového materiálu musí udržovat přehled o počtu použití. S každým podpisem se klíč mění, přesněji používá se jiná jeho část. A pokud by klíč byl použit vícekrát, má útočník možnost získat privátní klíč a kompletně kompromitovat celou historii podpisů.
Pro stavové algoritmy LMS, XMSS a XMSSMT je možné počet podpisů zvolit. Uvedená schémata jsou založena na stromu hashí a tyto stromy mají jednoznačnou strukturu. Struktura je pro počet podpisů, přesněji klíčů, extrémně důležitá. Strom má určitou hloubku (h) a v případě vícevrstevných stromů (XMSMT) má ještě určitý počet vrstev (d). Protože se jedná o binární strom, počet podpisů odpovídá číslu 2^h. Pokud se jedná o vícevrstevnou strukturu, tak počet podpisů odpovídá 2^h*d. jsou stavové stromy určeny pouze pro následující algoritmy, založené na stromu hashí:

• LMS - Leighton-Micali Signature (Merkle tree)
• XMSS - eXtended Merkle Signature Scheme
• XMSSMT - XMSS Multi-Tree – hierarchie Merklových stromů

• ML-DSA (původně Krystal Dilithium, v současnosti Module Lattice DSA dle FIPS 204)
• SLH-DSA (původně SPHINCS+, v současnosti Stateless Hash-Based DSA dle FIPS 205)
• FN-DSA (původně Falcon, v současnosti Fast Fourier Transform-based NTRU DSA dle FIPS 206)

ML-DSA

Tento algoritmus používá podobný princip, jako klasické asymetrické podpisové algoritmy. Přesněji, podobný princip jako takzvaný Schnorrův podpis, byl jím přímo inspirován. V některých případech se jako princip podpisu zmiňuje Fiat-Shamir, který je k danému algoritmu ještě bližší. Schnorrův podpis jeho princip používá také, ale odlišným způsobem. Jak ale probíhá podepisování? Díky privátnímu klíči a náhodné výzvě dojde k tvorbě pracovního výstup, který se následně použije k tvorbě dvou částí podpisu. Jedna z hodnot obsahuje podepisovaná data a pracovní hodnotu, druhá obsahuje náhodný vstup (použitý i pro tvorbu pracovní hodnoty) přičtený k násobku hashe a tajného klíče. A obráceně, pokud chce příjemce data ověřit, pomocí veřejného klíče provede nad uvedenými částmi podpisu sérii matematických operací. Tím získá tajnou hodnotu, kterou spojí s podepsanými daty (bez podpisu) a zkusí je hashovat. Pokud informace v podpisu a výsledek operace je stejný, je v pořádku i podpis.Ale takový popis asi málokomu co řekne.
Pokud se mám vyhnout jakémukoliv jinému popisu, lze algoritmus popsat ještě výrazně jednodušeji, ale s podstatně nižší přesností. Můžeme si představit sál, který je celý vydlážděn stejnými dlaždicemi obdélníkového tvaru. Jedná se tedy o dvourozměrný prostor, v reálné situaci bude těchto rozměrů podstatně více. V případě snahy o podpis si vyberu jednu z dlaždic, kterou označím podpisem. Zároveň spočítám dvě hodoty, které jsou součástí podpisu, ale jsou upravené pomocí privátního klíče. Pokud chce příjemce ověřit podpis, musí nad ním provést operace pomocí veřejného klíče. Tím zjistí souřadnice podpisu. Jedná se o hodně volnou analogii, ale cílem tohoto článku není detailní popis algoritmu.
Uvedený algoritmus je extrémně rychlý, ale diskutuje se jeho citlivost na zvolené vstupy. Stejne jako u klasických algoritmů musí být zajištěna ochrana před použitím dvou stejných hodnot náhody pro různé texty. V takovém případě bylo možné snadno řešením kvadratické rovnice dospět k privátnímu klíči. Bohužel se ukázalo, že použití kvalitního generátoru náhodnosti nemusí být dostatečné. Za určitých specifických podmínek mohou "prosakovat" některé bity klíče do podpisu. Tento problém byl prokázán už pro algoritmus ECDSA a tuto znalost je možné použít i k útoku. Stejně tak je možné znalosti vstupů náhodnosti použít pro napadení ML-DSA.

SLH-DSA

V tomto případě se jedná o kombinaci FORS (Forest of Random Subsets) podpisu, který je následně podepsán pomocí WOTS+ podpisu za pomocí XMSS stromu. Kompletní algoritmus je na představu náročnější, ale pro přiblížení je možné použít následující představu.
FORS podpis udělá hash zprávy. Tuto zprávu rozdělí na samostatné části, které se berou jako adresa v rámci vygenerovaných stromů hashí. Jedna část určuje této části hash výstupu určuje který strom, druhá konkrétní hash hodnotu v rámci stromu. Tedy je možné si tento podpis představit jako tvorbu seznamu adres hashí, generovaných z nějakého vstupu. Ale jak se to vlastně realizuje ve skutečnosti a jak je tento postup propojen s WOTS+ podpisy a Merklovými stromy?
Privátní klíč pro SLH-DSA je tvořen hodnotami SecretKey.seed, SecretKey.pseudorandomfunction, PublicKey.seed a PublicKey.root. Veřejný klíč obsahuje pouze PublicKey.seed a PublicKey.root. Právě PublicKey.root je kořenem pro stromy Merklových hashí. Na jeho základě se generují samostatné stromy pro FORS podpis. Aby se uvedené hodnoty lišily, používá se SecretKey.seed pro náhodné změny od veřejného klíče, tedy útočník není schopen získat informace o počátečních hodnotách. Hash zprávy tak adresuje vytvořené záznamy adresy v rámci FORS stromu, včetně cesty k jeho kořeni. Následně jsou výsledná data veřejné části FORS podpisu předána WOTS+ schématu. Toto schéma používá zcela odlišný Merklův strom pro tvorbu finálního podpisu a zajištění důvěry. Vlastně se tak jedná o podpis přes malé pečetě. FORS působí jako úředník razítkující dokumenty a WOTS+ jako notář, který všechny dokumenty s razítkem podepíše.
Ve výsledku se tak jedná o robusní, byť relativně složitý systém. Jeho parametry omezují počet podpisů (2²⁴, 2³², ... 2⁶⁴), přesto není stavový. Jednorázové klíče se generují na základě informací o podepisovaných datech. Dalo by se to přirovnat k situaci, kdy čítač počtu podpisů by byl generován na základě hashe podepisovaných dat. Podobný příklad je i mezi ECDSA a EdDSA. Zatímco ECDSA generuje nonce náhodně, EdDSA ji generuje na základě hashe dat a privátního klíče. Tím je snížena pravděpodobnost kolize na mizivou hodnotu.

FN-DSA

Tento algoritmus je postaven na mřížkách, co je tvar vzniklý skládáním vektorů. Protože vektory nejsou shodné, je možné si mřížku představit jako obdélníkové dlaždice, kerými je vydlážděn sál. Tento sál má dvě vrstvy dlažby, základní je tvořená privátními klíči. Veřejné klíče dělají další vrstvu, která je od privátních klíčů odvozená. Lze si to představit jako poloprůhledné dlaždice. Díky tomu nejsou vidět "spáry", rozuměj mřížka z privátních klíčů. V případě snahy o tvorbu podpisu se opět spočítá hash dat. Ten se pomocí postupu GPV (Gentry-Peikert-Vaikuntanathan) změní na vektor v mřížce. V tuto chvíli nastupuje matematický aparát, jako je FFT (Fourierova Transformace), který pro tento vektor hledá konkrétní bod umístění tak, aby mezi ním a středem dlaždice byla co nejkratší vzdálenost. Lze si to představit jako umístění terče pod poloprůhledné dlaždice na mřížku privátních klíčů (hash). Díky veřejnému klíči je možné identifikovat nejbližší střed dlaždice a ověřit, zda je informace o hashi a podpisu správná. Digitální podpis je tvořenem vektorem podpisu, identifikátorem hashovací funkce a dalšími informacemi. To je zpravidla volitelný kontext, v rámci kterého se podpis provádí.

LMS

Jak už bylo zmíněno na začátku, Leighton-Micali Signature patří mezi stavové podpisy. Z uvedeného důvodu je nutno pracně držet pořadí podpisů, protože v žádném případě nesmí dojít k podepsání dvou odlišných informací stejným klíčem. Mimo nutnosti udržovat stav je uvedené schéma výrazně pomalejší. Navíc je určeno pro nižší úroveň zabezpečení než například XMSS (další schéma) a díky intenzivnímu využívání klíčového materiálu se brzy vyčerpá. Jako další zajímavost, toto schéma používá WOTS+ podpisy, vysvětlené na začátku článku. Proč by ale mělo mít smysl LMS přes všechna tato omezení používat?
Protože je tu definovaný určitý počet možných podpisů, včetně jejich pořadových čísel, je tak zajištěná kontinuita. To může být zajímavé například pro digitální podpis firmare nebo update nějakých software balíčků. Zároveň to sebou nese jisté riziko. Již při návrhu se musí počítat s určitým cyklem údržby a životnosti. Proto pro jakékoliv změny mimo rámec pravidelných update musí být k dispozici rezerva, oprava veřejného klíče již není možná.
Jak tento mechanismus vlastně pracuje? Na začátku je vytvořen Merklův strom, který má v koncových bodech předem definovaný počet hashí. Vytvoření hashe nad zvolenými daty můžeme připravit WOTS+ podpis, který je pak následně reprezentován formou cesty k danému koncovému bodu. Podpis tak obsahuje cesty, které umožní znovu vytvořit původní hash zprávy, dále pak pořadové číslo podpisu. Na základě dostupných informací je možné dopočítat kořen stromu, což umožní porovnat informace s veřejným klíčem.
Pokud si to chceme představit, můžeme jako příklad uvést velký úřad. Každý úředník bude mít sadu razítek, které může použít jenom jednou. Úřad je kořen stromu, úředník je jeden z uzlů a na konci jsou konkrétní razítka. Pokud bude potřeba orazítkovat dokument, úředník za tento dokument odpovědný si náhodně vybere jedno z razítek, připíše na dokument jak se k tomu razítku dostat (úřad, patro, dveře, úředník, polička s razítky, krabice s konkrétním razítkem), dokument orazí a razítko vrátí zpět do přihrádky. Protože ho může použít jenom jednou, není důležité číslo razítka, ale cesta, jak se k razítku dostat. V takovém případě je možné ověřit soulad čísla na dokumentu a razítku. Tedy ověřit jeho validitu.

XMSS/XMSSMT

XMSS/XMSSMT jsou schémata do jisté míry podobná předchozímu LMS. Na rozdíl od předchozího schématu, XMSS/XMSSMT podporují podstatně větší počet podpisů s jedním klíčem díky definovatelné hloubce stromu. Sice i tyto podpisy mají určitý maximální počet využití klíče, ale ten je řádově úplně jinde. Dále, jsou určeny pro bezpečnostně náročnější prostředí. V případě XMSSMT (Multi Tree) pak je ještě zvýšena celková kapacita použitím více Merklových stromů hashí. I tyto podpisová schémata jsou pomalá. ale díky prokazatelné bezpečnosti to je dobrý obchod.
Pokud se porovnávají bezpečností parametry mezi LMS, XMSS a XMSSMT, je rozdíl v počtu podpisů na základě hloubky stromu a v případě Mutli Tree pak i v počtu stromů. LMS má pro 128b bezpečnostní ekvivalent hloubku stromu h=8, což pro 2^h, tedy 2⁸ odpovídá maximálně 256 podpisům. Pro 192b bezpečností ekvivalent se pak jedná o 2¹⁶, tedy 65536 podpisů. U XMSS se jedná o hodnoty 2²⁴=16777216, 2³²=4294967296 a konečně 2⁶⁴ s obrovským počtem 1,844×10¹⁹ podpisů. V případě vícestromové struktury se pak může uvedené číslo výrazně zvýšit.
Protože LMS a XMSS jsou si značně podobné, není potřeba popisovat vlastnosti. Princip tvorby podpisu a analogie jsou stejné. Pokud by jsme se bavili o implementaci a přesném popisu, je zde pár rozdílů. Ty jsou ale zpravidla pod rozlišovací schopností většiny lidí. Měli by být zajišťovány osobami, které se této tématice věnují a mají dostatečně hluboké matematické znalosti.

Přehled

Tabulka obsahující údaje vztažené k jednotlivým podpisům a porovnání objemu používaných dat. Standardně jsou používány velikosti v bitech. Pokud je uvedena jednotka, velikost výstupu závisí na parametrech konfigurace algoritmu.

Algoritmus	Standard	Privátní klíč (bit)	Veřejný klíč (bit)	Šířka vstupních dat (bit)	Velikost podpisu (bit)
ML-DSA-44	FIPS 204	20480	10496	128 (SHAKE128)	19360
ML-DSA-65	FIPS 204	22256	15616	128 (SHAKE128)	26472
ML-DSA-87	FIPS 204	39168	20736	256 (SHAKE256)	37016
FN-DSA-512	FIPS 206	10248	7176	256 (SHAKE256)	5328
FN-DSA-768	není standardizováno	14856	10760	256 (SHAKE256)	8000
FN-DSA-1024	FIPS 206	18440	14344	256 (SHAKE256)	10240
SLH-DSA-128	FIPS205	512	256	256 (SHA256)	~ 8KB
SLH-DSA-192	FIPS205	512	256	512 (SHA512)	~ 12KB
SLH-DSA-256	FIPS205	512	256	512 (SHA512)	~ 16KB
LMS-128	RFC 8554	Dle výšky stromu	256	256 (SHA256)	~ 1KB - 2KB
XMSS-128	RFC 8391	Dle výšky stromu	256	256 (SHA256)	~ 2,5KB - 3KB
XMSS-192	není standardizováno	Dle výšky stromu	256	256 (SHA256)	~ 3KB - 4KB
XMSS-256	není standardizováno	Dle výšky stromu	256	256 (SHA256)	~ 3KB - 6KB
XMSSMT-128	není standardizováno	Dle výšky stromu	256	256 (SHA256)	~ 2,5KB - 4KB
XMSSMT-192	RFC 8391	Dle výšky stromu	256	256 (SHA256)	~ 3KB - 4KB
XMSSMT-256	RFC 8391	Dle výšky stromu	256	256 (SHA256)	~4KB - 6KB

Závěr

Přechod na kryptografii odolnou kvantovým počítačům sebou v některých případech nese výraznou změnu přístupu. Současné technologie nejsou dokonalé a naráží na nové útoky, ohrožující jejich bezpečnost. To je samozřejmě součástí běžného vývoje. Z uvedených důvodů se budou muset správci a vlastníci systémů zamyslet, zda a jak změnit požadavky na digitální podepisování, ale i architekturu systému nebo odhad výpočetních nároků. Zvláště algoritmy LMS/XMSS/XMSSMT jsou při výpočtech digitálních podpisů žrouti strojového času, na druhou stranu umožňují extrémně rychlé ověření podpisu.

Reference:

1. FIPS 204 - Module-Lattice-Based Digital Signature Standard
   Zdroj: https://www.nist.gov/
2. FIPS 205 - Stateless Hash-Based Digital Signature Standard
   Zdroj: https://www.nist.gov/
3. FIPS 206 Fast Fourier Transform-based NTRU Digital Signature Standard
   Zdroj: https://www.nist.gov/
4. RFC 8554 - Leighton-Micali Hash-Based Signatures
   Zdroj: https://www.rfc-editor.org/
5. RFC 8391 - XMSS: eXtended Merkle Signature Scheme / Multi Tree Scheme
   Zdroj: https://www.rfc-editor.org/
6. IACR - An attack on ML-DSA using an implicit hint
   Zdroj: https://eprint.iacr.org/

Autor článku:

Jan Dušátko

Jan Dušátko se počítačům a počítačové bezpečnosti věnuje již skoro čtvrt století. V oblasti kryptografie spolupracoval s předními odborníky např. s Vlastimilem Klímou, či Tomášem Rosou. V tuto chvíli pracuje jako bezpečnostní konzultant, jeho hlavní náplní jsou témata související s kryptografií, bezpečností, e-mailovou komunikací a linuxovými systémy.

Podobné články

16. 9. 2024

Sdílení souborů protokolem SMB a kryptografie

17. 9. 2024

Sdílení souborů protokolem NFS a kryptografie

27. 9. 2024

Algoritmy odolné kvantovým počítačům

8. 10. 2024

Ukládání hesel pomocí Crypt interface