Ha a mai kriptográfiai protokollok meghibásodnának, lehetetlen lenne az online kapcsolatok biztonságossá tétele – bizalmas üzenetek küldése, biztonságos pénzügyi tranzakciók végrehajtása vagy adatok hitelesítése. Bárki bármihez hozzáférhetett; bárki bárkinek kiadhatta magát. A digitális gazdaság összeomlana.
Mikor (vagy if) elérhetővé válik egy teljesen működőképes kvantumszámítógép, pontosan ez történhet. Ennek eredményeként 2017-ben az Egyesült Államok kormányának Nemzeti Szabványügyi és Technológiai Intézete (NIST) nemzetközi versenyt indított, hogy megtalálja a legjobb módszereket a „posztkvantum” kriptográfia megvalósítására.
A múlt hónapban az ügynökség kiválasztotta a nyertesek első csoportját: négy protokollt, amelyeket némi átdolgozással kvantumpajzsként fognak bevetni. Négy további jelöltet is bejelentett, amelyek még mérlegelés alatt állnak.
Aztán július 30-án egy kutatópár felfedte, hogy igen megtörte az egyik jelöltet egy óra múlva laptopon. (Azóta mások még gyorsabbá tették a támadást, és percek alatt felrúgták a protokollt.) „Egy olyan drámai és erőteljes támadás… elég sokk volt” – mondta. Steven Galbraith, matematikus és informatikus az Aucklandi Egyetemen, Új-Zélandon. Nemcsak a támadás alapjául szolgáló matematika volt meglepő, de csökkentette a (nagyon szükséges) posztkvantum kriptográfia sokféleségét – kiiktatta a titkosítási protokollt, amely nagyon eltérően működött a NIST versenyben szereplő sémák túlnyomó többségétől.
"Ez egy kicsit balhé" - mondta Christopher Peikert, a Michigani Egyetem kriptográfusa.
Az eredmények megrendítették és bátorították a posztkvantum kriptográfiai közösséget. Megrendülten, mert ez a támadás (és egy másik a verseny korábbi fordulójából) hirtelen nedves újsággá változtatta a digitális acélajtót. – A semmiből jött – mondta Dustin Moody, a NIST szabványosítási erőfeszítéseinek egyik vezető matematikusa. De ha egy kriptográfiai séma megtörik, akkor a legjobb, ha jóval azelőtt megtörténik, hogy vadonban használnák. „Sok érzelem jár át rajtad” – mondta David Jao, a kanadai Waterloo Egyetem matematikusa, aki az IBM kutatójával együtt Luca De Feo2011-ben javasolta a protokollt. Természetesen a meglepetés és a csalódás is köztük van. – De emellett – tette hozzá Jao –, legalább most eltört.
Titkos séták görbék között
Jao és De Feo lehetőséget látott egy olyan kriptográfiai rendszer létrehozására, amely egyszerre hasonlít a jól ismert protokollokhoz, és kellően különbözik azoktól. A szuperszinguláris izogén Diffie-Hellman protokollnak (SIDH) nevezett sémájuk az elliptikus görbékkel foglalkozott – ugyanazokkal a matematikai objektumokkal, amelyeket a ma elterjedt kriptográfia egyik legelterjedtebb típusában használnak. De teljesen más módon használta őket. Ez volt a legkompaktabb séma is, amelyet a NIST fontolgatott (azzal a kompromisszummal, hogy lassabb volt, mint sok más jelölt).
És „matematikailag nagyon elegáns” – mondta Jao. – Akkoriban ez egy gyönyörű ötletnek tűnt.
Tegyük fel, hogy két fél, Alice és Bob titokban akar üzenetet váltani, még egy potenciális támadó éber tekintete alatt is. Az élekkel összekapcsolt pontok gyűjteményével kezdődnek, amelyeket gráfnak neveznek. Minden pont más elliptikus görbét ábrázol. Ha egy görbét egy adott módon (egy izogénnek nevezett térképen keresztül) alakíthat át egy másikra, rajzoljon egy élt a pontpárok közé. Az eredményül kapott gráf hatalmas, és könnyen eltévedhet benne: Ha viszonylag rövid sétát tesz a szélein, olyan helyre kerül, ahol teljesen véletlenszerűnek tűnik.
Alice és Bob gráfjai ugyanazokat a pontokat tartalmazzák, de az élek eltérőek – különböző izogeniák határozzák meg őket. Alice és Bob ugyanabban a pontban indulnak, és mindketten véletlenszerű élek mentén ugrálnak a saját grafikonjukon, nyomon követve az egyik pontból a másikba vezető útjukat. Ezután mindegyik közzéteszi a végpontját, de titokban tartja az útját.
Most helyet cserélnek: Alice Bob utolsó pontjához megy, Bob pedig Alice-hez. Mindegyik megismétli titkos sétáját. Ezt úgy teszik, hogy mindketten ugyanarra a pontra kerüljenek.
Ezt a helyet titokban találták meg, így Alice és Bob titkos kulcsként használhatja – olyan információ, amely lehetővé teszi egymás üzeneteinek biztonságos titkosítását és visszafejtését. Még ha egy támadó látja is azokat a közbenső pontokat, amelyeket Alice és Bob küldenek egymásnak, nem ismerik Alice vagy Bob titkos sétáját, így nem tudják kitalálni a végső végpontot.
De ahhoz, hogy a SIDH működjön, Alice-nek és Bobnak további információkat is ki kell cserélnie a sétáikról. Ez az extra információ vezetett a SIDH bukásához.
Új csavar a régi matematikában
Thomas Decru nem akarta megtörni a SIDH-t. Megpróbált erre építeni – általánosítani a módszert egy másik típusú kriptográfia fejlesztése érdekében. Ez nem sikerült, de ötletet váltott ki: az ő megközelítése hasznos lehet a SIDH megtámadásában. És így közeledett Wouter Castryck, kollégája a belgiumi Leuveni Katolikus Egyetemen és egyik korábbi doktori tanácsadója, és mindketten belemerültek a vonatkozó irodalomba.
Egy papírra bukkantak, amelyet a matematikus adott ki Ernst Kani Ebben egy tétel volt, amely „szinte azonnal alkalmazható volt a SIDH-ra” – mondta Castryck. – Azt hiszem, ha egyszer rájöttünk, hogy… a támadás elég gyorsan, egy-két nap alatt jött.
Végül, hogy visszaszerezze Alice titkos sétáját (és így a megosztott kulcsot), Castryck és Decru megvizsgálta két elliptikus görbe szorzatát – Alice kezdőgörbéjét és azt a görbét, amelyet nyilvánosan küldött Bobnak. Ez a kombináció egyfajta felületet hoz létre, amelyet Abel-felületnek neveznek. Ezután felhasználták ezeket az Abel-felületeket, Kani-tételt (amely az Abel-felületeket elliptikus görbékhez kapcsolja), és az Alice által Bobnak adott plusz információkat, hogy feltárják Alice minden lépését.
„Majdnem olyan, mint egy irányjelző jel, amely lehetővé teszi [bizonyos Abel-felületeken] való bezárkózást” – mondta Jao. "És ez a jel azt mondja, hogy ezen az úton kell haladnia, hogy megtegye a következő lépést a megfelelő [titkos séta] megtalálásához." Ez egyenesen Alice és Bob közös kulcsához vezetett.
"Ez egy nagyon váratlan megközelítés, amely bonyolultabb objektumokra megy, hogy eredményeket kapjon az egyszerűbb objektumokról" - mondta Jao.
„Nagyon izgatott voltam, amikor láttam, hogy ezt a technikát használják” – mondta Kristin Lauter, a Meta AI Research matematikusa és kriptográfusa, aki nemcsak az izogénalapú kriptográfia kifejlesztésében segített, hanem Abel-féle felületeken is dolgozott. „Szégyen ezért nem gondolok rá, mint arra, hogy megtörjem.”
Castryck és Decru támadása 62 perc alatt megtörte a SIDH protokoll legalacsonyabb biztonsági szintjét, és alig egy nap alatt a legmagasabb biztonsági szintet. Aztán nem sokkal később egy másik szakértő úgy módosította a támadást, hogy mindössze 10 percbe telt az alacsony biztonságú verzió feltörése, és néhány órába telt a fokozott biztonságú verzió feltörése. Általánosabb támadások közzétéve az elmúlt hetekben valószínűtlenné teszi a SIDH megmentését.
„Különleges érzés volt” – mondta Castryck, bár keserédes. "Megöltük az egyik kedvenc rendszerünket."
Egy vízválasztó pillanat
Lehetetlen garantálni, hogy egy rendszer feltétel nélkül biztonságos. Ehelyett a kriptográfusok arra számítanak, hogy elegendő idő múlik el, és elegendő ember próbálja megoldani a problémát, hogy magabiztosnak érezze magát. "Ez nem azt jelenti, hogy holnap nem ébredsz fel és nem tapasztalod, hogy valaki új algoritmust talált erre" - mondta. Jeffrey Hoffstein, matematikus a Brown Egyetemen.
Ezért olyan fontosak az olyan versenyek, mint a NIST. A NIST verseny előző fordulójában Ward Beullens, az IBM kriptográfusa olyan támadást dolgozott ki, megtörte a Rainbow nevű sémát egy hétvégén. Castryckhez és Decruhoz hasonlóan ő is csak azután tudta megindítani a támadását, hogy más szemszögből szemlélte a mögöttes matematikai problémát. És a SIDH elleni támadáshoz hasonlóan ez is megtörte azt a rendszert, amely más matematikára támaszkodott, mint a legtöbb javasolt posztkvantum protokoll.
"A legutóbbi támadások vízválasztó pillanatot jelentettek" - mondta Thomas Perst, a PQShield startup kriptográfusa. Rávilágítanak arra, hogy milyen nehéz a posztkvantum kriptográfia, és mennyi elemzésre lehet szükség a különböző rendszerek biztonságának tanulmányozásához. "Egy matematikai objektumnak az egyik perspektívában nincs nyilvánvaló szerkezete, és van egy másik perspektívában kihasználható szerkezete" - mondta. "A nehéz rész az, hogy megtaláljuk a megfelelő új perspektívát."
