Om dagens kryptografiprotokoll skulle misslyckas skulle det vara omöjligt att säkra onlineanslutningar – att skicka konfidentiella meddelanden, göra säkra finansiella transaktioner eller autentisera data. Vem som helst kunde komma åt vad som helst; vem som helst kunde låtsas vara vem som helst. Den digitala ekonomin skulle kollapsa.
När (eller if) en fullt fungerande kvantdator blir tillgänglig, det är precis vad som kan hända. Som ett resultat lanserade den amerikanska regeringens National Institute of Standards and Technology (NIST) 2017 en internationell tävling för att hitta de bästa sätten att uppnå "postkvant"-kryptering.
Förra månaden valde byrån sin första grupp av vinnare: fyra protokoll som, med viss revidering, kommer att användas som en kvantsköld. Den tillkännagav också fyra ytterligare kandidater som fortfarande övervägs.
Sedan den 30 juli avslöjade ett par forskare att de hade brutit en av dessa kandidater om en timme på en bärbar dator. (Sedan dess har andra gjort attacken ännu snabbare och brutit mot protokollet på några minuter.) "En attack som är så dramatisk och kraftfull ... var ganska chock," sa Steven Galbraith, en matematiker och datavetare vid University of Auckland i Nya Zeeland. Inte bara var matematiken som låg bakom attacken överraskande, utan den minskade den (välbehövliga) mångfalden av post-kvantkryptografi – eliminerade ett krypteringsprotokoll som fungerade mycket annorlunda än de allra flesta system i NIST-tävlingen.
"Det är lite av en bummer," sa Christopher Peikert, en kryptograf vid University of Michigan.
Resultaten har gjort post-kvantkryptografin både skakad och uppmuntrad. Skakad, eftersom denna attack (och en annan från en tidigare omgång av tävlingen) plötsligt förvandlade vad som såg ut som en digital ståldörr till våt tidning. "Det kom ur det blå," sa Dustin Moody, en av matematikerna som leder NIST-standardiseringsarbetet. Men om ett kryptografiskt system kommer att gå sönder, är det bäst om det händer långt innan det används i naturen. "Det är många känslor som går igenom dig," sa David Jao, en matematiker vid University of Waterloo i Kanada som tillsammans med IBM-forskare Luca De Feo, föreslog protokollet 2011. Visst är överraskning och besvikelse bland dem. "Men också," tillade Jao, "den gick åtminstone sönder nu."
Hemliga promenader bland kurvor
Jao och De Feo hade sett en möjlighet för ett kryptografiskt system som både liknade och var lämpligt skilt från välkända protokoll. Deras schema, kallat supersingular isogeny Diffie-Hellman-protokollet (SIDH), handlade om elliptiska kurvor - samma matematiska objekt som används i en av de mest utbredda typerna av kryptografi som används idag. Men det använde dem på ett helt annat sätt. Det var också det mest kompakta systemet som NIST övervägde (med avvägningen att det var långsammare än många av de andra kandidaterna).
Och "matematiskt är det verkligen elegant", sa Jao. "På den tiden verkade det som en vacker idé."
Säg att två parter, Alice och Bob, vill utbyta ett meddelande i hemlighet, även under en potentiell angripares vaksamma blick. De börjar med en samling punkter förbundna med kanter som kallas en graf. Varje punkt representerar en annan elliptisk kurva. Om du kan omvandla en kurva till en annan på ett speciellt sätt (via en karta som kallas isogeni), rita en kant mellan punktparet. Den resulterande grafen är enorm och lätt att gå vilse i: Om du tar en relativt kort promenad längs dess kanter hamnar du någonstans som ser helt slumpmässig ut.
Alices och Bobs grafer har alla samma punkter, men kanterna är olika - de definieras av olika isogener. Alice och Bob börjar vid samma punkt, och de hoppar var och en längs slumpmässiga kanter på sin egen graf och håller reda på sin väg från en punkt till en annan. Var och en publicerar sedan sin slutplats men håller sin väg hemlig.
Nu byter de plats: Alice går till Bobs sista punkt och Bob till Alices. Var och en upprepar sin hemliga promenad. De gör detta på ett sådant sätt att de båda kommer att hamna på samma punkt.
Den här platsen har hittats i hemlighet, så Alice och Bob kan använda den som sin hemliga nyckel – information som gör att de kan kryptera och dekryptera varandras meddelanden på ett säkert sätt. Även om en angripare ser de mellanliggande punkterna som Alice och Bob skickar till varandra, känner de inte till Alices eller Bobs hemliga vandring, så de kan inte ta reda på den sista slutpunkten.
Men för att få SIDH att fungera behöver Alice och Bob också utbyta lite ytterligare information om sina promenader. Den extra informationen är det som ledde till SIDH:s fall.
En ny vändning på gammal matematik
Thomas Decru ville inte bryta SIDH. Han försökte bygga vidare på det - att generalisera metoden för att förbättra en annan typ av kryptografi. Det fungerade inte, men det väckte en idé: hans tillvägagångssätt kan vara användbart för att attackera SIDH. Och så närmade han sig Wouter Castryck, hans kollega vid katolska universitetet i Leuven i Belgien och en av hans tidigare doktorandrådgivare, och de två dök ner i relevant litteratur.
De snubblade över en tidning publicerad av matematikern Ernst Kani 1997. I det fanns ett teorem som "nästan omedelbart var tillämpligt på SIDH", sa Castryck. "Jag tror att när vi insåg att... attacken kom ganska snabbt, på en eller två dagar."
Till slut, för att återställa Alices hemliga promenad (och därför den delade nyckeln), undersökte Castryck och Decru produkten av två elliptiska kurvor - Alices startkurva och kurvan som hon skickade offentligt till Bob. Den kombinationen ger en sorts yta som kallas en abelisk yta. De använde sedan dessa abelska ytor, Kanis teorem (som relaterar abelska ytor till elliptiska kurvor), och den extra information Alice gav Bob för att avslöja varje steg Alice tog.
"Det är nästan som en referenssignal som låter dig låsa in på [vissa abeliska ytor]," sa Jao. "Och den signalen talar om för dig att det är den här vägen du bör gå för att ta nästa steg för att hitta rätt [hemlig promenad]." Vilket ledde dem direkt till Alice och Bobs delade nyckel.
"Det är ett mycket oväntat tillvägagångssätt, att gå till mer komplicerade objekt för att få resultat om det enklare objektet," sa Jao.
"Jag var väldigt glad över att se den här tekniken användas," sa Kristin Lauter, en matematiker och kryptograf vid Meta AI Research som inte bara hjälpte till att utveckla isogeni-baserad kryptografi utan också har arbetat på abelska ytor. "Så skäms på mig för att jag inte tänker på det som ett sätt att bryta [det]."
Castryck och Decrus attack bröt den lägsta säkerhetsversionen av SIDH-protokollet på 62 minuter och den högsta säkerhetsnivån på knappt ett dygn. Sedan, kort efteråt, finjusterade en annan expert attacken så att det tog bara 10 minuter att bryta lågsäkerhetsversionen och ett par timmar att bryta högsäkerhetsversionen. Mer allmänna attacker postat under de senaste veckorna gör det osannolikt att SIDH kan räddas.
"Det var en speciell känsla", sa Castryck, om än bitterljuv. "Vi dödade ett av våra favoritsystem."
Ett vattendrag
Det är omöjligt att garantera att ett system är ovillkorligt säkert. Istället förlitar sig kryptografer på att tillräckligt med tid går och att tillräckligt många människor försöker bryta problemet för att känna sig trygga. "Det betyder inte att du inte kommer att vakna imorgon och upptäcka att någon har hittat en ny algoritm för att göra det," sa Jeffrey Hoffstein, en matematiker vid Brown University.
Därför är tävlingar som NISTs så viktiga. I den föregående omgången av NIST-tävlingen utarbetade Ward Beullens, en kryptograf på IBM, en attack som bröt ett system som heter Rainbow på en helg. Precis som Castryck och Decru kunde han iscensätta sin attack först efter att han sett det underliggande matematiska problemet från en annan vinkel. Och precis som attacken på SIDH, bröt den här ett system som förlitade sig på annan matematik än de flesta föreslagna post-kvantprotokoll.
"De senaste attackerna var en vattendelare", sa Thomas Prest, en kryptograf vid uppstarten PQShield. De belyser hur svårt postkvantkryptografi är och hur mycket analys som kan behövas för att studera säkerheten i olika system. "Ett matematiskt objekt kanske inte har någon uppenbar struktur i ett perspektiv, och har en exploateringsbar struktur i ett annat," sa han. "Det svåra är att identifiera rätt nya perspektiv."
