PQC aneb Post Quantum Cryptography

Shrnutí současného stavu v oblasti kryptografie odolné kvantovým počítačům, spolu se zjednodušeným vysvětlením útoků na současné algoritmy, přehledy problémů a významu jednotlivých technologií.

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

Vyznat se v termínech označující současný vývoj v oblasti kryptografie je docela náročné. Ale je to nutné, zvlášť kvůli blízkému nástupu technologie kvantových počítačů. Vývoj těchto strojů dal nový impuls vývoji kryptografie. Zároveň jsou populárně označovány jako kryptografický Armagedon, smrt klasické kryptografie a dalšími chytlavými termíny. Kvantové počítače mohou způsobit nepříjemnosti pro existující technologie, které se týkají např. domluvy na šifrovacích klíčích nebo digitálních podpisů, mouhou ale představovat hrozbu i pro další současné šifrovací techniky. Důvod je jednoduchý, v současnosti je možné sbírat data a dešifrovat je až budou uvedené stroje k dispozici (HNDL = Harvest Now, Decrypt Later). Jsou tajemství např. ekonomického rázu, které je nutné chránit delší dobu. A to mohou být jako roky, tak desítky let.

Současná kryptografie má v arzenálu mocný nástroj, asymetrickou kryptografii. Asymetrickou, protože klíče jsou používány asymetricky. Soukromý klíč pro šifrování, veřejný pro dešifrování (nebo obráceně, dle účelu). Uživatel má vždy pár soukromý a veřejný klíč, kde veřejný je od soukromého odvozen. Jedná se o algoritmy pod názvy RSA, ElGamal, Schnorův podpis, DSA, nebo o kryptografii nad elitickými křivkami (ECDH/ECDSA). Tyto metody se používají pro domluvu na sdíleném tajemství (chrání naši komunikaci v rámci SSL/TLS, SSH, IPSec a dalších technologiích) nebo pro digitální podpis. První algoritmy pro asymetrickou kryptografii, která tyto oblasti zajišťuje se objevily už v 70‘ letech. První prakticky nasazení o dekádu později. Nyní, po 40 letech vývoje se nám podařilo odstranit největší problémy, začít tyto technologie používat. Přestože se jedná ve většině případů o triviální postupy, které vychází z učiva základní a střední školy, některé z problémů jsou extrémně zajímavé a dodnes nejsou jednoznačně dořešeny. U současných asymetrických algoritmů je dopad kvantových počítačů zničující. Způsobil to nápad Petera W. Shora, který pro faktorizaci navrhl použít nejprve hledání modulárního základu čísla. K tomuto účelu je možné použít kvantovou verzi Fourierovy transformace (matematická verze "měření periody"). A jedinou možností obrany je najít nové, kvantovým počítačům odolné postupy.

Současná symetrická kryptografie (klíč je použit symetricky = stejný klíč je použit pro šifrování i dešifrování) je postavena nad blokovými šiframi jako je AES, ARIA, CAMELLIA, případně proudovými jako je ChaCha20. Na jejich vyjmenování by tento článek nestačil. Uvedené algoritmy představují metodu, jak zabezpečit velké objemy dat, protože jsou relativně rychlé. Kvantové počítače přináší nepříjemnost, tyto šifrovací algoritmy mohou být v případě použití malých klíčů (tedy menší než cca 168b, ale z důvodů alespoň minimální bezpečnostní rezervy doporučeno alespoň 192b) ohroženy Grooverovým útokem, ale není to planý poplach? Odpověď je jednoduchá, není. Přestože Grooverův algoritmus není nic jiného, než efektivní způsob prohledávání netříděné databáze. V případě kvantového počítače jsou tak pro útok dvě možné cesty. Buď vytvořit obrovskou databázi všech kombinací otevřeného textu, klíčů a šifrového textu, nebo spojit vyhledávací a šifrovací algoritmus do jednoho složitějšího.

