Cryptografen vrezen quantumcomputer

De quantumcomputer is er nog (lang) niet, maar mocht de ontwikkeling in een stroomversnelling komen, dan is het gedaan met de cryptografie die momenteel het fundament van veilige communicatie vormt. Cryptografen zijn zich dus aan het voorbereiden op een nieuwe tijd.

“We zijn reeds benaderd door nationale veiligheidsdiensten met het verzoek om werk te gaan maken van een volgende generatie cryptografische algoritmes die bestand is tegen aanvallen door quantumcomputers, op een termijn van twee decennia. Zo anticiperen we op het einde van RSA-cryptografie.”

Heldere taal van Thierry Breton, de ceo van computerbedrijf Atos, een van de grootste exploitanten van datacentra ter wereld. Toegegeven, Breton deed zijn uitspraak bij de presentatie vlak voor de zomer van een nieuwe supercomputer die speciaal ontworpen is om de quantumcomputer te simuleren. Het maakte dus deel uit van een verkooppraatje: koop onze computer voor je onderzoek (naar quantumbestendige cryptomethoden). Maar onzin was het bepaald niet.

Post-quantum cryptografie heet dit rap groeiende onderzoeksgebied. Niet te verwarren met quantumcryptografie. Dit laatste staat voor de inzet van quantummethoden om berichten te versleutelen. Post-quantumcryptografie betreft methoden voor gewone computers die berichten zo versleutelen dat ze bestand zijn tegen kraakpogingen door quantumcomputers.

Brute force

Even een stapje terug: wat is precies het probleem? Welnu, de huidige generatie zogeheten asymmetrische algoritmen is gebaseerd op een beperkt aantal wiskundige problemen waarvan de oplossingsruimte met het efficiëntste algoritme meer dan polynomiaal (vaak exponentieel) toeneemt met de omvang ervan. Een bekend voorbeeld is het ontleden van een groot getal in zijn factoren, het factorisatieprobleem. Daar bestaan diverse algoritmen voor, maar bij steeds grotere getallen neemt de benodigde rekenkracht razendsnel toe.

In cryptografische termen betekent dit dat een algoritme op basis van het factorisatieprobleem (zoals het populaire RSA dat achter het groene slotje in de browser schuil gaat), mits deugdelijk geïmplementeerd, eigenlijk niet kraakbaar is. Wanneer computers krachtiger worden, verleng je de sleutel en ben je klaar. In de jaren negentig was de sleutel van RSA meestal 128 cijfers lang. Die valt nu op een pc in afzienbare tijd te kraken. Sleutels zijn inmiddels duizenden bits lang.

De wet van Moore, die eens in de anderhalf jaar een verdubbeling van de rekenkracht voorspelt, is geen bedreiging voor RSA. Die rekenkracht kun je ook inzetten voor cryptografie met een langere sleutel. Supercomputers zijn miljoenen malen sneller dan een pc, maar ook dat is oplosbaar met een sleutelverlenging.

Echter, in 1994 vond de Amerikaanse wiskundige Peter Shor een nieuw, efficiënter algoritme voor het factorisatieprobleem. Daarmee steeg de kraaktijd niet meer explosief bij verlenging van de sleutel. Shors algoritme werkt niet op een gewone computer, maar wel op een quantumcomputer. Dus als die er komt, is RSA kapot. Dat kan echter nog rustig enkele tientallen jaren duren. Het hoogste door een quantumcomputer in factoren ontbonden getal is op dit moment 143, maar er zijn geen principiële beperkingen en in de ICT kunnen ontwikkelingen zomaar in een stroomversnelling komen.

Vanwege het kostenplaatje zullen de eerste quantumcomputers bovendien grotendeels (maar allicht niet exclusief) in handen zijn van overheden. Logisch dus dat veiligheidsdiensten, inclusief de Nederlandse NCSC, nerveus worden bij de gedachte eraan. Michael McCaul, voorzitter van de commissie voor nationale veiligheid in het Amerikaanse huis van afgevaardigden, hintte tijdens een lezing eerder dit jaar dat quantum-inspanningen nodig zijn om de Verenigde Staten te behoeden voor Russische aanvallen.

Radioactief

Toch moeten ons nu al ongerust maken, stelt de Eindhovense hoogleraar cryptografie Tanja Lange, die leiding geeft aan het Europese onderzoeksconsortium PQcrypto. ‘Informatie die we nu met RSA versleutelen zal tegen die tijd kraakbaar zijn. Dus moeten we ons afvragen hoe erg dat is. Ik heb bijvoorbeeld contact met een organisatie die radioactief afval opslaat. Dat gebeurt uiteraard op een fysiek veilige manier, maar er zit ook een digitale beveiligingscomponent in. De quantumcomputer valt binnen hun tijdshorizon, dus zij kijken nu al naar alternatieven voor RSA en bestaande equivalenten daarvan.’

