Strasti a slasti kryptografie odolné kvantovým počítačům, část první: KEM

V rámci soutěže NIST došlo k publikaci algoritmů pro výměnu klíčů a digitální podpis. Dle mého názoru je vhodné popsat chování těchto algoritmů popularizační formou, tedy bez použití matematiky. Představa, jak uvedené algoritmy pracují, může být pro někoho důležitá. Každý z těchto algoritmů má svoje specifické vlastnosti, které mohou přinést jistá omezení, ty je vhodné chápat. Zbrklá implementace těchto algoritmů nebo nepochopení jejich principů může mít výrazné dopady na celkovou ochranu dat. První článek se bude věnovat KEM algoritmům CRYSTALS-Kyber, HQC a CSIDH. Zkratka KEM znamená Key Encapsulation Mechanism, v češtině jako mechanismus zapouzdření klíčů. Druhý připravovaný článek se pak bude věnovat DSA algoritmům Falcon, Sphincs++ a algoritmům využívajícím Merklovy stromy. Název DSA znamená Digital Signature Algorithm, v češtině Algoritmus Digitálního Podpisu. Jedná se o rodinu algoritmů a nesmí se plést se zastaralým standardem pro digitální podpis DSA. Ten byl postaven nad Schnorrovým podpisem (nebo jak uvádí některé prameny, nad algoritmem El-Gamal,).

Algoritmus pro zapouzdření klíčů ML-KEM

Jedná se o standard FIPS-203. Princip domluvy na klíčích je vcelku jednoduchý. Díky využití asymetrické kryptografie jedna strana využije veřejný klíč protistrany pro šifrování citlivého údaje a následně ho pošle protistraně. Protistrana může provést opačnou operaci dešifrování, protože právě jenom ona má privátní klíč. Díky tomu obě strany mají citlivé údaje, které je možné použít přímo jako šifrovací klíče, nebo je vložit do funkce pro odvození klíčů (KDF, Key Derivation Funcion). Klíč je možné poskytnout pro obě strany stejným způsobem. V takovém případě jak zasílání tak příjem komunikace používá pro symetrické šifry stejný klíč. Další možností je poskytnout dva samostatné klíče, jeden pro odesílání, druhý pro příjem dat. Sice bude stále použit symetrický algoritmus, ale každý z proudů dat bude šifrován odlišným klíčovým materiálem. Postup výměny klíčů do jisté míry připomíná svou funkčností možnosti algoritmu RSA.

Funkční princip algoritmu ML-KEM aka CRYSTALS-Kyber (pouze pro zvědavé)

