Tento článek vám přináší odpovědi na základní otázky kolem kvantově odolného šifrování. Tento článek přímo navazuje na dnešní oznámení NIST o výběru kandidátů pro standardizaci.

Kvantově odolné šifrování

Co to je kvantově odolné šifrování?

Kvantově odolné šifrování, anglicky také zvané jako post-quantum cryptography (PQC), quantum-resistant cryptography, nebo quantum-safe cryptography, je typ šifrovacích algoritmů, které by měly být odolné i vůči rozšifrování pomocí kvantových počítačů. Většina dnešních asymetrických šifer, tedy těch, které se používají pro zabezpečení jakýkoliv přenosů dat v rámci internetu nebo obecně počítačových sítí, bude jednoduše rozluštitelná pomocí budoucích kvantových počítačů.

Kdy tady budou takové kvantové počítače?

Ještě nemůžeme na 100% říci, že se takových kvantových počítačů dočkáme. Nicméně jsme na dobré cesty a odhady jsou, že v horizontu 10 až 20 let budou schopné rozšifrovat RSA 2048. Pokud se používá menší klíč, například RSA 256, tak ten horizont je blíže. Avšak je velmi obtížné určit přesnější časové okno, neboť výzkum a vývoj kolem kvantových počítačů je velmi dynamický.

10 až 20 let, to mě nemusí teď pálit ne, nebo ne?

Ano i ne. Pro běžné surfování na internetu, to opravdu není v současnosti hrozba. Nicméně, pokud skrze síť posíláte citlivější data, která budou relevantní i za těch 10 až 20 let, například biometrické identifikátory, osobní údaje, data ohledně návrhu a výroby zbraní, léčiv, chemikálií, zpravodajská data, vládní komunikace, obchodní tajemství a podobně, tak hrozba je tu už hned. Již jsou reportovány aktivity Číny v této oblasti, že se snaží již nyní zkopírovat šifrovaná data a veřejné klíče k nim s tím, že až bude dostupný kvantový počítač, tak to rozšifrují. Tato strategie se nazývá „harvest now, decrypt later“. Nicméně lze s jistotou očekávat, že to dělají i další než jen Čína.

Také je potřeba počítat s tím, že implementace kvantově odolných šifrování také zabere nezanedbatelný čas a proto je vhodné s tím začít v předstihu.

Jak je možné, že jsou současná šifrování tak slabá?

Současná asymetrická šifrování se skládají ze zašifrovaných dat a veřejného klíče. Veřejný klíč v sobě ukrývá klíč právě k těm zašifrovaným datům. Veřejný klíč je postaven na určité matematické úloze, která bez potřebných znalostí, je pro současné počítače prakticky nespočítatelná. Tedy, k onomu klíči k odemčení dat se dostanou jen odesílatel a příjemce. Avšak, již v devadesátých letech (ještě než byl postaven vůbec první kvantový počítač), Peter Shor navrhl algoritmus, který ve svém důsledku exponenciálně rychleji spočítá právě i ty matematické úlohy, které jsou použity pro současná šifrování a mi je považovali za neprolomitelná. A s blížícím se nástupem kvantových počítačů z čistě teoretické úlohy se stává reálná hrozba. Kvantově odolné šifrovací algoritmy tedy stojí na matematických úlohách, dostatečně těžkých i pro kvantový počítač.

Co s tím mám dělat?

Je potřeba přejít právě na nějaké kvantově odolné šifrování. A čím dříve, tím lépe. Avšak o čím větší organizaci se jedná, tím náročnější proces to je a zabere i několik let. V podstatě již velká část softwarových gigantů kolem toho už pracuje. Navíc zde vniká spoustu startupů, které rovněž nabízí své kvantově odolné řešení. Důležité je vybrat vhodný algoritmus pro kvantově odolné šifrování. K tomu by nám měli pomocí standardizační autority.

Je tu i jiné řešení než PQC?