Pokud se spojí Grooverův a šifrovací algoritmus, např. s implementací AES pro kvantové počítače, měli bychom získat mocný nástroj. Teoreticky by takové řešení mělo vrátit informaci hned. Výpočty se různí, pro klíč o velikosti 128b by se mělo jednat o interval od 8 minut až po 30 let (záleží na konstrukci celého zařízení, zda by se jednalo o specializovaný obvod nebo obecný kvantový počítač s programem). Ale už pro klíč o velikosti 192b by se jednalo o časovou náročnost minimálně 40 000 let. Proto je nutné použít větší klíčový materiál, aby bylo možné útok přesunout z praktické do teoretické roviny. Zatím se samozřejmě jedná o teoretický útok, protože na uvedený na něj ještě nemáme vybavení a odzkoušeny byly jenom části algoritmu. Důležité je zvolit délku klíče tak, aby s rezervou chránila tajemství po požadovanou dobu, tedy například několik dekád.

Pro zajímavost. V případě, kdy bychom chtěli pouze vytvořit databázi klíčů a šifrových textů pro klíč o velikosti 128b, dostáváme se mimo technologické a surovinové možnosti. Pokud by paměťová buňka vyžadovala 100 atomů křemíku (a nějakých dopujících prvků), bez dalších podpůrných obvodů by úložiště mělo poloměr 5000 AU … a díky své hmotnosti a gravitačnímu působení by se okamžitě zhroutila do černé díry. Tudy tedy cesta nevede, takové řešení je možné brát jenom jako kryptografický útok a matematickou hříčku.

Soutěže v oblasti post-quantum kryptografie

V současné době, tedy koncem roku 2024, probíhají následující soutěže věnující se výběru kvantově odolných algoritmů. Ty jsou často označované jako PQC – Post Quantum Cryptography. Na základě výsledku těchto soutěží je vhodné připravovat přechod na kryptografii odolnou kvantovým počítačům. Hrubá představa pro přechod může vypadat např. následujícím způsobem, v závislosti na požadavcích klientů. V roce 2030 má být ukončena podpora algoritmů se 128b bezpečnostním ekvivalentem a nejdéle do roku 2035 by měla být ukončena podpora hybridních algoritmů.

1 - Spuštění projektů migrace na PQC / QRC
2 - Začátek vlastní migrace
3 - Ukončení migrace pro kvantově odolnou kryptografii výměny klíčů u KI (Kritická Infrastruktura)
4 - Ukončení přechodu na kvantově odolnou kryptografii pro výměnu klíčů
   - Ukončení podpory symetrických algoritmů s bezpečnostním ekvivalentem < 192b
5 - Ukončení migrace na kvantově odolnou kryptografii pro digitální podpis

Výsledky této soutěže jsou obecně přijímány v Kanadě, Evropě, na Blízkém východě, v části Asie, Japonsku, Austrálii a na dalších místech. Více informací o této soutěži lze najít na adresách:
NIST Post Quantum Cryptography
NIST Post Quantum Cryptography: Additional Digital Signature Schemes

Jedná se o lokální záležitost, jako nezávislí gestoři zde působí experti jako je Tanja Lange. Díky exportu vědeckých a kulturních trendů (soft power) bude mít tato aktivita pravděpodobně nějaký, v současnosti obtížně předvídatelný dopad, ale bude určitě používáno společnostmi Samsung, LG, KIA/Hyundai... Více informací o této soutěži lze najít na adrese KpqC competition.

Čína se snaží projevit svoji nezávislost i v této oblasti. V nedávné době jsem narazil na informaci, že Rusko by mělo mít zájem na tomto vývoji spolupracovat, ale informací je málo a pro mne jsou obtížně čitelné. Více informací o soutěži lze najít na CACR PQC standardization

Standardy s dopadem na Evropu

Pro Evropu je určující standardizace v ETSI ( European Telecommunications Standards Institute), dále je pro ni zajímavý i obecně akceptovaný výsledek soutěže NIST PQC, který již vytvořil tři standardy, čtvrtý je ve stadiu návrhu. Dle současné situace bude dost algoritmů pro digitální podpis, ale patrně nedostatek pro zajištění alternativy domluvy na sdíleném tajemství. To je ale nezbytné pro zachování možnosti domluvy na klíčích a zajištění důvěrnosti šifrované komunikace.
FIPS 203 ML-KEM (původně Krystal Kyber, Key Exchange Mechanism, SVP+LWE problem)
FIPS 204 ML-DSA (původně Krystal Dilithium, Digital Signature Algorithm, SVP+LWE problem)
FIPS 205 SHL-DSA (SPHINCS+, Stateless Hash Based DSA, Digital Signature Algorithm, využívá bezstavové stromy hashí)
draft FIPS 206 FN-DSA (Falcon - Fast-fourier transform over NTRU-lattice based DSA, Digital Signature Algorithm, využívá stavové stromy hashí)

