Jos nykyiset salausprotokollat epäonnistuisivat, verkkoyhteyksiä olisi mahdotonta turvata - luottamuksellisten viestien lähettäminen, suojattujen taloustoimien suorittaminen tai tietojen todentaminen. Kuka tahansa voi käyttää mitä tahansa; kuka tahansa voi teeskennellä olevansa kuka tahansa. Digitaalisuus romahtaa.
Milloin (tai if) täysin toimiva kvanttitietokone tulee saataville, juuri niin voi tapahtua. Tämän seurauksena Yhdysvaltain hallituksen National Institute of Standards and Technology (NIST) käynnisti vuonna 2017 kansainvälisen kilpailun löytääkseen parhaat tavat "post-quantum" -salauksen saavuttamiseksi.
Viime kuussa virasto valitsi ensimmäisen voittajaryhmänsä: neljä protokollaa, jotka otetaan käyttöön kvanttisuojana. Se ilmoitti myös neljästä lisäehdokkaasta, jotka ovat vielä harkinnassa.
Sitten 30. heinäkuuta tutkijapari paljasti, että heillä oli rikki yksi ehdokkaista tunnissa kannettavalla tietokoneella. (Sittemmin muut ovat tehneet hyökkäyksestä entistä nopeamman, rikkoen protokollan muutamassa minuutissa.) "Hyökkäys, joka on niin dramaattinen ja voimakas... oli melkoinen shokki", sanoi Steven Galbraith, matemaatikko ja tietojenkäsittelytieteilijä Aucklandin yliopistossa Uudessa-Seelannissa. Hyökkäyksen taustalla oleva matematiikka ei ollut pelkästään yllättävää, vaan se vähensi (erittäin kaivattua) postkvanttisalauksen monimuotoisuutta – eliminoi salausprotokollan, joka toimi hyvin eri tavalla kuin suurin osa NIST-kilpailun järjestelmistä.
"Se on vähän harmillista", sanoi Christopher Peikert, kryptografi Michiganin yliopistosta.
Tulokset ovat saaneet postkvanttisalausyhteisön järkyttymään ja rohkaisemaan. Järkytettynä, koska tämä hyökkäys (ja toinen edelliseltä kilpailukierrokselta) muutti yhtäkkiä digitaalisen teräsoven märäksi sanomalehdeksi. "Se tuli tyhjästä", sanoi Dustin Moody, yksi NIST-standardointityötä johtavista matemaatikoista. Mutta jos salausjärjestelmä rikkoutuu, on parasta, jos se tapahtuu hyvissä ajoin ennen sen käyttöä luonnossa. "Sinun läpi kulkee monia tunteita", sanoi David Jao, matemaatikko Waterloon yliopistosta Kanadassa, joka yhdessä IBM-tutkijan kanssa Luca de Feo, ehdotti pöytäkirjaa vuonna 2011. Varmasti yllätys ja pettymys kuuluvat niihin. "Mutta myös", Jao lisäsi, "ainakin se meni rikki nyt."
Salaiset kävelyt käyrien välissä
Jao ja De Feo olivat nähneet mahdollisuuden luoda salausjärjestelmä, joka oli sekä samanlainen että sopivasti erilainen kuin hyvin tunnetut protokollat. Heidän suunnitelmansa, jota kutsutaan supersingularisogeny Diffie-Hellman -protokollaksi (SIDH), käsitteli elliptisiä käyriä - samoja matemaattisia objekteja, joita käytetään yhdessä yleisimmistä nykyään käytetyistä salaustyypeistä. Mutta se käytti niitä täysin eri tavalla. Se oli myös tiiviin järjestelmä, jota NIST harkitsi (sillä kompromissilla se oli hitaampi kuin monet muut ehdokkaat).
Ja "matemaattisesti se on todella tyylikäs", sanoi Jao. "Silloin se vaikutti kauniilta ajatukselta."
Oletetaan, että kaksi osapuolta, Alice ja Bob, haluavat vaihtaa viestin salassa, jopa mahdollisen hyökkääjän valppaana katseen alla. Ne alkavat kokoelmalla pisteitä, joita yhdistävät reunat, joita kutsutaan graafiksi. Jokainen piste edustaa erilaista elliptistä käyrää. Jos pystyt muuttamaan yhden käyrän toiseksi tietyllä tavalla (isogenyksi kutsutun kartan kautta), piirrä reuna pisteparin väliin. Tuloksena oleva graafi on valtava ja siihen on helppo eksyä: Jos kävelet suhteellisen lyhyesti sen reunoja pitkin, päädyt jonnekin, joka näyttää täysin satunnaiselta.
Liisan ja Bobin graafit sisältävät kaikki samat pisteet, mutta reunat ovat erilaisia – ne määritellään eri isogenioilla. Alice ja Bob aloittavat samasta pisteestä, ja he hyppäävät kukin satunnaisia reunoja pitkin omassa kaaviossaan pitäen kirjaa polkunsa pisteestä toiseen. Jokainen julkaisee sitten lopetuspaikkansa, mutta pitää polkunsa salassa.
Nyt he vaihtavat paikkoja: Alice menee Bobin viimeiseen pisteeseen ja Bob Aliceen. Jokainen toistaa salaisen kävelynsä. He tekevät tämän siten, että molemmat päätyvät samaan pisteeseen.
Tämä sijainti on löydetty salassa, joten Alice ja Bob voivat käyttää sitä salaisena avaimenaan – tietona, jonka avulla he voivat salata ja purkaa toistensa viestit turvallisesti. Vaikka hyökkääjä näkisi välipisteet, jotka Alice ja Bob lähettävät toisilleen, he eivät tiedä Alicen tai Bobin salaista kävelyä, joten he eivät voi selvittää lopullista päätepistettä.
Mutta jotta SIDH toimisi, Alice ja Bob tarvitsevat myös lisätietoja kävelystään. Nämä lisätiedot johtivat SIDH:n kaatumiseen.
Uusi käänne vanhaan matematiikkaan
Thomas Decru ei aikonut rikkoa SIDH:ta. Hän yritti rakentaa sen pohjalle - yleistää menetelmää toisen tyyppisen kryptografian parantamiseksi. Se ei toiminut, mutta se herätti ajatuksen: Hänen lähestymistapansa saattaa olla hyödyllinen SIDH:n hyökkäämiseen. Ja niin hän lähestyi Wouter Castryck, hänen kollegansa Leuvenin katolisessa yliopistossa Belgiassa ja yksi hänen entisistä tohtorinneuvonantajistaan, ja he sukelsivat aiheeseen liittyvään kirjallisuuteen.
He törmäsivät matemaatikon julkaisemaan paperiin Ernst Kani Vuonna 1997. Siinä oli lause, joka "oli lähes välittömästi sovellettavissa SIDH:hen", Castryck sanoi. "Luulen, että kun tajusimme, että… hyökkäys tuli melko nopeasti, yhdessä tai kahdessa päivässä."
Lopulta palauttaakseen Alicen salaisen kävelyn (ja siten jaetun avaimen) Castryck ja Decru tutkivat kahden elliptisen käyrän tuloa – Alicen aloituskäyrän ja käyrän, jonka hän lähetti julkisesti Bobille. Tämä yhdistelmä tuottaa eräänlaisen pinnan, jota kutsutaan Abelin pinnaksi. Sitten he käyttivät näitä Abelin pintoja, Kanin lausetta (joka yhdistää Abelin pinnat elliptisiin käyriin) ja lisätietoa, jonka Alice antoi Bobille paljastaakseen jokaisen Alicen tekemän askeleen.
"Se on melkein kuin kotiutussignaali, jonka avulla voit lukittua [tietyille Abelin pinnoille]", Jao sanoi. "Ja tuo signaali kertoo, että tämä on tapa, jolla sinun tulee mennä seuraavaan askeleen oikean [salaisen kävelyn] löytämiseksi." Mikä johti heidät suoraan Alicen ja Bobin yhteiseen avaimeen.
"Se on hyvin odottamaton lähestymistapa, jossa mennään monimutkaisempiin objekteihin saadakseen tuloksia yksinkertaisemmasta kohteesta", Jao sanoi.
"Olin erittäin innoissani nähdessäni tämän tekniikan käytön", sanoi Kristin Lauter, Meta AI Researchin matemaatikko ja kryptografi, joka ei ainoastaan auttanut kehittämään isogenyysiin perustuvaa kryptografiaa, vaan on myös työskennellyt Abelin pinnoilla. "Joten häpeä minua, kun en ajatellut sitä tapana rikkoa [se]."
Castryckin ja Decrun hyökkäys rikkoi SIDH-protokollan alhaisimman suojaustason 62 minuutissa ja korkeimman suojaustason vajaassa päivässä. Sitten, pian sen jälkeen, toinen asiantuntija viritti hyökkäystä niin, että heikomman suojan murtamiseen meni vain 10 minuuttia ja korkean turvatason murtamiseen pari tuntia. Yleisempiä hyökkäyksiä lähetetty viime viikkoina tehdä epätodennäköiseksi, että SIDH voidaan pelastaa.
"Se oli erityinen tunne", Castryck sanoi, vaikkakin katkeransuloinen. "Tapomme yhden suosikkijärjestelmistämme."
Vesistöalue
On mahdotonta taata, että järjestelmä on ehdoitta turvallinen. Sen sijaan kryptografit luottavat siihen, että aikaa kuluu tarpeeksi ja ihmiset yrittävät ratkaista ongelman tunteakseen olonsa itsevarmaksi. "Se ei tarkoita, ettet herää huomenna ja huomaa, että joku on löytänyt uuden algoritmin sen tekemiseen", sanoi Jeffrey Hoffstein, matemaatikko Brownin yliopistosta.
Siksi NISTin kaltaiset kilpailut ovat niin tärkeitä. NIST-kilpailun edellisellä kierroksella IBM:n kryptografi Ward Beullens suunnitteli hyökkäyksen, joka rikkoi suunnitelman nimeltä Rainbow viikonloppuna. Castryckin ja Decrun tapaan hän pystyi toteuttamaan hyökkäyksensä vasta nähtyään taustalla olevaa matemaattista ongelmaa eri näkökulmasta. Ja kuten SIDH:n hyökkäys, tämäkin rikkoi järjestelmän, joka perustui eri matematiikkaan kuin useimmat ehdotetut post-kvanttiprotokollat.
"Viimeaikaiset hyökkäykset olivat vedenjakaja", sanoi Thomas Perst, kryptografi käynnistysyrityksessä PQShield. Ne korostavat, kuinka vaikeaa post-kvanttisalaus on ja kuinka paljon analyysiä saatetaan tarvita eri järjestelmien turvallisuuden tutkimiseen. "Matemaattisella objektilla ei ehkä ole ilmeistä rakennetta yhdessä näkökulmassa, ja sillä voi olla hyödynnettävä rakenne toisessa", hän sanoi. "Vaikeinta on löytää oikea uusi näkökulma."