Ano, alternativou je tzv. kvantová distribuce klíče, anglicky quantum key distribution (QKD). Lze matematicko-informačně dokázat, že tato metoda distribuce klíče je neprolomitelná, pokud se správně implementuje. Problém je, že se jedná o zcela novou oblast – kvantové sítě. QKD je již dnes komerčně dostupné, ale technologie je stále v počátku a má spoustu „ale“. Kvantové sítě mají zatím omezený dosah, rovněž mají omezené větvení (drtivá většina sítí je bod-bod), potřebujete kompletně nový hardware, atp.

Mluvíte o prolomitelnosti asymetrického šifrování. Jak je na tom symetrické šifrování?

Kvantové počítače teoreticky nabízí až kvadratické zrychlení možného brutálního útoku (tedy zkoušení všech možných kombinací). Nicméně současné symetrické šifry se obecně považují za bezpečné i proti kvantovým počítačům. Obecné doporučení zní zdvojnásobit délku šifrovacích klíčů.

Nicméně, není vyloučeno, že se ještě nějaký kvantový algoritmus, který využije nějakých vnitřních symetrií symetrických šifrovacích algoritmů objeví. V tokovém případě bude potřeba nahradit i daný typ symetrického šifrování.

Setkávám se s pojmy jako PKE, KEM nebo signatures, o co jde?

Ve skutečnosti potřebujeme dva typy šifrování z pohledu použití. PKE (Public-key Encryption) or KEM (key encapsulation mechanism) označuje mechanismus asymetrického klíče, tedy metody, jak přes síť přenést veřejný klíč. Tento mechanismus je zásadní pro zabezpečení jakéhokoliv přenosu přes internet či jakoukoliv síť. Diginal sigantures, neboli digitální podpisy, je podobný mechanismus, jehož cílem ale není šifrování obsahu jako ověření jeho původu. Na internetu je spousta souboru ke stahování, dostáváme spoustu emailů, které mohou být i podvrhem atd. Pro určení bezpečného původu se používají právě digitální podpisy. Protože principy pro digitální podpisy jsou na stejném principy jako asymetrické šifrování, i ony jsou náchylné k možnému budoucímu podvrhování podpisů kvantovým počítačem.

Proces standardizace a NIST

Co to je NIST a proč o něm mluvíte?

NIST je zkratka National Institute of Standards and Technology, česky bychom řekli Národní institut standardů a technologie z USA. NIST je jednou z hlavních autorit ohledně standardizace, ale i například měřící laboratoře, kde NIST vyvíjí a provozuje super přesné atomové hodiny, apod. Klíčové pro nás je, že ty kvantově odolné algoritmy, které NIST vybere, budou klíčové pro komunikaci s americkými vládními institucemi, tedy pro americký trh a následně i pro globální trh. Navíc, NIST si s výběrem dává poměrně záležet.

O čem je dnešní oznámení NIST?

Po třech kolech výběrového řízení, NIST dnes oznámil finalisty pro kvantově odolné šifrování, které budou standardizovány. Pro PKE-KEM se jedná o:

Pro digitální podpisy budou standardizovány:

Vybraní čtyři kandidáti nyní postoupí do procesu standardizace. Tento proces ještě nějaký čas potrvá, nicméně na softwarovém i hardwarovém řešení lze začít pracovat již nyní. Také si lze všimnout, že vypadl algoritmus RAINBOW, u kterého jsme mohli vidět prolomení právě i jen na obyčejném notebooku.

NIST říká, že CRYSTALS-Kyber a CRYSTALS-Dilithium byly vybrány hlavně díky jejich vysoké bezpečnosti a dobrému výkonu a lze očekávat, že budou pracovat dobře pro většinu aplikací. Falcon pak bude využit pro případy, kdy digitální podpis z CRYSTALS-Dilithium by byl příliš velký. SPHINCS+ byl vybrán jako alternativa, která pracuje na jiném principu než na mřížce.