Uvedené algoritmy mají navíc doporučenou bezpečnostní úroveň, tzv. NIST Security level:
Security level 1, bezpečnostní ekvivalent 128b (AES-128, exhaustive key search)
Security level 2, bezpečnostní ekvivalent 128b (SHA-256, collision search)
Security level 3, bezpečnostní ekvivalent 192b (AES-192, exhaustive key search)
Security level 4, bezpečnostní ekvivalent 192b (SHA-384, collision search)
Security level 5, bezpečnostní ekvivalent 256b (AES-256, exhaustive key search)

Co je zajímavější, jaká doporučení poskytují k daným standardům jednotlivé organizace. Dle mého názoru ještě stále není ujasněno, jak k uvedeným standardům přistupovat. Vzhledem k obtížnosti analýzy složitosti útoku je převod na bezpečnostní ekvivalent stále problém. Zde je přehled k algoritmům digitálního podpisu:

Digitální podpis je důležitý pro autentizaci, elektronickou komunikaci, nebo z hlediska zákonů jako projev vůle. Samotný digitální podpis ale není schopen zajistit ochranu přenášených informací, nebo se dokonce domluvit na klíčovém materiálu (sdílené tajemství). Od toho tu jsou jiné algoritmy, přesněji prozatím pouze jeden algoritmus:

Právě algoritmy pro domluvu na sdíleném tajemství (KEM - Key Exchange Method) mohou vynutit i změny v současných metodách ochrany. Nejčastěji se používají protokol SSL/TLS, následované SSH protokolem. Obě tyto vrstvy mají do jisté míry podobnou architekturu a strukturu protokolu. Právě u SSL/TLS hrozí, že certifikáty s klíčovým materiálem podepisovaným post-kvantovými algoritmy mohou překročit velikost záznamu. Ten může být přenášen i více pakety, ale musí být menší než 18432B (2¹⁴ + 2048). Pokud je certifikát nebo "certificate chain" delší, přeruší se navazování spojení. A některé navrhované KEM algoritmy mohou mít klíčový materiál extrémně rozsáhlý.

Mimo uvedených algoritmů se objevily, víceméně dočasně, takzvané hybridní algoritmy. Ty jsou postaveny nad kombinací klasických a post-kvantových algoritmů a mají fungovat jako ochrana, pokud by některý z uvedených mechanismů zaznamenal výrazné ohrožení bezpečnosti. V současnosti se používají v SSL/TLS a SSH, mezi tyto hybridní algoritmy se řadí:

Problémy, umožňující tvorbu asymetrických algoritmů

Z hlediska metod, použitých při tvorbě klasických asymetrických je k dispozici následující sada problémů. Ty jsou v současnosti na svém vrcholu a v dohledné době je bude nutné nahradit jinou sadou, schopnou odolat kvantovým počítačům:

V případě algoritmů odolných kvantovým počítačům bylo nutné najít zcela odlišnou skupinu problémů. Předchozí sada problémů nebyla dostatečně odolná novým technologiím, takže bylo nutné hledat něco kvalitnějšího. Takový postup je normální součástí vývoje a kryptografie samozřejmě také nezůstává stát. Některé z těchto postupů jsou přibližně stejně staré, jakou současná asymetrická kryptografie, některé jsou součástí vývoje posledních dekád. Pro nové algoritmy použily následující skupiny zajímavých problémů:

Závěr

