Če bi današnji kriptografski protokoli odpovedali, bi bilo nemogoče zaščititi spletne povezave – pošiljati zaupna sporočila, izvajati varne finančne transakcije ali preverjati pristnost podatkov. Vsakdo je lahko dostopal do česar koli; vsak se lahko pretvarja, da je kogarkoli. Digitalno gospodarstvo bi propadlo.
Ko (oz if) postane na voljo popolnoma delujoč kvantni računalnik, prav to bi se lahko zgodilo. Posledično je leta 2017 Nacionalni inštitut za standarde in tehnologijo ameriške vlade (NIST) začel mednarodno tekmovanje za iskanje najboljših načinov za doseganje »postkvantne« kriptografije.
Prejšnji mesec je agencija izbrala svojo prvo skupino zmagovalcev: štiri protokole, ki bodo z nekaj popravki uporabljeni kot kvantni ščit. Objavil je tudi štiri dodatne kandidate, ki so še v obravnavi.
Nato sta 30. julija dva raziskovalca razkrila, da sta zlomil enega od teh kandidatov v eni uri na prenosniku. (Od takrat so drugi naredili napad še hitrejši in v nekaj minutah zlomili protokol.) »Napad, ki je tako dramatičen in močan ... je bil pravi šok,« je dejal Steven Galbraith, matematik in računalničar na Univerzi v Aucklandu na Novi Zelandiji. Ne samo, da je bila matematika, na kateri temelji napad, presenetljiva, ampak je zmanjšala (prepotrebno) raznolikost postkvantne kriptografije – odpravila je šifrirni protokol, ki je deloval zelo drugače od velike večine shem v konkurenci NIST.
"To je malo hudo," je rekel Christopher Peikert, kriptograf na Univerzi v Michiganu.
Rezultati so postkvantno kriptografsko skupnost pretresli in opogumili. Pretresen, ker je ta napad (in še en iz prejšnjega kroga tekmovanja) nenadoma spremenil tisto, kar je bilo videti kot digitalna jeklena vrata, v moker časopis. "Prišlo je iz jasnega," je rekel Dustin Moody, eden od matematikov, ki vodi prizadevanja za standardizacijo NIST. Toda če se bo kriptografska shema zlomila, je najbolje, da se to zgodi precej preden se začne uporabljati v naravi. "Veliko čustev te preveva," je rekel David Jao, matematik na univerzi Waterloo v Kanadi, ki je skupaj z IBM-ovim raziskovalcem Luca De Feo, je protokol predlagal leta 2011. Med njimi sta zagotovo presenečenje in razočaranje. "Ampak tudi," je dodal Jao, "zdaj se je vsaj pokvarilo."
Skrivni sprehodi med oblinami
Jao in De Feo sta videla priložnost za kriptografski sistem, ki je podoben dobro znanim protokolom in se od njih primerno razlikuje. Njihova shema, imenovana supersingularni izogenični Diffie-Hellmanov protokol (SIDH), je obravnavala eliptične krivulje – iste matematične objekte, ki se uporabljajo v eni najbolj razširjenih vrst kriptografije, ki se uporablja danes. Vendar jih je uporabilo na povsem drugačen način. To je bila tudi najbolj kompaktna shema, o kateri je NIST razmišljal (s kompromisom, da je bila počasnejša od mnogih drugih kandidatov).
In "matematično je res elegantno," je dejal Jao. "Takrat se je zdela lepa ideja."
Recimo, da želita dve strani, Alice in Bob, na skrivaj izmenjati sporočilo, tudi pod budnim pogledom potencialnega napadalca. Začnejo se z zbirko točk, povezanih z robovi, imenovano graf. Vsaka točka predstavlja drugačno eliptično krivuljo. Če lahko eno krivuljo pretvorite v drugo na določen način (prek zemljevida, imenovanega izogenija), narišite rob med parom točk. Graf, ki nastane, je ogromen in v njem se zlahka izgubiš: če se razmeroma kratko sprehodiš po njegovih robovih, boš končal nekje, ki je videti povsem naključno.
Alicein in Bobov graf imata vse iste točke, a robovi so različni – definirani so z različnimi izogenijami. Alice in Bob začneta na isti točki in vsak skačeta po naključnih robovih na svojem grafu ter spremljata svojo pot od ene točke do druge. Vsak nato objavi svojo končno lokacijo, vendar ohrani svojo pot skrivnost.
Zdaj zamenjata mesti: Alice gre na Bobovo končno točko, Bob pa na Alicino. Vsak ponavlja svoj skrivni sprehod. To naredita tako, da bosta oba končala na isti točki.
Ta lokacija je bila najdena na tajnosti, zato jo lahko Alice in Bob uporabita kot svoj skrivni ključ – informacijo, ki jima omogoča varno šifriranje in dešifriranje sporočil drug drugega. Tudi če napadalec vidi vmesne točke, ki si jih pošiljata Alice in Bob, ne pozna Alicine ali Bobove skrivne hoje, zato ne more ugotoviti te končne končne točke.
Da pa SIDH deluje, morata Alice in Bob izmenjati tudi nekaj dodatnih informacij o svojih sprehodih. Te dodatne informacije so privedle do propada SIDH.
Nov preobrat v stari matematiki
Thomas Decru ni nameraval zlomiti SIDH. Poskušal je graditi na tem - posplošiti metodo za izboljšanje druge vrste kriptografije. To se ni obneslo, vendar je sprožilo idejo: njegov pristop bi lahko bil koristen za napad na SIDH. In tako se je približal Wouter Castryck, njegov kolega na Katoliški univerzi v Leuvnu v Belgiji in eden od njegovih nekdanjih doktorskih svetovalcev, sta se poglobila v ustrezno literaturo.
Slučajno so naleteli na članek, ki ga je izdal matematik Ernst Kani leta 1997. To je bil izrek, ki je bil "skoraj takoj uporaben za SIDH," je dejal Castryck. "Mislim, da ko smo ugotovili, da ... je napad prišel precej hitro, v enem ali dveh dneh."
Na koncu sta Castryck in Decru pregledala produkt dveh eliptičnih krivulj – Aliceine začetne krivulje in krivulje, ki jo je javno poslala Bobu, da bi obnovila Alicein skrivni sprehod (in s tem skupni ključ). Ta kombinacija ustvari nekakšno površino, imenovano abelova površina. Nato so uporabili te abelove ploskve, Kanijev izrek (ki povezuje abelove ploskve z eliptičnimi krivuljami) in dodatne informacije, ki jih je Alice dala Bobu, da bi razkrila vsak Alicin korak.
"To je skoraj kot signal za navajanje, ki vam omogoča, da se zaklenete na [določene abelske površine]," je dejal Jao. "In ta signal vam pove, da je to pot, po kateri bi morali iti, da bi naredili naslednji korak in našli pravi [skrivni sprehod]." Kar jih je pripeljalo naravnost do skupnega ključa Alice in Boba.
"To je zelo nepričakovan pristop, gre za bolj zapletene predmete, da bi dobili rezultate o enostavnejšem predmetu," je dejal Jao.
"Zelo sem bil navdušen, ko sem videl uporabo te tehnike," je dejal Kristin Lauter, matematik in kriptograf pri Meta AI Research, ki ni le pomagal razviti kriptografije, ki temelji na izogeniji, temveč je delal tudi na abelovih površinah. "Torej sram me je, ker nisem razmišljal o tem kot o načinu, kako bi ga zlomil."
Napad Castrycka in Decruja je zlomil najnižjo varnostno različico protokola SIDH v 62 minutah in najvišjo varnostno raven v manj kot enem dnevu. Nato je kmalu zatem drug strokovnjak prilagodil napad, tako da je trajalo le 10 minut, da je zlomil različico z nizko varnostjo, in nekaj ur, da je zlomil različico z visoko stopnjo varnosti. Bolj splošni napadi objavljeno v zadnjih nekaj tednih ni verjetno, da bi bilo mogoče rešiti SIDH.
"To je bil poseben občutek," je dejal Castryck, čeprav grenak. "Ubili smo enega naših najljubših sistemov."
Prevodni trenutek
Nemogoče je zagotoviti, da je sistem brezpogojno varen. Namesto tega se kriptografi zanašajo na dovolj časa in dovolj ljudi, ki poskušajo rešiti težavo, da se počutijo samozavestne. "To ne pomeni, da se jutri ne boste zbudili in ugotovili, da je nekdo našel nov algoritem za to," je dejal Jeffrey Hoffstein, matematik na Univerzi Brown.
Zato so tekmovanja, kot je NIST, tako pomembna. V prejšnjem krogu tekmovanja NIST je Ward Beullens, IBM-ov kriptograf, zasnoval napad, ki zlomil shemo, imenovano Rainbow čez vikend. Tako kot Castryck in Decru je bil sposoben uprizoriti svoj napad šele, ko je osnovni matematični problem pogledal z drugega zornega kota. In tako kot napad na SIDH je tudi ta zlomil sistem, ki je temeljil na drugačni matematiki kot večina predlaganih postkvantnih protokolov.
"Nedavni napadi so bili prelomen trenutek," je dejal Thomas Prest, kriptograf pri startupu PQShield. Poudarjajo, kako težka je postkvantna kriptografija in koliko analiz je morda potrebnih za preučevanje varnosti različnih sistemov. "Matematični objekt v eni perspektivi morda nima očitne strukture, v drugi pa ima strukturo, ki jo je mogoče izkoristiti," je dejal. "Težji del je prepoznati pravo novo perspektivo."