Algoritmus používá matematickou strukturu známou jako mřížky. Tato struktura vzniká opakovaným skládáním stejných vektorů. Pro příklad mřížky je možné použít dlažbu. Představte si, že jste v obrovské dlážděné místnosti. Každá dlaždice má stejnou velikost, tedy délku a šířku (výsledkem je obdélník). Opakováním těchto dlaždic vzniká pravidelný síťový vzor na podlaze nebo i na stěně. Tento vzor je generován privátním klíčem, tedy délkou a šířkou dlaždice. Pokud budeme chtít vytvořit veřejný klíč, je nutné použít nějaký nový podle vzoru základní mřížky. Nemusí být ani pravoúhlý, vektory mohou svírat libovolný úhel. Důležité je, aby se nepotkávaly s průsečíky sítí privátních klíčů (podkladovou mřížkou). Pro veřejný klíč tak použijeme například průhledné kosodélníkové dlaždice. Hodnoty délky stran kosodélníku budou jednotlivé části veřejného klíče. Jejich odvození je možné právě od zmiňovaného tajného klíče, ke kterému přidáváme neurčitost (chybu).
Při šifrování se využívá složitosti dvou problémů. Prvním je LWE (Learning with Error), druhým je SVP (Shortest Vector Problem). Uvedené problémy je nutné znát pro pochopení celé struktury šifrování, ale vysvětlení každého z problémů je nutné oddělit od druhého.
LWE je založen na náročnosti hledání násobků a odpovídající chyby pro rovnici N=v*w+e. V tomto případě se násobí dvě čísla a přičte se chyba. Obdobným způsobem je možné násobit i vektory, v případě šifrování na mřížkách to není ve jen ve dvou rozměrech, ale rozměrů mohou být desítky nebo stovky. Ke každému výsledku se přičte nová hodnota náhodné chyby, která tak vytváří šum a ztěžuje útok. V našem příkladu budeme ale stále používat pouze dva rozměry. Právě LWE stojí za utajením privátních klíčů, které díky chybové hodnotě e zašumí. Uvedená chyba je pro každou hranu dlaždice odlišná (například hodnoty -1;0;1). Takže neznáme vlastně jejich přesné rozměry, průhledné dlaždice v tomto případě až tak průhledné nebudou. A aby toho nebylo málo, průhledné dlaždice (veřejné klíče) jsou odvozeny od privátních klíčů, ale privátní klíč je uschován. V tu chvíli ztrácíme jistotu a musíme spoléhat pouze na vzor, který vidíme.
SVP je pro změnu založen na náročnosti zjištění, jaká je nejkratší cesta mezi dvěma body mřížky. Přesněji mezi bodem určeným veřejnými klíči a mezi bodem určeným privátními klíči. Pokud je potřeba najít nejkratší vektor (nejkratší vzdálenost) od konkrétního bodu mřížky tvořené veřejným klíčem k libovolnému bodu mřížky tvořené privátním klíčem, přes průhledné dlaždice by jsme je mohli najít. Jenže co když vidíme jenom kosodélníkový obraz? Aby toho nebylo málo, co když ani ty dlaždice nebudou dvourozměrné, ale budou mít sto nebo tisíc dimenzí? Najednou se z docela jednoduchého problému stává noční můra.
V případě šifrování je vlastní šifrovaný záznam rozbitý na malé kousky, které se jako chyba přidávají ke každé jednotlivé průhledné dlaždici. Výsledkem jsou nepravidelnosti, které by bylo možné napadnout. Ale matematika zde dovoluje vytvořit postup, který uvedené nepravidelnosti převede do tvaru, který je extrémně obtížné interpretovat. Tedy dojde k tvorbě šifrového textu. Ten pro útočníka nedává smysl a není možné ho jen s použitím veřejného klíče dešifrovat. Ale vlastník privátního klíče je v jiné situaci, dokáže odečíst jak svoje chyby, tak velikost „dlaždic“ ke kterým byly tyto kousky přilepeny. Výsledkem budou malé kousky šifrového textu, které stačí pouze složit do odpovídajícího tvaru. Tím získá původní text před zašifrováním a obě strany tak sdílí stejné tajemství.

Tabulka velikosti klíčů pro ML-KEM

Algoritmus pro zapouzdření klíčů HQC, standard v přípravě

Před nedávnem byl ve čtvrtém kole výběru kvantově odolných algoritmů NIST, přijat jako další výherce algoritmus HQC. Tento algoritmus byl schválen v březnu 2025, odhaduje se termín vydání standardu někdy příští rok, tj. 2026. Opět se jedná o algoritmus pro výměnu klíčů, tedy jedna strana klíč vygeneruje a pošle na stranu druhou. Do jisté míry funkčností připomíná možnosti výměny klíčů pomocí algoritmu RSA.

Funkční princip algoritmu HQC (pouze pro zvědavé)

