V červenci skončilo třetí kolo výběru NIST pro standard postkvantové kryptografie (PQC). Byli vybráni kandidáti pro čtvrté kolo. To, že nejsou k dispozici kvantové počítače, neznamená, že nám prolomení stávajících kryptoalgoritmů nehrozí. Podle [2] útok již probíhá tak, že útočníci zachycují cenné zašifrované informace, ukládají je a počítají s dešifrováním na dobu, až budou kvantové počítače k dispozici a kryptografické „přezbrojení“ bude v potřebném čase nezvládnutelné.
PQC NIST AES SHA-3 CRYSTALS
NIST (Národní institut pro standardy a technologie amerického ministerstva obchodu) má cenné zkušenosti s vývojem kryptografických standardů. Jako příklad široce respektované standardizace NISTu lze uvést AES nebo SHA-3. V červenci letošního roku NIST [3, 4] vybral z přihlášených algoritmů [5] první skupinu (viz Obr. 1) nástrojů schopných odolat útoku budoucího kvantového počítače. Čtyři vybrané šifrovací algoritmy se stanou součástí postkvantového kryptografického standardu NIST, jehož dokončení se očekává přibližně za dva roky. 
Obr. 1: Z červencového vyhlášení NIST
Oznámení následuje po šestiletém úsilí řízeném NIST, který v roce 2016 vyzval světové kryptology, aby navrhli a následně prověřili šifrovací metody, jež by mohly odolat útoku budoucího kvantového počítače, který je výkonnější než dnes dostupné, srovnatelně omezené stroje. Výběr představuje začátek finále projektu standardizace postkvantové kryptografie (PQC).
Zvažují se čtyři další algoritmy pro zahrnutí do standardu a NIST plánuje oznámit finalisty z tohoto kola v budoucnu. NIST oznamuje své volby ve dvou fázích kvůli potřebě široké řady obranných nástrojů. Jak kryptografové poznali od začátku úsilí NIST, existují různé systémy a úkoly, které používají šifrování, a užitečný standard by nabízel řešení navržená pro různé situace, používal různé přístupy k šifrování a nabízel více než jeden algoritmus pro každý případ použití.
Algoritmy jsou navrženy pro dva hlavní úkoly, pro které se obvykle používá šifrování: obecné šifrování používané k ochraně informací vyměňovaných ve veřejné síti a digitální podpisy používané pro ověřování identity. Všechny čtyři algoritmy byly vytvořeny odborníky spolupracujícími z mnoha zemí a institucí.
Pro výměnu klíče při obecném šifrování NIST zvolil algoritmus CRYSTALS-Kyber. Mezi jeho výhody patří poměrně malé šifrovací klíče, které si dvě strany mohou snadno vyměnit, a také rychlost provozu. Pro digitální podpisy NIST vybral tři algoritmy CRYSTALS-Dilithium, FALCON a SPHINCS+. První dva jsou založeny na mřížkách, zatímco SPHINCS+ využívá hashování.
Recenzenti zaznamenali vysokou účinnost prvních dvou a NIST doporučuje CRYSTALS-Dilithium jako primární algoritmus s Falconem pro aplikace, které potřebují menší signatury, než může poskytnout Dilithium. Třetí, SPHINCS+, je o něco rozsáhlejší a pomalejší než ostatní dva, ale je cenný jako záloha z jediného důvodu: je založen na jiném matematickém přístupu než ostatní výběry NIST.
Na stránce https://asecuritysite.com/pqc/pqc_sig naleznete tabulku rychlostí generování klíče zpracovanou profesorem Billem Buchananem [1] ze School of Computing at Edinburgh Napier University. Z tabulky je zřejmé, že Dilithium a Picnic jsou nejrychlejší a Rainbow a SPHINCS+ jsou nejpomalejší. Nyní trochu blíže k jednotlivým kryptografickým metodám.
CRYSTALS jsou dvě kryptografická primitiva
CRYSTALS (Cryptographic Suite for Algebraic Lattices) zahrnuje dvě kryptografická primitiva: Kyber, IND-CCA2- -secure key-encapsulation mechanism (KEM); a Dilithium, silně zabezpečený algoritmus digitálního podpisu EUF-CMA (Existential Unforgeability under Chosen Message Attack). Oba algoritmy jsou navrženy tak, aby vydržely útoky kvantových počítačů. Celkově lze říci, že mřížkové metody obecně produkují poměrně malé velikosti klíčů a mají dobré úrovně výkonu. Byly také poměrně dobře prozkoumány.
Kyber pro výměnu klíčů a kryptografii veřejného klíče
V oblasti PKE/KEM (Key-exchange and Public-Key encryption) se mřížkový Kyber posouvá na standard, zatímco další mřížkové metody vypadly (Sabre, NTRU a FrodoKEM). NIST chtějí pokročit i v nemřížkových metodách. Do 4. kola soutěže postoupily:
- BIKE (Bit Flipping Key Encapsulation) – mechanismus zapouzdření klíče založený na kódu QC-MDPC (kvazicyklická kontrola parity střední hustoty).
- Klasický McEliece – používá polynomiální okruhy nad konečnými poli, v tuto chvíli nebyl přijat kvůli velkému veřejnému klíči.
- HQC (Hamming Quasi-Cyclic) založený na dekódování náhodných kvasicyklických kódů.
- SIKE (Supersingular Isogeny Key Encapsulation) – výměna klíčů je založená na izogenních supersingulárních eliptických křivkách.
Pro úpravy těchto metod byl stanoven jako deadline říjen 2022.
V analýze metod PKE/KEM publikované profesorem Buchananem na https://asecuritysite.com/pqc/pqc_kem lze vidět, že Kyber512 (který má 128bitové zabezpečení ekvivalentní AES) byl nejrychlejší pro generování klíčů, zapouzdření a dekapsulaci. Pokud jde o velikosti klíčů, vidíme, že Kyber512 má relativně malý veřejný klíč 500 bajtů, šifrovaný text 768 bajtů a tajný (soukromý) klíč o velikosti 1 632 bajtů. S ECC jsou poměrně malé velikosti klíčů, např. 32 bajtů pro soukromý klíč a 64 bajtů pro veřejný klíč.
Dilithium, SPINHCS+ a Falcon pro podpisy
Zatímco Dilithium, SPINHCS+ a Falcon postoupily, Rainbow (Multivariační kvadratický algoritmus) a Picnic (Zero Knowledge Proof na bázi hash) nepostupují. Pokud jde o výkon, Dilithium funguje nejlépe ze všech mřížkových metod a je celkově nejsilnější. I když je pro generování klíčů pomalejší než Picnic, je nejrychlejší pro podepisování a ověřování, viz https://asecuritysite.com/pqc/pqc_sig.
Pro velikosti klíčů má Dilithium2 1 312 bajtů pro veřejný klíč, 2 528 bajtů pro soukromý klíč a 2 420 bajtů pro podpis. Falcon to má podobně pro velikosti klíčů a podpis. Může se ale v některých případech stát, že Dilithium vytváří příliš dlouhé podpisy. Pro tyto případy je určen Falcon.
Protože NIST nechce plně spoléhat na mřížkovou metodu, sáhl i mezi ty nemřížkové. Zvítězil SPHINCS+, který má krátké klíče, nefunguje však tak dobře jako mřížkové metody pro podepisování a ověřování podpisů.
Podívejme se na výsledky publikované v [1] – SPHINCS+ sice v testech vytváří jeden z nejmenších veřejných (32 bajtů) a soukromých klíčů (64 bajtů), ale velikost podpisu (17 088 bajtů) je delší než u metod mřížky. Výkonem zase bodoval proti mřížkovým metodám.
S Falcon-512 (který má ekvivalentní zabezpečení jako RSA- 204) byl dle [1] generován veřejný klíč o velikosti 897 bajtů, soukromý klíč 1 281 bajtů a velikost podpisu 690 bajtů, zatímco FALCON-1024 poskytl veřejný klíč 1 793 bajtů, soukromý klíč 2 305 bajtů a velikost podpisu 1 313 bajtů.
Algoritmus je odvozen od NTRU (N-tý stupeň zkrácených polynomických jednotek okruhu), což je metoda založená na mřížce pro kvantově robustní digitální podepisování. Falcon ale používá NTRU jinak, a to jako asymetrickou metodu šifrování. Využívá tím toho, že NTRU není založen na metodách faktorizace (RSA), diskrétních protokolů nebo eliptických křivek. V testech na https://asecuritysite.com/pqc/pqc_sig byl pro šifrování dvakrát rychlejší než RSA a pro dešifrování třikrát. Celkově je FALCON ve srovnání s Dilithiumem pro generování klíčů relativně pomalý, ale je mu blízký ve výkonu, pokud jde o podepisování a ověřování klíčů.
Co bude následovat
NIST plánuje do konce léta 2022 vydat novou výzvu k předkládání návrhů pro kvantově odolné algoritmy digitálního podpisu s veřejným klíčem. NIST má zájem o návrhy pro podpisová schémata, která mají krátké podpisy a rychlé ověření.
Příspěvky, které budou reagovat na tuto výzvu, budou přijímány do 1. června 2023. Předkladatelům se doporučuje, aby s NIST komunikovali předem. NIST rozhodne, který (pokud nějaký) z předložených podpisových algoritmů přijme, a zahájí nový proces hodnocení. NIST očekává, že tento proces bude rozsahem mnohem menší než současný proces PQC. Podpisová schémata přijatá do tohoto procesu budou muset být důkladně analyzována, což bude trvat několik let.
Závěr
Práce na přechodu nemusí čekat na úplné standardy NIST, protože hybridní kryptografie umožňuje bezpečně nasazovat kvantově odolná schémata, aniž by byla ohrožena současná úroveň zabezpečení.
Mezi kroky, které mohou organizace dle [2] již nyní podniknout ke zmírnění hrozby kvantové výpočetní techniky, patří: vytvoření kryptografického inventáře, kde v rámci jejich infrastruktury a produktů existuje veškerá kryptografie s veřejným klíčem; vytvoření plánu pro uzákonění přechodu, jakmile budou normy zveřejněny; experimentování s různými rodinami PQC algoritmů, měření výkonu, zkoumání různých přístupů (např. hybridní), posuzování vzájemných závislostí atd.; a zajištění toho, že systémy jsou kryptoagilní, to znamená připravené na přechod na PQC s minimálními náklady a časem.
Použité zdroje:
[ 1 ] Buchanan, Bill. Day 0 of a Post Quantum Cryptography World, July 05, 2022, https://medium.com/asecuritysite-when-bob-met-alice/ day-0-of-a-post-quantum-cryptography-world-5f498cb835f7
[ 2 ] JOSEPH David. Transitioning organizations to post-quantum cryptography. Dostupné z: https://eorder.sheridan.com/3_0/app/ orders/13150/article.php
[ 3 ] NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. Dostupné z: https://www.nist.gov/news-events/news/2022/07/ nist-announces-first-four-quantum-resistant-cryptographic-algorithms
[ 4 ] PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates. July 05, 2022. Dostupné z: https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[ 5 ] Post-Quantum Cryptography. Dostupné z: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/ round-3-submissions
Tato e-mailová adresa je chráněna před spamboty. Pro její zobrazení musíte mít povolen Javascript.
