Kui tänapäeva krüptograafiaprotokollid peaksid ebaõnnestuma, oleks võrguühenduste turvamine – konfidentsiaalsete sõnumite saatmine, turvaliste finantstehingute tegemine või andmete autentimine – võimatu. Igaüks võis kõigele juurde pääseda; igaüks võib teeselda kellekski. Digimajandus kukuks kokku.
Millal (või if) saab kättesaadavaks täisfunktsionaalne kvantarvuti, just nii võib juhtuda. Selle tulemusena käivitas USA valitsuse riiklik standardite ja tehnoloogia instituut (NIST) 2017. aastal rahvusvahelise konkursi, et leida parimad viisid "kvantjärgse" krüptograafia saavutamiseks.
Eelmisel kuul valis agentuur välja oma esimese võitjate rühma: neli protokolli, mis mõningase muudatusega võetakse kasutusele kvantkilbina. Samuti teatas ta veel neljast veel kaalumisel olevast kandidaadist.
Siis 30. juulil avastas paar teadlast, et neil oli murdis ühe neist kandidaatidest tunni pärast sülearvutis. (Sellest ajast on teised rünnakut veelgi kiiremaks muutnud, rikkudes protokolli mõne minutiga.) "Nii dramaatiline ja võimas rünnak... oli paras šokk," ütles Steven Galbraith, matemaatik ja arvutiteadlane Aucklandi ülikoolis Uus-Meremaal. Rünnaku aluseks olnud matemaatika polnud mitte ainult üllatav, vaid ka vähendas (väga vajalikku) postkvantkrüptograafia mitmekesisust – kõrvaldades krüpteerimisprotokolli, mis töötas väga erinevalt enamikust NIST-i võistluse skeemidest.
"See on natuke jama," ütles Christopher Peikert, krüptograaf Michigani ülikoolis.
Tulemused on jätnud postkvantkrüptograafia kogukonna nii raputama kui ka julgustama. Raputatud, sest see rünnak (ja veel üks eelmisest võistlusvoorust) muutis digitaalse terasukse moodi väljanägemise ootamatult märjaks ajaleheks. "See tuli ootamatult," ütles Dustin Moody, üks matemaatikutest, kes juhib NIST-i standardimistööd. Kuid kui krüptograafiline skeem läheb katki, on kõige parem, kui see juhtub palju enne selle kasutamist looduses. "Teid läbivad palju emotsioone," ütles David Jao, matemaatik Kanadas Waterloo ülikoolis, kes koos IBM-i teadlasega Luca De Feo, pakkus protokolli välja 2011. aastal. Kindlasti on nende hulgas üllatus ja pettumus. "Aga ka," lisas Jao, "vähemalt läks see nüüd katki."
Salajased jalutuskäigud kurvide vahel
Jao ja De Feo olid näinud võimalust luua krüptosüsteem, mis sarnanes hästi tuntud protokollidega ja erines neist. Nende skeem, mida nimetatakse supersingulaarseks isogeensuseks Diffie-Hellmani protokolliks (SIDH), käsitles elliptilisi kõveraid - samu matemaatilisi objekte, mida kasutatakse ühes tänapäeval kõige levinumas krüptograafiatüübis. Kuid see kasutas neid täiesti erineval viisil. See oli ka kõige kompaktsem skeem, mida NIST kaalus (koos kompromissiga, et see oli aeglasem kui paljud teised kandidaadid).
Ja "matemaatiliselt on see tõesti elegantne," ütles Jao. "Tol ajal tundus see ilus idee."
Oletame, et kaks osapoolt, Alice ja Bob, tahavad salaja sõnumit vahetada, isegi potentsiaalse ründaja valvsa pilgu all. Need algavad punktide kogumiga, mis on ühendatud servadega, mida nimetatakse graafikuks. Iga punkt tähistab erinevat elliptilist kõverat. Kui saate ühe kõvera teatud viisil teisendada (kaardi abil, mida nimetatakse isogeneesiks), tõmmake punktipaari vahele serv. Saadud graafik on tohutu ja sinna on lihtne eksida: kui teete suhteliselt lühikese jalutuskäigu piki selle servi, jõuate kuhugi, mis tundub täiesti juhuslik.
Alice'i ja Bobi graafikutel on kõik samad punktid, kuid servad on erinevad - need on määratletud erinevate isogeenidega. Alice ja Bob alustavad samast punktist ja kumbki hüppavad mööda oma graafiku juhuslikke servi, jälgides oma teed ühest punktist teise. Seejärel avaldab igaüks oma lõpu asukoha, kuid hoiab oma tee saladuses.
Nüüd vahetavad nad kohad: Alice läheb Bobi viimasesse punkti ja Bob Alice'i. Igaüks kordab oma salajast jalutuskäiku. Nad teevad seda nii, et mõlemad jõuavad samasse punkti.
See asukoht leiti salaja, nii et Alice ja Bob saavad seda kasutada oma salajase võtmena – teabena, mis võimaldab neil üksteise sõnumeid turvaliselt krüptida ja dekrüpteerida. Isegi kui ründaja näeb vahepunkte, mida Alice ja Bob teineteisele saadavad, ei tea nad Alice'i või Bobi salajast käiku, seega ei saa nad seda lõplikku lõpp-punkti välja mõelda.
Kuid selleks, et SIDH toimiks, peavad Alice ja Bob oma jalutuskäikude kohta lisateavet vahetama. See lisateave viis SIDH-i allakäiguni.
Vana matemaatika uus pööre
Thomas Decru ei kavatsenud SIDH-i murda. Ta püüdis sellele tugineda – üldistada meetodit teist tüüpi krüptograafia täiustamiseks. See ei õnnestunud, kuid see tekitas idee: tema lähenemine võib olla kasulik SIDH-i ründamiseks. Ja nii ta lähenes Wouter Castryck, tema kolleeg Belgias Leuveni katoliku ülikoolis ja üks tema endistest doktoriõppe nõunikest ning nad kaks sukeldusid vastavasse kirjandusse.
Nad komistasid matemaatiku avaldatud paberi otsa Ernst Kani 1997. aastal. See oli teoreem, mis "oli peaaegu kohe rakendatav SIDH-le," ütles Castryck. "Ma arvan, et kui saime aru, et … rünnak tuli üsna kiiresti, ühe või kahe päevaga."
Lõpuks uurisid Castryck ja Decru Alice'i salajase jalutuskäigu (ja seega jagatud võtme) taastamiseks kahe elliptilise kõvera korrutist – Alice'i lähtekõverat ja kõverat, mille ta Bobile avalikult saatis. See kombinatsioon tekitab teatud tüüpi pinna, mida nimetatakse Abeli pinnaks. Seejärel kasutasid nad neid Abeli pindu, Kani teoreemi (mis seostab Abeli pindu elliptiliste kõveratega) ja lisateavet, mille Alice Bobile andis, et paljastada iga Alice'i samm.
"See on peaaegu nagu kodusignaal, mis võimaldab teil lukustada [teatud Abeli pinnad]," ütles Jao. "Ja see signaal ütleb teile, et see on tee, mille järgi peaksite tegema järgmise sammu õige [salajase jalutuskäigu] leidmiseks." Mis viis nad otse Alice'i ja Bobi jagatud võtme juurde.
"See on väga ootamatu lähenemine, mis läheb keerulisemate objektide juurde, et saada tulemusi lihtsama objekti kohta," ütles Jao.
"Olin väga põnevil, et seda tehnikat kasutatakse," ütles Kristin Lauter, Meta AI Researchi matemaatik ja krüptograaf, kes mitte ainult ei aidanud välja töötada isogeenipõhist krüptograafiat, vaid on töötanud ka Abeli pindade kallal. "Nii häbi, et ma ei mõelnud sellele kui võimalusele [seda] murda."
Castrycki ja Decru rünnak purustas SIDH-protokolli madalaima turvalisusega versiooni 62 minutiga ja kõrgeima turvataseme veidi vähem kui päevaga. Varsti pärast seda muutis teine ekspert rünnakut nii, et madala turvalisusega versiooni purustamiseks kulus vaid 10 minutit ja kõrge turvalisusega versiooni purustamiseks paar tundi. Üldisemad rünnakud postitatud viimastel nädalatel muuta SIDH päästmine ebatõenäoliseks.
"See oli eriline tunne," ütles Castryck, kuigi kibemagus. "Tappisime ühe oma lemmiksüsteemi."
Veelahelik hetk
On võimatu tagada, et süsteem on tingimusteta turvaline. Selle asemel loodavad krüptograafid, et piisavalt aega möödub ja piisavalt inimesi, kes üritavad probleemist lahti saada, et end enesekindlalt tunda. "See ei tähenda, et te ei ärka homme ja ei leia, et keegi on leidnud selle tegemiseks uue algoritmi," ütles Jeffrey Hoffstein, Browni ülikooli matemaatik.
Seetõttu on sellised võistlused nagu NIST nii olulised. NIST-i konkursi eelmises voorus kavandas IBMi krüptograaf Ward Beullens rünnaku, mis rikkus skeemi nimega Rainbow nädalavahetusel. Nagu Castryck ja Decru, suutis ta oma rünnaku lavastada alles pärast seda, kui oli vaatlenud matemaatilist probleemi teise nurga alt. Ja nagu SIDH-i rünnak, rikkus see ka süsteemi, mis toetus teistsugusele matemaatikale kui enamik kavandatud postkvantprotokolle.
"Hiljutised rünnakud olid veelahe," ütles Thomas Perst, krüptograaf käivitusettevõttes PQShield. Need rõhutavad, kui keeruline on postkvantkrüptograafia ja kui palju analüüsi võib vaja minna erinevate süsteemide turvalisuse uurimiseks. "Matemaatilisel objektil ei pruugi ühes perspektiivis ilmselge struktuur olla ja teises perspektiivis võib see olla kasutatav struktuur," ütles ta. "Raske osa on õige uue vaatenurga leidmine."