Zároveň vidíme, že pro PKE/KEM nemáme alternativu. Z toho důvodu bude NIST pokračovat čtvrtým kolem, kde budou posuzovány algoritmy BIKE, HQC, SIKE a Classic McEliece, kde první tři původně byli onačeny jako alternativa a poslední, McEliece byl finalista, ale zatím na kandidáta na standardizaci to nedotáhl (hlavně z důvodu velikosti veřejného klíče). NIST očekává, že skoro určitě jako druhý vybere alespoň jednoho z dvojce BIKE a HQC.

Proč výběr kandidátů na PQC trval tak dlouho?

Ano, je to dlouhý proces, který začal v roce 2016 a ten bude i kontinuálně pokračovat. Výběr nových algoritmů pro kvantově odolné šifrování je netriviální záležitost. Je zde několik kritérií, které chcete dodržet.

1) Je potřeba dané kandidáty detailně prozkoumat z matematického i informačního hlediska. Protože by tyto algoritmy měli nahradit stávající šifrování, musíte si být jisti, že je to opravdu bezpečné. Minimálně dvakrát se stalo, že kandidáti byli prolomeny i jen na klasickém notebooku. Kdybychom něco takového nasadili, tak by to byla katastrofa obrovských rozměrů. Protože je potřeba si dávat záležet a výběr u NIST je proto několika kolový.

2) Nechcete jen jeden algoritmus, ale několik tzv. rodin algoritmů, tedy několik algoritmů pracujících na rozdílných principech. To je důležité pro případ, kdy se v budoucnu objeví nějaký nový algoritmus ať pro klasický nebo kvantový počítač, který by jej mohl rozšifrovat. To pak jednoduše přepneme na šifrování z jiné rodiny, která dost pravděpodobně není zasažena. Pravda je taková, že u žádných šifrovacích algoritmů nejsme schopni dokázat, že je to neprolomitelný v nějaký rozumný čas.

3) Je potřeba s ohledem na výpočetní náročnost jednotlivých šifrovacích algoritmů najít shodu na ideálních parametrech jako jsou velikost klíče, rychlost dešifrování, velikost šifrovaného textu, atd.

4) Jsou zde i právní aspekty. Algoritmus-kandidát by měl být volně dostupný, ať už jako open source nebo majitel patentu jej uvolní pro komerční i nekomerční účely.

A NIST je jediná autorizační autorita?

Není, jsou zde i jiné, které na tom pracují, například ITU, ETSI, atd. Avšak, panuje zde však všeobecné přesvědčení, že NIST s velmi důkladným výběrem kandidátů ještě před samotným procesem standardizace spíše opravdu představí algoritmy, které jsou bezpečné informaticky, ale i právně.

Na aktivitách kolem doporučení a standardizace pracují často i organizace mající na starost národní bezpečnost, například NSA v USA, GCHQ/NCSC v Velké Británii, BSI v Německu či ANSSI ve Francii.

Jak vypadá proces implementace kvantově odolného šifrování?

Bude se jednat o dlouhodobý a poměrně bolestivý proces. NIST odhaduje, že potrvá 5-15 let po dokončení standardizace než bude PQC všude plně implementované. Problémů je tu celá řada. Není to tak, že by vše bylo šifrované přímo operačním systémem, jako je Windows, ale každá aplikace, dokonce i v rámci jednotlivých externích knihoven používaných aplikacemi pro nějakou komunikaci ven najdete různé implementace šifrování. To vše bude potřeba nahradit.

Další věcí je, že dnes i části hardware mají speciální části pro zrychlení výpočtů pro šifrování. Právě rychlost bude asi největší problém. Lze si jednoduše představit, že použití těžších matematických úloh zabere i více výpočetního výkonu a času a obecně to povede ke zpomalení počítačů. V případě malých zařízení, například v rámci internetu věcí (IoT), i k zásadním zpomalením.

Výše, jsme zmínili, že během testování byly nějaké algoritmy prolomeny. To však neznamená, že ten algoritmus není bezpečný. Ve skutečnosti většina těchto algoritmů má několik parametrů, které potřebujete nějak vhodně vybrat. Jedním extrémem je rychlý výpočet, ale méně bezpečné. Druhý extrém je super bezpečný, ale velmi výpočetně náročný.