Die alternatieven zijn er namelijk, soms al heel lang. Het McEliece systeem, bijvoorbeeld, dateert uit 1978, hetzelfde jaar als RSA. In plaats van factorisatie gebruikt het een ander wiskundig probleem in de hoogste complexiteitsklasse. Het is razendsnel, maar heeft als groot nadeel dat je één megabyte aan informatie moet uitwisselen voor je aan iets anders toekomt. Dat was voor het netwerk van 1978 volstrekt onacceptabel (en nu soms ook nog). Maar als je zeker wilt weten dat je vaatjes uranium nog op hun plek staan, is een hobbel van één megabyte in het communicatiekanaal alleszins aanvaardbaar. Dus is een cryptografisch protocol op basis van McEliece voor dit doel in de maak.

‘McEliece is een voorbeeld van een systeem met een relatief hoge betrouwbaarheid, omdat het al zo lang bestaat, maar met praktische bezwaren’, vertelt Lange, die in de speciale quantumcomputer-editie van het tijdschrift Nature half september een overzichtsartikel over het vakgebied schreef. ‘Daartegenover staan methoden die licht en snel zijn, maar nieuwer en dus minder goed getest. Dat laatste moet wel gebeuren.’

Kandidaat-standaard

Het is wat te simplistisch om te stellen dat een methode óf kraakbaar is óf niet. In het McEliece systeem zijn wel eens kwetsbaarheden ontdekt, maar die gaten zijn ook weer gedicht. Een van de meest belovende nieuwe systemen, NTRU, heeft een nogal hectische geschiedenis van lekken en reparaties. Voor een ander nieuw systeem bleek na vijf jaar onderzoek echter een quantum-algoritme te bestaan dat het definitief onbruikbaar maakte.

Vandaar de grote behoefte aan wiskundigen die zich over bestaande alternatieven buigen of er zelf een verzinnen. Het Amerikaanse National Institute of Standards and Technology (NIST) heeft momenteel een oproep uitstaan om kandidaat-standaarden in te leveren voor toekomstige methoden. De verwachting is dat dit meer focus in het onderzoek zal brengen, omdat duidelijk wordt wat de interessantste algoritmen zijn. Overigens zijn de Amerikanen zelf, anders dan Europeanen en Canadezen, niet goed vertegenwoordigd in publiek onderzoek naar nieuwe methoden.

Lange: ‘Toen we een tien jaar geleden een eerste conferentie over post-quantumcryptografie hielden, waren er evenveel sprekers als toehoorders. Afgelopen zomer hadden we een conferentie met 23 sprekers en tien keer zoveel toehoorders. De belangstelling neemt dus toe, al zijn er wereldwijd nog altijd niet meer dan een paar honderd mensen actief mee bezig.’

Updates

Naast fundamentele vragen over wiskundige houdbaarheid van een post-quantumalgoritme zijn er ook veel praktische voorwaarden waaraan het moet voldoen om werkbaar te zijn. Het moet niet teveel processorkracht en bandbreedte vragen. Dat is ook een kwestie van een efficiënte vertaling van de wiskundige principes naar software. Bij die vertaalstap kunnen ook weer kwetsbaarheden in de code belanden die niet inherent zijn aan het algoritme zelf.

Heb je eenmaal een sluitend algoritme en een waterdichte implementatie daarvan, dan ben je er nog niet, legt Daniel Bernstein, hoogleraar cryptografische implementaties aan de University of Illinois at Chicago, uit: ‘Toen het voor digitale handtekeningen gebruikte MD5-algoritme in diskrediet raakte, ging Microsoft op zoek naar alle plekken waar het in Windows werd gebruikt. Dat bleken er 800 te zijn. Als je een algoritme moet updaten is dat dus een hele klus. Als gevolg daarvan zijn softwarefabrikanten huiverig om nieuwe methoden te implementeren als ze niet heel zeker van hun zaak zijn.’

Omdat het overgrote deel van de Windows pc’s op internet is aangesloten en de cryptografie softwarematig geïmplementeerd, is een update daarvan nog relatief eenvoudig. De laatste (en zeker ook de komende) jaren wordt echter een enorme hoeveelheid aan sensoren en andere internet-of-things-gadgets over de wereld uitgestrooid. Daar zit een deel van de cryptografie hardwarematig in, bijvoorbeeld in de vorm van een speciale coprocessor, omdat die energie-efficiënt is. Nu hebben de meeste sensoren niet de levensduur van nucleair afval, maar je zult altijd zien dat een vergeten sensor ergens door een hacker ontdekt wordt om een heel systeem open te peuteren. In juli werden op deze manier de sensoren in het aquarium van een Amerikaans casino gebruikt als toegangspoort om tien gigabyte aan informatie uit het netwerk te stelen.

Zo lang dit soort kraken ook zonder quantumcomputer te zetten zijn, zal de gemiddelde internetgebruiker zich weinig zorgen maken over een geavanceerd apparaat dat misschien pas over tientallen jaren voor een kleine groep beschikbaar is. Maar mocht het zover komen, zal hij blij zijn dat er mensen over hebben nagedacht.

×