Hvis dagens kryptografiprotokoller skulle svikte, ville det være umulig å sikre nettforbindelser – å sende konfidensielle meldinger, foreta sikre økonomiske transaksjoner eller autentisere data. Hvem som helst kunne få tilgang til hva som helst; hvem som helst kunne utgi seg for å være hvem som helst. Den digitale økonomien ville kollapse.
Når (eller if) en fullt funksjonell kvantedatamaskin blir tilgjengelig, det er nettopp det som kan skje. Som et resultat lanserte den amerikanske regjeringens National Institute of Standards and Technology (NIST) i 2017 en internasjonal konkurranse for å finne de beste måtene å oppnå "post-kvante" kryptografi.
Forrige måned valgte byrået sin første gruppe vinnere: fire protokoller som, med en viss revisjon, vil bli distribuert som et kvanteskjold. Den kunngjorde også fire ekstra kandidater som fortsatt er under vurdering.
Så den 30. juli avslørte et par forskere at de hadde knust en av disse kandidatene om en time på en bærbar PC. (Siden den gang har andre gjort angrepet enda raskere, og brutt protokollen i løpet av få minutter.) "Et angrep som er så dramatisk og kraftig ... var ganske et sjokk," sa sa Steven Galbraith, en matematiker og informatiker ved University of Auckland i New Zealand. Ikke bare var matematikken som lå til grunn for angrepet overraskende, men den reduserte det (sårt tiltrengte) mangfoldet av post-kvantekryptografi – og eliminerte en krypteringsprotokoll som fungerte veldig annerledes enn det store flertallet av ordningene i NIST-konkurransen.
"Det er litt av en bummer," sa Christopher Peikert, en kryptograf ved University of Michigan.
Resultatene har gjort post-kvantekryptografisamfunnet både rystet og oppmuntret. Rystet, fordi dette angrepet (og et annet fra en tidligere runde i konkurransen) plutselig gjorde det som så ut som en digital ståldør til våt avis. "Det kom ut av det blå," sa Dustin Moody, en av matematikerne som leder NIST-standardiseringsinnsatsen. Men hvis et kryptografisk opplegg skal gå i stykker, er det best om det skjer i god tid før det brukes i naturen. "Det er mange følelser som går gjennom deg," sa David Jao, en matematiker ved University of Waterloo i Canada som sammen med IBM-forsker Luca De Feo, foreslo protokollen i 2011. Absolutt overraskelse og skuffelse er blant dem. "Men også," la Jao til, "den ble i det minste ødelagt nå."
Hemmelige turer blant kurver
Jao og De Feo hadde sett en mulighet for et kryptografisk system som både var likt og passende forskjellig fra kjente protokoller. Opplegget deres, kalt supersingular isogeny Diffie-Hellman-protokollen (SIDH), omhandlet elliptiske kurver - de samme matematiske objektene som brukes i en av de mest utbredte typene kryptografi som er distribuert i dag. Men den brukte dem på en helt annen måte. Det var også den mest kompakte ordningen som NIST vurderte (med den avveining at den var tregere enn mange av de andre kandidatene).
Og "matematisk er det veldig elegant," sa Jao. "På det tidspunktet virket det som en vakker idé."
La oss si at to parter, Alice og Bob, ønsker å utveksle en melding i hemmelighet, selv under det våkne blikket til en potensiell angriper. De begynner med en samling punkter forbundet med kanter kalt en graf. Hvert punkt representerer en annen elliptisk kurve. Hvis du kan transformere en kurve til en annen på en bestemt måte (via et kart kalt en isogeni), tegner du en kant mellom punktparet. Den resulterende grafen er enorm og lett å gå seg vill i: Hvis du tar en relativt kort spasertur langs kantene, ender du opp et sted som ser helt tilfeldig ut.
Alices og Bobs grafer har alle de samme punktene, men kantene er forskjellige - de er definert av forskjellige isogenier. Alice og Bob starter på samme punkt, og de hopper langs tilfeldige kanter på hver sin graf, og holder styr på veien fra ett punkt til et annet. Hver publiserer deretter sluttplasseringen, men holder banen hemmelig.
Nå bytter de plass: Alice går til Bobs siste punkt, og Bob til Alices. Hver gjentar sin hemmelige vandring. De gjør dette på en slik måte at de begge vil havne på samme punkt.
Denne plasseringen er funnet i det skjulte, så Alice og Bob kan bruke den som sin hemmelige nøkkel – informasjon som lar dem kryptere og dekryptere hverandres meldinger på en sikker måte. Selv om en angriper ser mellompunktene som Alice og Bob sender hverandre, kjenner de ikke til Alices eller Bobs hemmelige tur, så de kan ikke finne ut det endelige endepunktet.
Men for å få SIDH til å fungere, må Alice og Bob også utveksle litt tilleggsinformasjon om turene deres. Den ekstra informasjonen er det som førte til SIDHs fall.
En ny vri på gammel matematikk
Thomas Decru ville ikke bryte SIDH. Han prøvde å bygge videre på det - å generalisere metoden for å forbedre en annen type kryptografi. Det fungerte ikke, men det utløste en idé: Hans tilnærming kan være nyttig for å angripe SIDH. Og så nærmet han seg Wouter Castryck, hans kollega ved det katolske universitetet i Leuven i Belgia og en av hans tidligere doktorgradsrådgivere, og de to dykket ned i den relevante litteraturen.
De snublet over en artikkel publisert av matematikeren Ernst Kani i 1997. I det var et teorem som "var nesten umiddelbart aktuelt for SIDH," sa Castryck. "Jeg tror at når vi først skjønte at ... angrepet kom ganske raskt, på en eller to dager."
Til slutt, for å gjenopprette Alices hemmelige vandring (og derfor den delte nøkkelen), undersøkte Castryck og Decru produktet av to elliptiske kurver - Alices startkurve og kurven hun sendte offentlig til Bob. Den kombinasjonen produserer en slags overflate som kalles en abelsk overflate. De brukte deretter disse abelske overflatene, Kanis teorem (som relaterer abelske overflater til elliptiske kurver), og den ekstra informasjonen Alice ga Bob for å avdekke hvert skritt Alice tok.
"Det er nesten som et målsøkingssignal som lar deg låse deg fast på [visse abelske overflater]," sa Jao. "Og det signalet forteller deg at dette er veien du bør gå for å ta neste skritt for å finne den riktige [hemmelige vandringen]." Noe som førte dem rett til Alice og Bobs felles nøkkel.
"Det er en veldig uventet tilnærming, å gå til mer kompliserte objekter for å utlede resultater om det enklere objektet," sa Jao.
"Jeg var veldig spent på å se denne teknikken bli brukt," sa Kristin Lauter, en matematiker og kryptograf ved Meta AI Research som ikke bare hjalp til med å utvikle isogeni-basert kryptografi, men som også har jobbet på abelske overflater. "Så skam meg for ikke å tenke på det som en måte å bryte [det]."
Castryck og Decrus angrep brøt den laveste sikkerhetsversjonen av SIDH-protokollen på 62 minutter og det høyeste sikkerhetsnivået på i underkant av en dag. Så, kort tid etterpå, finjusterte en annen ekspert angrepet slik at det tok bare 10 minutter å bryte lavsikkerhetsversjonen og et par timer å bryte den høysikkerhetsversjonen. Mer generelle angrep lagt ut de siste ukene gjør det usannsynlig at SIDH kan reddes.
"Det var en spesiell følelse," sa Castryck, om enn en bittersøt en. "Vi drepte et av favorittsystemene våre."
Et vannskille øyeblikk
Det er umulig å garantere at et system er ubetinget sikkert. I stedet stoler kryptografer på at det går nok tid og at nok folk prøver å løse problemet til å føle seg trygge. "Det betyr ikke at du ikke vil våkne i morgen og oppdage at noen har funnet en ny algoritme for å gjøre det," sa Jeffrey Hoffstein, en matematiker ved Brown University.
Derfor er konkurranser som NISTs så viktige. I forrige runde av NIST-konkurransen utviklet Ward Beullens, en kryptograf hos IBM, et angrep som brøt et opplegg kalt Rainbow i en helg. I likhet med Castryck og Decru, var han bare i stand til å iscenesette angrepet sitt etter at han så på det underliggende matematiske problemet fra en annen vinkel. Og som angrepet på SIDH, brøt denne et system som var avhengig av annen matematikk enn de fleste foreslåtte post-kvanteprotokoller.
"De siste angrepene var et vannskille," sa Thomas Prest, en kryptograf ved oppstarten PQShield. De fremhever hvor vanskelig post-kvantekryptografi er, og hvor mye analyse som kan være nødvendig for å studere sikkerheten til ulike systemer. "Et matematisk objekt har kanskje ingen åpenbar struktur i ett perspektiv, og har en utnyttbar struktur i et annet," sa han. "Den vanskelige delen er å identifisere det riktige nye perspektivet."