Současné algoritmy budou do roku 2030-2040 vážně ohrožené a je nutné se připravit na dopady, které kvantové počítače přinesou. Na druhou stranu je nutné být opatrný, předčasná implementace může vytvořit problém sám o sobě. Důvod této předběžné opatrnosti je jednoduchý. Trvalo nám 40 let vytvořit funkční asymetrickou kryptografii postavenou nad vcelku jednoduchými problémy, vlastně nad učivem základní a střední školy. Nové přístupy vyžadují podstatně hlubší matematické znalosti, důkazy správnosti a jedině vývoj v matematice odpoví na otázku, zda jsou zvolené postupy správné. Jednotlivé kroky by proto dle mého názoru měly být přibližně následující:
1. Zvětšit velikost klíčů pro symetrické algoritmy na 192b (o 25% vyšší zátěž než u 128b), lépe na 256b (o 25% vyšší zátěž než u 192b). Tím je možné jednoduše předejít problémům s možností útoku Grooverovým algoritmem.
2. Nejdéle do roku 2024 přejít na hybridní algoritmy, pokud se nepřejde přímo na kvantově odolné algoritmy. Hybridní algoritmy přesto nebude vhodné používat déle než do roku 2030-2035 a v nejdéle v této době musí být nahrazeny otestovanými kvantově odolnými algoritmy. Tato cesta je pro paranoiky, kteří buď mají obavy z možných slabin nových algoritmů, nebo kleptografie (návrh umožňující neoprávněný přístup k informacím) u nových standarů.
3. Do dvou let od standardizace začít, případně nejdéle do pěti let od standardizace dokončit přechod na kvantově odolné algoritmy. A to jak pro domluvu na klíčích, tak pro digitální podpis. V případě digitálního podpisu to bude znamenat podstatně větší množství změn v různých systémech.

Přílohy: Seznam knihoven podporujících kvantovou kryptografii

BoringSSL je knihovna společnosti Google jako fork OpenSSL. Je implementována v prohlížečích Chrome, Chromium a operačním systému Android. https://boringssl.googlesource.com/
Botan je opensource knihovna v jazyce C++. Podporuje Unix/POSIX a Windows systémy. Více informací na GitHub
liboqs je opensource knihovna v jazyce C. Podporuje Linux, Mac a Windows skrze knihovnu "Open Quantum Safe Provider for OpenSSL". Více informací na GitHub
oqs-provider je opensource knihovna rozhraní v jazyce C. Podporuje Linux, Mac a Windows a poskytuje pro knihovnu OpenSSL funkce z podpůrné knihovny, poskytující PQC algoritmy. GitHub
SymCrypt je knihovna společnosti Microsoft pod MIT licencí. Podporuje jak nové CNG API, tak starší CAPI we Windows. V prostředí Linux je možné volat SymCrypt API přímo nebo pomocí rozhraní, například rozhraní pro OpenSSL. GitHub

Přílohy: Seznam algoritmů v soutěži NIST PQC

Seznam algoritmů v soutěži organizace NIST, včetně jejich stažení, vyřazení, slučování nebo standardizace. Tento přehled ještě stále není kompletní a cílem je doplnit jednotlivé chybějící údaje tak, aby umožnili náhled na celý vývoj.

Příloha: Post-Quantum Cryptography: Additional Digital Signature Schemes

Seznam algoritmů v rozšířené sadě Additional Digital Signature Schemes, včetně detailů jako u ostatních soutěží. Tato soutěž rozšiřuje NIST PQC competition a měla by nabídnout alternativní schémata digitálních podpisů.

Poznámka: MPC znamená Multi Party Computation, většina uvedených algoritmů splňuje ZKP, tj. Zero Knowledge Principle.

Přílohy: Seznam algoritmů v soutěži KpqC Competition

Seznam algoritmů v jihokorejské soutěži, včetně jejich detailů, obdobných k soutěži NIST PQC. Tento přehled ještě stále není kompletní a cílem je doplnit jednotlivé chybějící údaje tak, aby umožnili náhled na celý vývoj.

Přílohy: Seznam algoritmů v soutěži CACR PQC standardization

Soutěž byla ve dvou kategoriích, výsledky jsou uvedeny zde. K přehledu algoritmů prozatím chybí detaily. Proto není možné získat náhled na celý vývoj a určit, z jakých důvodů byly použity některé technologie a o jaký typ technologií se jedná. Detaily budou doplněny později.
Zvolené algoritmy: AIGIS-SIG, LAC.PLE, AIGIS-ENC, LAC.KEX, SIAKE, SCloud, AKCN(AKCN-MLWE), OKCN(SKCN-MLWE), Fatseal, AKCN-E8, TALE, PKP-DSS, Piglet-1

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.