Algoritmus používá pro ochranu údajů takzvaný problém dekódování obecného lineárního kódu. Vysvětlení opět vyžaduje určitou představu a drobný výlet do historie. První otázkou je, co jsou vlastně lineární kódy. Jedná se o kódování dat způsobem, které dokáží bránit různým přeslechům komunikace a obnovit přenášená data. Jedním z úžasných použití je kód pro spojení se sondami Voyager (Golay [24,12,8] a Reed Solomon). Uvedené kódy zajišťují ochranu proti chybám spojení a zároveň dovolují dekódování dat. Bez uvedeného samoopravného kódu by to nebylo možné.
Jak k tomu dochází? Představte si někoho, kdo vysílá Morseovou abecedou větu „Quis custodiet ipsos custodes?“ Série teček a čárek bude vypadat následujícím způsobem:
--.- ..- .. ... / -.-. ..- ... - --- -.. .. . - / .. .--. ... --- ... / -.-. ..- ... - --- -.. . ... ..--..
Co ale dělat v okamžiku, kdy bude radiové vysílání rušeno? Co když získáme text, který bude vypadat následujícím způsobem, kdy rušení bude označeno písmenem X? Budeme schopni zprávu přečíst?
--.XX..X ..XX..XXX-.X.X..- ... XX--- -.X .. . X / .XX.-X. ... XXXX... XX-.-XX..- X.. X ---XX.. XX... ..XX..
Luštění takové zprávy je náročné a za určitých podmínek nemožné. Odesílatel a příjemce vygenerují svoje privátní a veřejné klíče, kde privátní klíč je složen ze dvou vektorů. Většina bitů každého vektoru je nulová a jenom na několika místech jsou jedničky (řídká struktura). Veřejný klíč je generován na základě těchto privátních klíčů, jedná se o kontrolní matici vynásobenou druhým z vektorů, k této matici se přičte první vektor a náhodná chybová hodnota.
Při šifrování zprávy dochází k několika krokům. První, zpráva se převede do některého z cyklických kódů se samoopravnou schopností (Reed-Muller nebo Reed-Solomon) a vygenerují se dva pracovní vektory (stejným způsobem jako části privátního klíč). První vektor se vynásobí s kontrolní maticí a výsledek je použit jako první část šifrovaných dat. Druhá část vznikne jako násobek veřejného klíče s prvním vektorem, ke kterému se přičte obsah zprávy a chybové hodnoty. Tyto dva vektory se pošlou příjemci. Ten na základě privátního klíče a přijatých vektorů dokáže jednoduše odstranit šum. Vynásobí první část svého privátního klíče prvním vektorem a druhou část svého klíče druhým vektorem, hodnoty sečte a má zprávu v uvedeném samoopravném kódu. Ten je následně použit pro opravu případných chyb. Pro některé lidi se jedná o matematická kouzla, výsledek je ale obtížně napadnutelný.

Tabulka velikosti klíčů pro HQC

Algoritmus pro domluvu na klíčích CSIDH

Jeden z mých oblíbených algoritmů, který se bohužel neúčastnil soutěže a proto nebyl vybrán. Soutěže se účastnil pouze podobný algoritmus SIDH, který byl v srpnu 2023 zlomen. Oba algoritmy jsou postaveny nad určitou třídou eliptických křivek. Přestože pro většinu lidí v branži jsou eliptické křivky automaticky zranitelné kvantovými počítači, zde to nemusí platit. Záleží na tom, jaký problém je zvolen pro zajištění ochrany dat. Přestože byl SIDH zlomen ale CSIDH ne, je tu spousta otázek týkající se jeho bezpečnosti. Z uvedeného důvodu musí být ještě nějakou dobu bezpečnost prověrována. Algoritmus se mi ale líbí kvůli své nepopiratelné výhodě. Na rozdíl od předchozích dvou algoritmů zde nedochází k určení tajemství jednou stranou, kde následuje přenos protistraně. Tento algoritmus se domlouvá na klíčích a vyměňuje pouze mezivýsledky. Protože obě strany provádí série výpočtů, díky této výměně je výsledkem hodnota shodná na obou stranách. Klíč se nikde nepřenáší. V současnosti nám takový algoritmus chybí. Jak bude zmíněno dále, má to jisté bezpečnostní výhody. V případě přirování k současným technologiím se jedná se o ekvivalent funkčnosti algoritmu Diffie Helman nad eliptickými křivkami, ale takové přirovnání je hodně zjednodušující.

