Posztkvantum kriptográfia – az új algoritmus „60 perc alatt elment”

Írtunk a PQC-ről, röviden posztkvantum kriptográfia, korábban többször is.

Ha lemaradt volna az elmúlt évek médiaizgalmáról az úgynevezett kvantumszámítással kapcsolatban…

…ez (ha megbocsát, amit egyes szakértők valószínűleg meggondolatlan túlegyszerűsítésnek tartanak) olyan számítástechnikai eszközök építésének módja, amelyek nyomon követhetik többféle lehetséges kimenetel egy számításból egyidejűleg.

Nagy odafigyeléssel és talán egy kis szerencsével ez azt jelenti, hogy bizonyos típusú algoritmusokat átírhat a helyes válaszra, vagy legalább helyesen eldobhat egy csomó rossz választ anélkül, hogy minden lehetséges eredményt kipróbálna és tesztelne. egyenként.

Két érdekes kriptoanalitikai gyorsítás lehetséges egy kvantumszámítógép segítségével, feltételezve, hogy egy megfelelően erős és megbízható eszköz valóban megszerkeszthető:

• Grover kvantumkereső algoritmusa. Általában, ha a válaszok véletlenszerűen rendezett halmazában szeretne keresni, hogy megtudja, az Öné szerepel-e a listán, akkor a legrosszabb esetben az egész listán kell végigfutnia, mielőtt végleges választ kapna. Például, ha meg akarja találni a 128 bites AES visszafejtő kulcsot egy dokumentum kódolásának feloldásához, keresnie kell az összes lehetséges kulcs listáját, kezdve: 000..001, ..2, ..3, és így tovább, egészen a FFF..FFF (16 bájt értékű FF), hogy biztosan megoldódjon a probléma. Más szóval, meg kell határoznia a költségvetést, hogy kipróbálja mind a kettőt¹²⁸ lehetséges kulcsokat, mielőtt megtalálná a megfelelő kulcsot, vagy megállapítaná, hogy nincs. Grover algoritmusa azonban egy nagy és elég erős kvantumszámítógép mellett azt állítja, hogy képes végrehajtani ugyanazt a bravúrt a négyzetgyök a szokásos erőfeszítésből, így elméletileg mindössze 2 alatt feltöri a kódot⁶⁴ helyette próbálkozik.
• Shor kvantumfaktorizációs algoritmusa. Számos kortárs titkosítási algoritmus arra támaszkodik, hogy két nagy prímszám összeszorozása gyorsan megtörténik, míg a szorzatuk visszaosztása a két számra, amivel elkezdte, lehetetlen. Ennek átérezéséhez próbálja meg szorozni az 59 × 87-et tollal és papírral. Eltarthat egy percig, mire kiszedjük (5133 a válasz), de nem olyan nehéz. Most próbálja meg a másik utat. Osszuk vissza mondjuk a 4171-et két tényezőjére. Sokkal nehezebb! (43×97.) Most képzelje el, hogy ezt egy 600 számjegyből álló számmal teszi. Lazán szólva, elakadsz abban, hogy megpróbálod elosztani a 600 jegyű számot minden lehetséges 300 jegyű prímszámmal, amíg el nem éred a főnyereményt, vagy nem találod, hogy nincs válasz. Shor algoritmusa azonban azt ígéri, hogy megoldja ezt a problémát a logaritmus a szokásos erőfeszítésből. Így 2048 bináris számjegy faktorálása csak kétszer annyi ideig tart, mint egy 1024 bites szám, nem pedig kétszer olyan hosszú ideig, mint egy 2047 bites szám, ami óriási gyorsulást jelent.

A fenyegetés leküzdése

A Grover algoritmusából fakadó fenyegetést egyszerűen úgy lehet leküzdeni, ha növeljük a használt számok méretét négyzetre emelve, ami azt jelenti, hogy megduplázzuk a kriptográfiai hashben vagy a szimmetrikus titkosítási kulcsban lévő bitek számát. (Más szóval, ha úgy gondolja, hogy az SHA-256 jelenleg rendben van, akkor az SHA-512 használata PQC-rezisztens alternatívát jelentene.)

De Shor algoritmusát nem lehet olyan könnyen ellensúlyozni.

Egy 2048 bites nyilvános kulcs méretét exponenciálisan kell növelni, nem egyszerűen négyzetre emeléssel, így a 2×2048=4096 bites kulcs helyett vagy egy új kulcsra lenne szükség a lehetetlen 2-es mérettel.²⁰⁴⁸ bitek…

…vagy egy teljesen újfajta posztkvantum titkosítási rendszert kellene elfogadnia, amelyre Shor algoritmusa nem vonatkozott.

Nos, az amerikai szabványügyi testület, a NIST a PQC „verseny” 2017 vége óta.

A folyamat mindenki számára nyitott, minden résztvevőt szeretettel várunk, minden algoritmust nyíltan tettek közzé, és a nyilvános ellenőrzés nemcsak lehetséges, hanem aktívan bátorítják:

Pályázati felhívás. [2017. zárva]. […] A tervek szerint az új nyilvános kulcsú kriptográfiai szabványok egy vagy több további, nem minősített, nyilvánosan közzétett digitális aláírást, nyilvános kulcsú titkosítást és kulcsbeállítási algoritmust határoznak meg, amelyek világszerte elérhetőek, és képesek megvédeni az érzékeny kormányzati információkat. jóval a belátható jövőben, beleértve a kvantumszámítógépek megjelenését is.

Három beadvány és megbeszélés után A NIST bejelentette, 2022-07-05, hogy négy olyan algoritmust választott, amelyeket azonnali hatállyal „szabványnak” tekintett, és mindegyiknek kellemesen csengő neve van: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONés SPHINCS+.

