Als de huidige cryptografieprotocollen zouden mislukken, zou het onmogelijk zijn om online verbindingen te beveiligen - om vertrouwelijke berichten te verzenden, veilige financiële transacties uit te voeren of gegevens te authenticeren. Iedereen had toegang tot alles; iedereen kon doen alsof hij iemand was. De digitale economie zou instorten.
Wanneer (of if) een volledig functionele kwantumcomputer beschikbaar komt, dat is precies wat er zou kunnen gebeuren. Als gevolg hiervan lanceerde het National Institute of Standards and Technology (NIST) van de Amerikaanse regering in 2017 een internationale wedstrijd om de beste manieren te vinden om "post-kwantum" cryptografie te bereiken.
Vorige maand koos het bureau zijn eerste groep winnaars: vier protocollen die, met enige herziening, zullen worden ingezet als een kwantumschild. Het maakte ook vier extra kandidaten bekend die nog in behandeling zijn.
Toen, op 30 juli, onthulden een paar onderzoekers dat ze... een van die kandidaten gebroken in een uur op een laptop. (Sindsdien hebben anderen de aanval nog sneller gemaakt, waardoor het protocol binnen enkele minuten werd verbroken.) "Een aanval die zo dramatisch en krachtig is... was nogal een schok," zei Steven Galbraith, een wiskundige en computerwetenschapper aan de Universiteit van Auckland in Nieuw-Zeeland. Niet alleen was de wiskunde die ten grondslag lag aan de aanval verrassend, maar het verminderde ook de (broodnodige) diversiteit van post-kwantumcryptografie - waardoor een versleutelingsprotocol werd geëlimineerd dat heel anders werkte dan de overgrote meerderheid van de schema's in de NIST-competitie.
"Het is een beetje jammer", zei Christoffel Peikert, een cryptograaf aan de Universiteit van Michigan.
De resultaten hebben de post-kwantumcryptografiegemeenschap zowel geschokt als aangemoedigd. Geschrokken, omdat deze aanval (en nog een uit een vorige ronde van de competitie) plotseling veranderde wat leek op een digitale stalen deur in natte krant. "Het kwam uit de lucht vallen", zei Dustin Moody, een van de wiskundigen die de NIST-standaardisatie-inspanningen leidde. Maar als een cryptografisch schema kapot gaat, is het het beste als het gebeurt ruim voordat het in het wild wordt gebruikt. "Er gaan veel emoties door je heen," zei David Jao, een wiskundige aan de Universiteit van Waterloo in Canada die samen met IBM-onderzoeker Luca De Feo, stelde het protocol in 2011 voor. Verrassing en teleurstelling horen daar zeker bij. "Maar ook," voegde Jao eraan toe, "het is nu tenminste gebroken."
Geheime wandelingen tussen bochten
Jao en De Feo hadden een kans gezien voor een cryptografisch systeem dat zowel vergelijkbaar was met, als duidelijk onderscheidde van bekende protocollen. Hun schema, het supersingular isogeny Diffie-Hellman-protocol (SIDH) genoemd, ging over elliptische krommen - dezelfde wiskundige objecten die worden gebruikt in een van de meest voorkomende soorten cryptografie die tegenwoordig worden gebruikt. Maar het gebruikte ze op een heel andere manier. Het was ook het meest compacte schema dat NIST in overweging nam (met de afweging dat het langzamer was dan veel van de andere kandidaten).
En "wiskundig gezien is het echt elegant", zei Jao. “Dat leek me toen een mooi idee.”
Stel dat twee partijen, Alice en Bob, in het geheim een bericht willen uitwisselen, zelfs onder het toeziend oog van een potentiële aanvaller. Ze beginnen met een verzameling punten verbonden door randen, een grafiek genoemd. Elk punt vertegenwoordigt een andere elliptische kromme. Als je de ene curve op een bepaalde manier in een andere kunt transformeren (via een kaart die isogenie wordt genoemd), teken dan een rand tussen het paar punten. De resulterende grafiek is enorm en je kunt er gemakkelijk in verdwalen: als je een relatief korte wandeling langs de randen maakt, kom je uit op een plek die er volkomen willekeurig uitziet.
De grafieken van Alice en Bob hebben allemaal dezelfde punten, maar de randen zijn verschillend - ze worden gedefinieerd door verschillende isogenieën. Alice en Bob beginnen op hetzelfde punt en ze springen elk langs willekeurige randen op hun eigen grafiek, waarbij ze hun pad van het ene punt naar het andere bijhouden. Elk publiceert vervolgens hun eindlocatie, maar houdt hun pad geheim.
Nu wisselen ze van plaats: Alice gaat naar het laatste punt van Bob en Bob naar dat van Alice. Elk herhaalt hun geheime wandeling. Dit doen ze op zo'n manier dat ze allebei op hetzelfde punt uitkomen.
Deze locatie is in het geheim gevonden, zodat Alice en Bob deze als hun geheime sleutel kunnen gebruiken - informatie waarmee ze elkaars berichten veilig kunnen versleutelen en ontsleutelen. Zelfs als een aanvaller de tussenliggende punten ziet die Alice en Bob elkaar sturen, kennen ze de geheime wandeling van Alice of Bob niet, dus kunnen ze dat laatste eindpunt niet achterhalen.
Maar om SIDH te laten werken, moeten Alice en Bob ook wat aanvullende informatie over hun wandelingen uitwisselen. Die extra informatie heeft geleid tot de ondergang van SIDH.
Een nieuwe draai aan oude wiskunde
Thomas Decru was niet van plan om SIDH te breken. Hij probeerde erop voort te bouwen - om de methode te veralgemenen om een ander type cryptografie te verbeteren. Dat lukte niet, maar het leidde tot een idee: zijn aanpak zou nuttig kunnen zijn voor het aanvallen van SIDH. En dus benaderde hij Wouter Castryck, zijn collega aan de Katholieke Universiteit van Leuven in België en een van zijn voormalige doctoraatsadviseurs, en de twee doken in de relevante literatuur.
Ze struikelden over een paper gepubliceerd door de wiskundige Ernst Kani in 1997. Daarin stond een stelling die 'bijna onmiddellijk van toepassing was op SIDH', zei Castryck. "Ik denk dat toen we ons realiseerden dat... de aanval vrij snel kwam, in een of twee dagen."
Om Alice' geheime wandeling (en dus de gedeelde sleutel) terug te krijgen, onderzochten Castryck en Decru uiteindelijk het product van twee elliptische curven: de startcurve van Alice en de curve die ze publiekelijk naar Bob stuurde. Die combinatie produceert een soort oppervlak dat een abels oppervlak wordt genoemd. Vervolgens gebruikten ze deze abelse oppervlakken, de stelling van Kani (die abelse oppervlakken in verband brengt met elliptische krommen), en de extra informatie die Alice aan Bob gaf om elke stap die Alice nam te ontdekken.
"Het is bijna als een homing-signaal waarmee je kunt vergrendelen op [bepaalde abelse oppervlakken]," zei Jao. "En dat signaal vertelt je dat dit de manier is waarop je moet gaan om de volgende stap te zetten om de juiste [geheime wandeling] te vinden." Wat hen rechtstreeks naar de gedeelde sleutel van Alice en Bob leidde.
"Het is een zeer onverwachte benadering, naar meer gecompliceerde objecten gaan om resultaten af te leiden over het eenvoudigere object," zei Jao.
"Ik was erg opgewonden om te zien dat deze techniek werd gebruikt," zei Kristin Lauter, een wiskundige en cryptograaf bij Meta AI Research die niet alleen heeft geholpen bij het ontwikkelen van op isogenie gebaseerde cryptografie, maar ook heeft gewerkt aan abelse oppervlakken. "Ik schaam me zo dat ik er niet aan denk als een manier om [het] te breken."
De aanval van Castryck en Decru brak de laagst beveiligde versie van het SIDH-protocol in 62 minuten en het hoogste beveiligingsniveau in iets minder dan een dag. Kort daarna paste een andere expert de aanval aan, zodat het slechts 10 minuten duurde om de laagbeveiligde versie te doorbreken en een paar uur om de zwaarbeveiligde versie te doorbreken. Meer algemene aanvallen geplaatst in de afgelopen weken maken het onwaarschijnlijk dat SIDH kan worden geborgen.
"Het was een speciaal gevoel", zei Castryck, zij het een bitterzoete. "We hebben een van onze favoriete systemen vermoord."
Een keerpunt
Het is onmogelijk om te garanderen dat een systeem onvoorwaardelijk veilig is. In plaats daarvan vertrouwen cryptografen op voldoende tijd die verstrijkt en genoeg mensen die proberen het probleem te doorbreken om zich zelfverzekerd te voelen. "Dat betekent niet dat je morgen niet wakker wordt en ontdekt dat iemand een nieuw algoritme heeft gevonden om het te doen," zei Jeffrey Hofstein, een wiskundige aan de Brown University.
Daarom zijn wedstrijden zoals NIST's zo belangrijk. In de vorige ronde van de NIST-competitie bedacht Ward Beullens, een cryptograaf bij IBM, een aanval die brak een plan genaamd Rainbow in een weekend. Net als Castryck en Decru kon hij zijn aanval pas in scène zetten nadat hij het onderliggende wiskundige probleem vanuit een andere hoek had bekeken. En net als de aanval op SIDH brak deze een systeem dat op andere wiskunde vertrouwde dan de meeste voorgestelde post-kwantumprotocollen.
“De recente aanslagen waren een keerpunt”, zei Thomas Perst, een cryptograaf bij de startup PQShield. Ze benadrukken hoe moeilijk post-kwantumcryptografie is en hoeveel analyse nodig kan zijn om de beveiliging van verschillende systemen te bestuderen. "Een wiskundig object heeft misschien geen duidelijke structuur in het ene perspectief en een exploiteerbare structuur in een ander perspectief", zei hij. "Het moeilijkste is om het juiste nieuwe perspectief te identificeren."