Funkční princip algoritmu CSIDH (pouze pro zvědavé)

Jak už zde bylo uvedeno, jedná se o algoritmus nad eliptickými křivkami. Zní to složitě, ale v případě kryptografie na eliptických křivkách se používá modulární aritmetika. Tu je možné si představit jako oříznutí grafu v určité vzdálenosti nahoru a doprava, jakmile se tato vzdálenost překročí, začíná se na protilehlé straně. Jinak řečeno, jako bych papír stočil do ruličky a z ruličky udělal pneumatiku. Papír by musel být ovšem značně pružný. Tato představa řeší současnou kryptografii, ale ta odolná kvantovým počítačům je ještě o něco složitější.
V matematice existují takzvané invarianty. Ty označují vlastnost, která se nemění. Příkladem mohou být i eliptické křivky, kde jejich vlasnosti mohou být za určitých podmínek vzájemně invariantní, tedy mají něco stálého a společného. V případě SIDH/CSIDH se jedná o takzvaný j-invariant (třída izomorfismů). Pokud tedy zvolíme několik křivek, které mají stejný invariant, a zároveň mají tyto křivky podobné parametry, mohou mít stejný počet bodů na křivce. V takovém případě je možné tvořit vztahy mezi těmito body, tedy jakousi mapu přechodů. Celý princip spočívá v tom, jak budeme mezi křivkami procházet. Pokud přejdeme z jedné na druhou, můžeme se na grafu křivky (na dané čáře po obvodu té konkrétní pneumatiky) dostat k dalšímu bodu. Přejdeme na další křivku a opět můžeme najít další bod, nebo přímo pokračovat změnou křivky. Díky našemu klíči procházení (zůstanu stát, přechod mezi křivkami, změna bodu na křivce) tak tvoříme konkrétní mapu cesty. Uvedené cesty mohou být složité, v případě výpočtu jsou ale důležité tři body. První, kde začínáme. Druhý, který si s protistranou měníme. A konečně třetí, na kterém se s protistranou shodneme.
V případě domluvy na klíčích se určí počáteční křivka a konkrétní bod. Každá ze stran vyrazí vlastní cestou, až se dostane po předem definovaném počtu opakování na místo, kde klíč popisující průchod křivkami končí. V tu chvíli si obě strany vymění své body protistranou. Následně začnou opět vkládat svoji mapu cesty, tentokrát z vyměněných bodů. Po ukončení se musí shodnout na stejném výsledku, protože vlastně došlo ke složení mapy průchodu pro první a druhou stranu. Tento algoritmus má stále ještě spoustu otevřených otázek. Ty mohou a nebo také nemusí vést k jeho zlomení. Ale chybí nám tu mechanismus schopný zajistit domluvu na klíčích bez nutnosti posílat klíčový materiál z jedné strany na druhou.

Tabulka velikosti klíčů pro CSIDH

Současnost a celkové zhodnocení bezpečnosti

