Hvis nutidens kryptografiprotokoller skulle fejle, ville det være umuligt at sikre onlineforbindelser - at sende fortrolige beskeder, foretage sikre økonomiske transaktioner eller autentificere data. Enhver kunne få adgang til hvad som helst; enhver kunne udgive sig for at være hvem som helst. Den digitale økonomi ville bryde sammen.
Når (eller if) bliver en fuldt funktionel kvantecomputer tilgængelig, det er præcis, hvad der kunne ske. Som et resultat lancerede den amerikanske regerings National Institute of Standards and Technology (NIST) i 2017 en international konkurrence for at finde de bedste måder at opnå "post-kvante" kryptografi.
I sidste måned valgte agenturet sin første gruppe af vindere: fire protokoller, der med en vis revision vil blive implementeret som et kvanteskjold. Den annoncerede også fire yderligere kandidater, der stadig er under overvejelse.
Så den 30. juli afslørede et par forskere, at de havde knækket en af disse kandidater om en time på en bærbar computer. (Siden da har andre gjort angrebet endnu hurtigere og brudt protokollen i løbet af få minutter.) "Et angreb, der er så dramatisk og kraftfuldt ... var noget af et chok," sagde Steven Galbraith, en matematiker og datalog ved University of Auckland i New Zealand. Ikke alene var matematikken, der lå til grund for angrebet, overraskende, men det reducerede den (højt tiltrængte) mangfoldighed af post-kvantekryptografi - eliminerede en krypteringsprotokol, der fungerede meget anderledes end langt de fleste ordninger i NIST-konkurrencen.
"Det er lidt af en bummer," sagde Christopher Peikert, en kryptograf ved University of Michigan.
Resultaterne har efterladt post-kvantekryptografisamfundet både rystet og opmuntret. Rystet, fordi dette angreb (og et andet fra en tidligere runde af konkurrencen) pludselig forvandlede, hvad der lignede en digital ståldør, til våd avis. "Det kom ud af det blå," sagde Dustin Moody, en af matematikerne, der leder NIST-standardiseringsindsatsen. Men hvis en kryptografisk ordning går i stykker, er det bedst, hvis det sker i god tid, før det bliver brugt i naturen. "Der er mange følelser, der går igennem dig," sagde David Jao, en matematiker ved University of Waterloo i Canada, der sammen med IBM-forsker Luca De Feo, foreslog protokollen i 2011. Der er bestemt overraskelse og skuffelse blandt dem. "Men også," tilføjede Jao, "den er i det mindste gået i stykker nu."
Hemmelige vandreture blandt kurver
Jao og De Feo havde set en mulighed for et kryptografisk system, der både lignede og var passende adskilt fra velkendte protokoller. Deres skema, kaldet supersingular isogeny Diffie-Hellman protokol (SIDH), beskæftigede sig med elliptiske kurver - de samme matematiske objekter, der bruges i en af de mest udbredte typer kryptografi, der er implementeret i dag. Men det brugte dem på en helt anden måde. Det var også den mest kompakte ordning, som NIST overvejede (med den afvejning, at den var langsommere end mange af de andre kandidater).
Og "matematisk er det virkelig elegant," sagde Jao. "På det tidspunkt virkede det som en smuk idé."
Lad os sige, at to parter, Alice og Bob, ønsker at udveksle en besked i hemmelighed, selv under et vågent blik fra en potentiel angriber. De begynder med en samling af punkter forbundet af kanter kaldet en graf. Hvert punkt repræsenterer en anden elliptisk kurve. Hvis du kan transformere en kurve til en anden på en bestemt måde (via et kort kaldet en isogeni), skal du tegne en kant mellem punktparret. Den resulterende graf er enorm og let at fare vild i: Hvis du tager en forholdsvis kort tur langs dens kanter, ender du et sted, der ser helt tilfældigt ud.
Alices og Bobs grafer har alle de samme punkter, men kanterne er forskellige - de er defineret af forskellige isogenier. Alice og Bob starter på samme punkt, og de hopper hver især langs tilfældige kanter på deres egen graf og holder styr på deres vej fra et punkt til et andet. Hver offentliggør derefter deres slutplacering, men holder deres vej hemmelig.
Nu bytter de plads: Alice går til Bobs sidste punkt, og Bob til Alices. Hver gentager deres hemmelige gang. Det gør de på en sådan måde, at de begge ender på samme punkt.
Denne placering er blevet fundet i det skjulte, så Alice og Bob kan bruge den som deres hemmelige nøgle - information, der giver dem mulighed for at kryptere og dekryptere hinandens beskeder sikkert. Selvom en angriber ser de mellemliggende punkter, som Alice og Bob sender hinanden, kender de ikke Alices eller Bobs hemmelige gang, så de kan ikke finde ud af det sidste endepunkt.
Men for at få SIDH til at fungere, skal Alice og Bob også udveksle nogle yderligere oplysninger om deres gåture. Den ekstra information er det, der førte til SIDH's fald.
Et nyt twist på gammel matematik
Thomas Decru satte sig ikke for at bryde SIDH. Han forsøgte at bygge videre på det - at generalisere metoden for at forbedre en anden form for kryptografi. Det lykkedes ikke, men det udløste en idé: Hans tilgang kan være nyttig til at angribe SIDH. Og så nærmede han sig Wouter Castryck, hans kollega ved det katolske universitet i Leuven i Belgien og en af hans tidligere doktorgradsrådgivere, og de to dykkede ned i den relevante litteratur.
De faldt over et papir udgivet af matematikeren Ernst Kani i 1997. I det var et teorem, der "næsten umiddelbart kunne anvendes på SIDH," sagde Castryck. "Jeg tror, når vi indså, at... angrebet kom ret hurtigt, på en eller to dage."
Til sidst, for at genvinde Alices hemmelige gang (og derfor den delte nøgle), undersøgte Castryck og Decru produktet af to elliptiske kurver - Alices startkurve og kurven, hun sendte offentligt til Bob. Den kombination producerer en slags overflade kaldet en abelsk overflade. De brugte derefter disse abelske overflader, Kanis sætning (som relaterer abelske overflader til elliptiske kurver), og den ekstra information Alice gav Bob for at afdække hvert skridt Alice tog.
"Det er næsten som et målsøgningssignal, der lader dig låse ind på [visse abelske overflader]," sagde Jao. "Og det signal fortæller dig, at det er den vej, du skal gå for at tage det næste skridt for at finde den rigtige [hemmelige gåtur]." Hvilket førte dem direkte til Alice og Bobs fælles nøgle.
"Det er en meget uventet tilgang, at gå til mere komplicerede objekter for at udlede resultater om det enklere objekt," sagde Jao.
"Jeg var meget spændt på at se denne teknik blive brugt," sagde Kristin Lauter, en matematiker og kryptograf hos Meta AI Research, som ikke kun hjalp med at udvikle isogeni-baseret kryptografi, men også har arbejdet på abelske overflader. "Så skam mig over ikke at tænke på det som en måde at bryde [det]."
Castryck og Decrus angreb brød den laveste sikkerhedsversion af SIDH-protokollen på 62 minutter og det højeste sikkerhedsniveau på knap en dag. Så kort efter justerede en anden ekspert angrebet, så det tog kun 10 minutter at bryde lavsikkerhedsversionen og et par timer at bryde højsikkerhedsversionen. Mere generelle angreb udgivet i de sidste par uger gøre det usandsynligt, at SIDH kan reddes.
"Det var en speciel følelse," sagde Castryck, omend en bittersød en. "Vi dræbte et af vores yndlingssystemer."
Et vandskeløjeblik
Det er umuligt at garantere, at et system er ubetinget sikkert. I stedet stoler kryptografer på, at der går nok tid, og at nok mennesker forsøger at bryde problemet til at føle sig trygge. "Det betyder ikke, at du ikke vågner i morgen og opdager, at nogen har fundet en ny algoritme til at gøre det," sagde Jeffrey Hoffstein, matematiker ved Brown University.
Derfor er konkurrencer som NIST's så vigtige. I den forrige runde af NIST-konkurrencen udtænkte Ward Beullens, en kryptograf hos IBM, et angreb, der brød en ordning kaldet Rainbow i en weekend. Ligesom Castryck og Decru var han kun i stand til at iscenesætte sit angreb, efter at han så det underliggende matematiske problem fra en anden vinkel. Og ligesom angrebet på SIDH, brød denne et system, der var afhængig af anden matematik end de fleste foreslåede post-kvanteprotokoller.
"De seneste angreb var et skelsættende øjeblik," sagde Thomas Prest, en kryptograf ved opstarten PQShield. De fremhæver, hvor vanskelig post-kvantekryptografi er, og hvor meget analyse der kan være nødvendig for at studere sikkerheden i forskellige systemer. "Et matematisk objekt har muligvis ingen åbenlys struktur i ét perspektiv og har en udnyttelig struktur i et andet," sagde han. "Den svære del er at identificere det rigtige nye perspektiv."
