Om onze bankrekening of auto te beschermen tegen steeds krachtiger wordende quantumcomputers moeten we dringend op zoek naar nieuwe beveiliging. Ik brak één van de acht voorstellen met wiskunde. En een tien jaar oude pc.
5 juli 2022: Een Amerikaanse overheidsdienst kondigt de acht finale methodes aan waarvan we er in de nabije toekomst minstens twee zullen gebruiken om onze data te versleutelen. Eén van deze methodes lijkt al meer dan tien jaar immuun voor alle aanvallen. Ook Microsoft heeft veel vertrouwen in deze methode. Ze hebben een voorbeeld van de implementatie online staan met een beloning van $50.000 als je het kan kraken.
22 juli 2022: Als doctoraatstudent stuur ik samen met mijn supervisor Wouter Castryck een mail naar Microsoft om de beloning te claimen. Een pc die dringend aan vervanging toe is, slaagde er in de versleuteling te breken in slechts 85 seconden.
Gps in hogere dimensie
Deze versleuteling is gebaseerd op een pad vinden op een kaart waar je de weg niet kent. Het principe is: ga van punt A naar punt B. De enige moeilijkheid is dat er meer kruispunten op de kaart zijn dan atomen in het universum. Om punt B te bereiken zijn er weinig andere opties dan gewoon proberen alles af te lopen. De juiste wegbeschrijving (links, links, rechts, etc) is dan de sleutel van het beveiligingssysteem.
Echter, de kaart heeft ook een interpretatie op het snijpunt van algebra en meetkunde. Op zoek naar het gedrag van de kaart in hogere dimensies botste ik op een interessant resultaat. Het volstaat om één dimensie hoger te gaan om op elk kruispunt met zekerheid te kunnen zeggen of je links of rechts moet gaan aan de hand van algebra! En dit pad is exact de sleutel van het systeem.
Quantumdreiging
Maar waarom hebben we überhaupt nieuwe beveiligingsmethodes nodig? Wat is er mis met de huidige? Niks. Voorlopig toch niet. Al kan daar snel verandering in komen door de opkomst van steeds krachtigere quantumcomputers.
De huidige quantumcomputers zijn fysiek omvangrijk, maar nog niet op gebied van geheugen. Credit: IBM Research
Een quantumcomputer is een nieuw soort computer, gebouwd rond de wetten van de quantummechanica. Maar handig zijn ze nog niet echt. Bepaalde modellen kunnen bijvoorbeeld enkel werken bij een paar honderd graden onder nul. Bedrijven zoals Microsoft en IBM spenderen miljoenen aan onderzoek om ze sterker en praktischer te maken.
Een quantumcomputer is echter geen supercomputer die zomaar alles kan, maar hij is wel goed in specifieke taken oplossen. En helaas behoort het kraken van de huidige versleutelingsmethodes tot die taken.
Vermenigvuldigen voor gevorderden
In principe ligt wiskunde aan de basis van elke versleutelingsmethode. Daarbij moeten we gebruik maken van een gemakkelijke wiskundige bewerking die onwezenlijk moeilijk om te keren is. Zelfs niet met alle rekenkracht ter wereld.
Het bekendste voorbeeld hiervan is ongetwijfeld vermenigvuldigen. Wanneer je aan iemand zou vragen door welke getallen 31621 deelbaar is, zal die persoon eens goed in het haar krabben en je het antwoord schuldig blijven. Als je diezelfde persoon vraagt om 103 te vermenigvuldigen met 307 dan zal er mogelijks een zucht volgen, maar iedereen heeft in de lagere school geleerd hoe dit op te lossen met cijferen. De twee vragen zijn elkaars antwoord, maar de ene is duidelijk lastiger dan de andere.
Ook voor computers is een vermenigvuldiging uitvoeren doodeenvoudig, maar ze ongedaan maken is moeilijk zodra de getallen groot genoeg zijn. Cryptografen Ron Rivest, Adi Shamir en Leonard Adleman gebruikten dit in 1977 dan ook als inspiratie om hun versleutelingsmethode te publiceren. Hun methode is bijna 50 jaar oud, maar ze beveiligt nog dagelijks miljoenen toepassingen over de hele wereld.
Als je dit getal van 617 cijfers kan schrijven als product van 2 getallen van 309 cijfers ben je wereldberoemd. Maar de CIA zal ongetwijfeld plots geïnteresseerd zijn in jouw leven… Credit: Wikimedia
Sinds 1994 weten we dankzij de Amerikaanse wiskundige Peter Shor dat een quantumcomputer wél gemakkelijk een vermenigvuldiging ongedaan kan maken, en dus zitten we met een probleem. Gelukkig zijn quantumcomputers nog niet omvangrijk genoeg om dit al aan te kunnen. De grootste quantumcomputer heeft momenteel slechts een geheugen van 54 (quantum) bytes. Ter vergelijking: de eerste commerciële diskette uit 1972 had al 175.000 (gewone) bytes.
Ramp vermeden
Hoewel het dus nog even kan duren, moeten we de quantumdreiging niet onderschatten. Ontelbaar veel applicaties gebruiken versleutelingsmethodes, waardoor het jaren zou duren om alle nodige soft- en hardware te vervangen. Om de vijf jaar krijgen we bijvoorbeeld wel automatisch een nieuwe bankkaart toegestuurd. Maar als je na vijf jaar naar de garage gaat om gratis je auto te laten vervangen voor het nieuwste model zullen ze je eens goed uitlachen.
Daarom lanceerde het National Institute of Standards and Technology in 2016 al een oproep voor nieuwe versleutelingsmethodes die ook aanvallen van quantumcomputers kunnen weerstaan. Na vele jaren onderzoek kozen ze de acht methodes waarin de cryptografische wereld het meest vertrouwen had op gebied van zowel veiligheid als efficiëntie – niemand zit immers te wachten op een auto die twee minuten nodig heeft om te openen.
Samen met mijn collega brak ik niet veel later één van die acht methodes. Onze aanval veroorzaakte een schokgolf in de cryptografiewereld: een protocol dat zó lang zó goed stand had gehouden tegen alle aanvallen dat plots waardeloos bleek, was ongezien. Het vertrouwen voordien was immers zo groot dat het een reële kans maakte om op miljoenen toestellen geïmplementeerd te worden. Microsoft is dan wel $50.000 lichter, maar dat is een peulschil in vergelijking met de ramp en bijhorende kosten die werden vermeden.
Nasleep
Van de zeven overgebleven methodes lijkt het meeste vertrouwen te gaan naar drie beveiligingsmethodes die gebaseerd zijn op roosters. Roosters zijn collecties punten met een zekere regelmaat, die ook toepassingen hebben in bijvoorbeeld beeldverwerking. Beeldverwerking vindt plaats in 2D of 3D, waar alle relevante bewerkingen snel kunnen gebeuren. Maar wanneer je roosters in dimensie 1000 of hoger gebruikt, blijken ze ideaal om geheimen mee te verbergen!
Het zwarte punt in dit rooster vinden dat dichtst bij het rode punt ligt is gemakkelijk, maar in dimensie 1000 is dit (voorlopig nog?) onhaalbaar voor een quantumcomputer.
Ook het National Security Agency heeft zich al achter twee van deze beveiligingsmethodes op basis van roosters geschaard. De bedoeling is om deze tegen 2030 in gebruik te zien, en hopelijk volstaat dit om quantumcomputers te snel af te zijn.
Thomas Decru dingt mee naar de Vlaamse PhD Cup 2023. Ontdek meer over dit onderzoek op www.phdcup.be.