V tuto chvíli jsou přijaté algoritmy ML-KEM a HQC bezpečné, tedy alespoň na základě současných znalostí. Problémem je slovní spojení na základě současných znalostí. Stejně tak, jako se ukazuje možná hrozba pro současné algoritmy v kvantových počítačích, můžeme v budoucnosti nalézt jiné hrozby. Můžeme najít jiné způsoby útoků na algoritmy, nebo také nemusíme. To je důvod, proč je nutné vývoj v oblasti kryptografie bedlivě sledovat.
Další hrozby přinášejí překvapivě současné technologie. První je provozní hrozba, která spočívá ve struktuře SSL/TLS. Každý ze záznamů (Record protocol) musí být menší než 16384B, s dalšími hodnotami na úrovni TLS je možné rozšíření o dalších 2048B. (TLS Record protocol)+2048B(TLS Overhead)=18432B. Pokud je záznam větší, k navázání spojení pravděpodobně nedojde a skončí chybou. Důvodem je způsob navazování spojení. Při domluvě (TLS Handshake) je přenášen zároveň certifikát. A algoritmy odolné kvantovým počítačům mají prostě příliš velké klíče a podpisy. Pokud zpráva obsahující certifikát přeteče přes uvedenou hodnotu, nemusí dojít ke spojení. Částečně tento problém řeší fragmentace certifikátu (multiple records), ale ne každá implementace ho podporuje. Doporučení je držet se do hodnoty maximálně tří záznamů, občas je možné narazit i na několik stovek KB. Zde zpravidla dochází i k pádům TLS knihoven podporujících fragmentaci.
Druhým problémem je hrozba v oblasti SSL inspekce. Stejně jako v případě současných algoritmů, tak i v případě kvantově odolných algoritmů závisí ochrana proti SSL inspekci na vhodné konfiguraci. Na inspekčním systému dochází k dekódování komunikace díky schopnosti oficiálním způsobem padělat SSL certifikáty. Dochází tak vlastně k zřetězenému spojení, kde jedna šifrovaná komunikace je mezi klientem a inspekční bránou, druhá mezi inspekční bránou a cílovým systémem. Jedinou spolehlivou ochranou je použití mTLS (mutual TLS). To dovoluje ověřit certifikát klienta i serveru a zároveň kontrolovat vztah mezi klientským certifikátem a uživatelským jménem. Kvantově odolné algoritmy proti této hrozbě nechrání a není to ani jejich cílem. Tedy i v případě jejich použití je možné díky SSL inspekci je možné získat dešifrovaná data. Přes všechny chyby má ale inspekce ve velkém množství případů své opodstatnění. Ochrana sítě, kontrola komunikace na exfiltraci dat a další účely jsou pochopitelné. Ale je jako každý nástroj, i SSL inspekci je možné zneužít.
Celková bezpečnost systémů tedy záleží nejneom na podporovaných algoritmech a metodách ochrany přenášených dat. Současné algoritmy jsou dle dostupných údajů bezpečné. Z provozního hlediska je extrémně důležité, že máme dostupný už druhý algoritmus pro výměnu klíčů odolný kvantovým počítačům. Lépe, až budou dostupné další, ideálně i s podporou domluvy na klíčích. Ale tyto záležitosti se nesmí uspěchat a matematika v pozadí musí uzrát. Až teprve poté bude možné nasadit další připravované.
Z preventivního hlediska je vhodné se zamyslet i nad jednou zastaralou možností. Co dělat v případě technologického průlomu. V takovém případě je vhodné minimálně po dočasnou dobu využívat alternativní metody distribuce klíčů. A jako nouzové řešení mohou stále ještě posloužit … kurýři. Je to možná šílená myšlenka. Jedná se o nejhorší možný scénáře, na který dle mého nedojde. Ale kdo je předem varován, je také předem připraven (Praemonitus, praemunitus.).

Závěr

Z hlediska bezpečnosti je žádoucí mít k dispozici několik ověřených alternativ pro přechod na hybridní, případě čistě post-kvantovou kryptografii. Je vynikající, že máme k dispozici různé metody ochrany, ale ještě nás čeká dlouhý vývoj abychom byli schopni zajistit důvěrnost informací odpovídajícím způsobem. Tedy včetně záložních alternativ. Všechny mechanismy je nutné prověřit a zajistit nejenom jejich matematickou, ale také implementační bezpečnost. Je to prostě záležitost přirozeného vývoje. A ten nelze uspěchat. V dalším díle se budu věnovat algoritmům pro digitální podpis a odlišností, které se u kvatově odolné kryptografie objevují.

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.