Az első (CRYSTALS-KYBER) az úgynevezett a Kulcs megállapodási mechanizmus (KEM), ahol a nyilvános kommunikációs csatorna két vége biztonságosan összehoz egy egyszeri privát titkosítási kulcsot a munkamenet értékű adatának bizalmas cseréjéhez. (Egyszerűen fogalmazva: a leskelők csak felaprított káposztát kapnak, így nem tudják lehallgatni a beszélgetést.)

A másik három algoritmust használják Digitális aláírások, mellyel biztosíthatja, hogy az Ön által kiadott adatok pontosan megegyezzenek azzal, amit a feladó a másikba bevitt, így megelőzheti a manipulációt és az integritást. (Egyszerűen fogalmazva: ha valaki megpróbálja elrontani vagy elrontani az adatokat, tudni fogja.)

Több algoritmusra van szükség

Az új szabványok bejelentésével egy időben a NIST bejelentette a negyedik kör versenytársai, további négy algoritmust kínálva lehetséges alternatív KEM-ként. (Ne feledje, hogy a cikk írásakor már három jóváhagyott digitális aláírási algoritmus közül választhatunk, de csak egy hivatalos KEM.)

Ezek voltak: BIKE, Classic McEliece, HQC és a SIKE.

Érdekes módon a McEliece algoritmus Robert Mc Eliece amerikai kriptográfus találta fel még az 1970-es években, aki 2019-ben halt meg, jóval azután, hogy a NIST versenye már zajlott.

Ez azonban soha nem fogott meg, mert hatalmas mennyiségű kulcsfontosságú anyagot igényelt a korabeli népszerű alternatívához, a Diffie-Hellman-Merkle algoritmushoz (DHM, vagy néha csak DH) képest.

Sajnos a három Round Four algoritmus egyike, nevezetesen SIKE, úgy tűnik, feltörték.

című agyforgató dolgozatban EGY HATÉKONY KULCS-HELYREÁLLÍTÁSI TÁMADÁS A SIDH-NEK (ELŐZETES VÁLTOZAT), Wouter Castryk és Thomas Decru belga kriptográfusok úgy tűnik, valami halálos csapást mértek a SIKE algoritmusra.

Ha kíváncsi, a SIKE a rövidítése Szuperszinguláris Izogeny Key Encapsulation, és a SIDH jelentése Szuperegyedi Izogeny Diffie-Hellman, konkrét felhasználása a SIKE algoritmus ahol a kommunikációs csatorna két vége DHM-szerű „kriptodáncot” hajt végre, hogy egy csomó nyilvános adatot cseréljenek ki, amely lehetővé teszi, hogy mindkét végén egy privát értéket származtassanak, amelyet egyszeri titkos titkosítási kulcsként használnak.

Itt nem próbáljuk megmagyarázni a támadást; csak megismételjük, amit a lap állít, nevezetesen, hogy:

Nagyon lazán fogalmazva, a bemenetek itt tartalmazzák a kulcslétrehozási kriptodance egyik résztvevője által megadott nyilvános adatokat, valamint a folyamatban használt előre meghatározott (és ezért nyilvánosan ismert) paramétereket.

De a kinyert kimenet (az így hivatkozott információ az izogén φ fent) állítólag a folyamat soha fel nem tárt része – az úgynevezett privát kulcs.

Más szóval, pusztán a nyilvános információkból, például a kulcsbeállítás során nyíltan kicserélt adatokból, a kriptográfusok azt állítják, hogy vissza tudják állítani az egyik résztvevő privát kulcsát.

És miután megismeri a privát kulcsomat, könnyen és észrevétlenül úgy tesz, mintha én lennék, így a titkosítási folyamat megszakad.

Úgy tűnik, a kulcsfeltörő algoritmus körülbelül egy órát vesz igénybe, mindössze egyetlen CPU magot használva, olyan feldolgozási teljesítménnyel, mint egy mindennapi laptopban.

Ez ellentétes a SIKE algoritmussal, ha úgy van beállítva, hogy megfeleljen az 1. szintnek, a NIST alapvető titkosítási biztonsági fokozatának.

Mit kell tenni?

Semmit!

(Ez a jó hír.)

Ahogy a cikk szerzői javasolják, miután megjegyezték, hogy az eredményük még előzetes, „A dolgok jelenlegi állása mellett úgy tűnik, hogy a SIDH teljesen megbomlott bármely nyilvánosan generált alapgörbe esetében.”

(Ez a rossz hír.)

Ha azonban a SIKE algoritmust hivatalosan még nem hagyták jóvá, most vagy adaptálható ennek a konkrét támadásnak a meghiúsítására (amit a szerzők elismernek, lehetséges lehet), vagy egyszerűen eldobható.

Bármi is történik végül a SIKE-kal, ez kiváló emlékeztető arra, hogy a saját titkosítási algoritmusok feltalálása miért tele van veszélyekkel.

Ez is egy jó példa arra, hogy miért szabadalmaztatott titkosítási rendszerek amelyek magának az algoritmusnak a titkosságára támaszkodnak 2022-ben egyszerűen elfogadhatatlan a biztonságuk fenntartása.

Ha egy PQC-algoritmus, mint például a SIKE, több mint öt éven át túlélte a világ minden tájáról érkező szakértők által végzett meggyőződést és szondázást, annak ellenére, hogy kifejezetten nyilvánosságra hozták, hogy nyilvános vizsgálatnak vethessék alá…

…akkor nem kell feltenned magadnak a kérdést, hogy a saját készítésű, látás elől elrejtett titkosítási algoritmusaid mennyire boldogulnak, ha szabadon engedik!

---