De dreiging van quantumcomputers

We maken met ons allen al eeuwen gebruik van encryptie. Door de komst van de computer is het gebruik daarvan aan de ene kant eenvoudiger geworden, aan de andere kant is het ook eenvoudiger om zwakke algoritmes te kraken. Er zijn door de jaren heen verschillende moderne encryptiealgoritmes ontstaan, aangevoerd door DES in de jaren zeventig. Daar zijn intussen de nodige gaten in geschoten en daarom doen we het nog steeds met de opvolger AES, dat zijn intrede deed in 2001. Dit algoritme mag dan nog steeds de koning zijn op het gebied van symmetrische encryptie, we maken ook dagelijks veelvuldig gebruik van een andere soort.

De jaren zeventig waren namelijk ook het toneel van een andere ontwikkeling op het gebied van encryptie: asymmetrische cryptografie. Deze moest een oplossing bieden voor het probleem van sleuteldistributie. Bij AES vinden encryptie en decryptie immers plaats aan de hand van dezelfde sleutel, wat tot problemen leidt als je de sleutel op een veilige manier met iemand wilt delen. De onderzoekers Whitfield Diffie en Martin E. Hellman presenteerden in 1976 hun paper New Directions in Cryptography, waarin ze de basis legden voor publiekesleutelcryptografie. Ze introduceerden het concept van een sleutelpaar met een publieke en een privésleutel, die onderling in wiskundig verband staan met elkaar. Op internet wordt dit principe veelvuldig gebruikt, bijvoorbeeld om https-verbindingen van encryptie te voorzien, maar ook om WhatsApp-chats te versleutelen.

'Broken Rusty Lock', Nick Carter, CC BY 2.0

In de loop van de tijd zijn er verschillende aanvallen op het sleuteluitwisselingsprotocol van de twee wetenschappers verschenen, zoals Logjam. Tot nu is er echter nog geen aanval verschenen die de veiligheid van het volledige systeem ondermijnt. Toch weten we nu al dat veelgebruikte cryptosystemen als rsa en ecdsa een risico lopen door de komst van quantumcomputers, doordat ze gebruikmaken van wiskundige problemen die met behulp van een dergelijk systeem en de nodige algoritmes eenvoudig zijn op te lossen.

Daarom zouden we nu al actie moeten ondernemen, zo luiden de adviezen van wetenschappers en organisaties. Het is dan ook niet toevallig dat donderdag een deadline van het Amerikaanse NIST verliep om nieuwe cryptografische systemen in te sturen die ook tegen quantumcomputers zijn opgewassen. Het instituut maakte bekend dat het 82 inzendingen heeft gekregen van 75 universiteiten, 30 bedrijven en 10 overheidsorganisaties. De ingestuurde voorstellen worden besproken op de eerste conferentie voor de standaardisatie van deze ‘post-quantumcryptografie’, die in april plaatsvindt in Florida. Resultaten worden pas over drie tot vijf jaar verwacht. Genoeg aanleiding om eens op de achterliggende problematiek in te gaan en de effecten van quantumcomputers op encryptie nader te onderzoeken.

Tweakers sprak met wetenschapper Christian Schaffner over de komst van quantumcomputers en de gevolgen voor huidige vormen van encryptie. Schaffner is werkzaam bij de Universiteit van Amsterdam als universitair docent op het gebied van cryptografie en is betrokken bij QuSoft, het onderzoekscentrum voor quantumsoftware binnen het Centrum voor Wiskunde en Informatica, oftewel CWI. Daar houdt hij zich bezig met zowel de 'aanvallende' als de 'verdedigende' kant van quantumcryptografie. Het eerste betreft bijvoorbeeld het breken van versleuteling. Een voorbeeld van het verdedigende aspect is quantum key distribution, oftewel sleuteluitwisseling op quantumniveau.

Op de vraag of het nog onzeker is of quantumcomputers eraan komen en of ze een bedreiging voor encryptie vormen, antwoordt hij dat de wetenschappelijke consensus inmiddels wel is dat er iets moet gebeuren. Vijf jaar geleden waren er nog veel sceptici als het ging om het kraken van encryptie door quantumcomputers. “Als je kijkt naar wat de crypto-onderzoeksgemeenschap op dit moment doet, dan is er wel een grote focus op de vraag hoe we crypto kunnen maken die veilig blijft voor quantumaanvallers. Ik denk dat iedereen het ermee eens is dat er iets moet gebeuren. De vraag is alleen hoe snel dat moet. Als onderzoeker wil je toch graag de tijd vooruit zijn.”

IBM-quantumcomputer, via IBM

De NIST-competitie moet uitkomst bieden door voorstellen bijeen te brengen die versleutelingstechnieken bevatten om gegevens voor de voorzienbare toekomst te beveiligen tegen klassieke en quantumcomputers, en die compatibel zijn met bestaande protocollen en netwerken. Schaffner zegt over het NIST-programma: “NIST wil het geen competitie noemen, al is het dat in feite wel. Het geeft het alleen niet deze naam, omdat er niet één winnaar uitkomt, en NIST misschien ideeën uit verschillende hoeken wil gebruiken en deze tegelijk implementeren.“ Het staat vast dat het nog vele jaren gaat duren voordat de einduitslagen bekend zijn, aldus de onderzoeker. Het is nu nog onduidelijk welke kant we op moeten, omdat veel van de relevante wiskundige problemen nog niet voldoende zijn onderzocht.

Het Amerikaanse instituut verwoordt de noodzaak voor het in actie komen als volgt: “Het heeft ongeveer twintig jaar geduurd om onze huidige cryptografische publiekesleutelinfrastructuur op te bouwen. Daarom moeten we nu onze systemen van bescherming tegen quantumcomputers voorzien, los van de vraag of we precies kunnen schatten wanneer het tijdperk van die computers zal aanbreken.”

Meer waarschuwingen

NIST is niet de enige instelling die een waarschuwende toon aanslaat. In Nederland zijn dat bijvoorbeeld de AIVD en het NCSC, dat zich bezighoudt met de beveiliging van de overheid en kritieke sectoren. Onze inlichtingendienst publiceerde drie jaar geleden een informatieblad met daarin globale informatie over de verwachte komst van quantumcomputers. De dienst beroept zich op de TU Delft en schrijft dat die destijds de verwachting had om tussen 2030 en 2040 een quantumcomputer met duizenden qubits te bouwen. Als mogelijke oplossingen noemt de AIVD, of preciezer: het Nationaal Bureau voor Verbindingsbeveiliging van de dienst, het gebruik van quantumencryptie of van zogenaamde post-quantumcryptografie.

Het NCSC kwam in april van dit jaar met een factsheet over deze vorm van cryptografie. Deze publicatie grijpt terug op de verwachting uit het AIVD-informatieblad en plaatst de komst van ‘geavanceerde quantumcomputers’ minimaal dertien jaar in de toekomst. Ook uit deze publicatie komt naar voren dat er nu al actie nodig is, ook al zijn quantumcomputers misschien nog ver weg.

Volgens Schaffner levert het bouwen van een quantumcomputer de grootste problemen op. “In theorie weten we heel goed hoe een quantumcomputer werkt. Als je zo’n perfecte quantumcomputer zou hebben, dan weten we dat we daarmee bijvoorbeeld een algoritme kunnen draaien en daarmee een enorme tijdwinst bij het kraken van encryptie kunnen behalen. De grote vraag is nu alleen hoe je zo’n computer bouwt.” Bij een kwantumprocessor wordt de kwantumstaat van deeltjes in superpositie gebracht, waardoor ze zowel een 1 als een 0 kunnen vertegenwoordigen.

Verschillende grote partijen werken intussen aan de ontwikkeling van een dergelijke computer, waaronder IBM, Google, Microsoft, Intel en het Delftse QuTech. Dat onderzoekscentrum ontving laatst een chip van zeventien qubits van Intel voor testdoeleinden. IBM kondigde vervolgens aan dat het een prototype ontwikkelt van een quantumchip met vijftig qubits, die het bedrijf wil aanbieden via zijn IBM Q-programma, dat zich richt op het ontwikkelen van een commerciële quantumcomputer.

IBM Q-laboratorium

Schaffner zegt over de ontwikkeling: “Het is wel duidelijk dat we daarvoor errorcorrectie nodig hebben. Dat betekent dat er in feite meer qubits nodig zijn. Stel dat je encryptie kunt kraken met duizend perfecte qubits en je kunt een enkele perfecte qubit maken met nog eens duizend imperfecte qubits, dan loopt het aantal snel op. Bijvoorbeeld voor het kraken van rsa2048 is de huidige schatting dat je zo’n miljoen qubits nodig hebt.”

Hoewel we nog niet bij dat aantal in de buurt zijn, gaat de huidige ontwikkeling wel de kant op dat we niet meer eenvoudig simulaties kunnen uitvoeren. “Tot dertig of veertig qubits kun je ook nog wel op een laptop simuleren. In de buurt van vijftig wordt het heel moeilijk, omdat de toestandsruimte exponentieel groeit met elke qubit die je toevoegt. Zodra je het niet meer kunt simuleren, kom je in het gebied van wat mensen nu quantum supremacy noemen. Een betere term is trouwens quantum advantage. Op dat punt zijn we volgend jaar waarschijnlijk wel aangekomen”, aldus Schaffner.

Er is geen nauwkeurige schatting te maken van wanneer iemand beschikt over een gevorderde quantumcomputer die een bedreiging vormt voor huidige encryptietechnieken. Daarvoor is de ontwikkeling afhankelijk van te veel verschillende factoren. Neem bijvoorbeeld een ontwikkeling waardoor blijkt dat er snel opgeschaald kan worden naar een veel groter aantal perfecte qubits.

17qbit-quantumchip, via QuTech

Dat quantumcomputers als bedreiging voor encryptie worden gezien, moge duidelijk zijn. De vraag is waarom dat zo is. Tweakers sprak daarover met Tanja Lange, hoogleraar cryptologie aan de TU Eindhoven en hoofd van het Pqcrypto-onderzoeksproject. Samen met cryptoloog Daniel Bernstein publiceerde Lange dit jaar een paper over de staat van post-quantumcryptografie.

De dreiging die uitgaat van quantumcomputers heeft te maken met het zogenaamde algoritme van Shor. Lange zegt: “Dit algoritme schaalt op een dergelijke manier dat het verhogen van de sleutelgrootte niet voldoende is om een systeem te beveiligen. Een gebruiker die een systeem beveiligt, heeft daar net zoveel tijd voor nodig als een aanvaller die diezelfde beveiliging kraakt. Om het preciezer te zeggen maakt Shors algoritme het mogelijk om rsa in polynomiale tijd te kraken, terwijl versleuteling ook in polynomiale tijd gebeurt.”

Creatieve uitleg van publiekesleutelcryptografie. inleiding eindigt rond 2:00.

Dit heeft ermee te maken dat de kwetsbare cryptosystemen gebruikmaken van priemfactoren om een groot getal te produceren. Stel dat alleen het product van priemfactoren p en q bekend is, dan is het met een huidige computer zeer moeilijk om vanuit dat product terug te rekenen welke priemfactoren met elkaar vermenigvuldigd zijn. Doordat een quantumcomputer dit in polynomiale tijd kan, wat wil zeggen dat het efficiënt en snel uit te voeren is, is dit principe niet meer voldoende om het kraken van encryptie tegen te gaan. Maar, zoals eerder aangegeven, is een aanzienlijk aantal qubits vereist om bijvoorbeeld 2048bit rsa te kraken.

Schaffner legt uit dat de kracht van het algoritme van Shor voortkomt uit de quantumvariant van de zogenaamde Fouriertransformatie. “Die dient ertoe om signalen in elkaar te vertalen. Bijvoorbeeld om een bepaald signaal over tijd uit te drukken in frequentie. In de quantumvariant kun je de transformatie toepassen om een bepaalde periodiciteit vast te stellen in een quantumsignaal.” Een vergelijking die soms wordt gemaakt, is het effect dat golven elkaar kunnen opheffen of elkaar juist kunnen versterken. Dit versterkingseffect leidt ertoe dat de juiste oplossing van een probleem wordt uitvergroot.

Schematische weergave van de Fouriertransformatie, via irenevigueguix

Zowel Lange als Schaffner zegt dat er geen twijfel is dat het algoritme van Shor effectief zal zijn op een quantumcomputer. “Shors algoritme heeft een grote quantumcomputer nodig om te draaien. Om een getal n te factoriseren rekent Shors algoritme met twee elementen met een waarde kleiner dan n. Zodra quantumcomputers dat op een voldoende stabiele manier kunnen doen, is gegarandeerd dat het algoritme de geheime sleutel van rsa zal vinden. Dit is in het klein al uitgevoerd en het is mogelijk om een quantumcomputer te simuleren, waardoor we kunnen testen of quantumalgoritmes kunnen werken”, aldus Lange.

Het algoritme van Shor is goed in het vinden van priemfactoren en leent zich daardoor bij uitstek voor het aanvallen van publiekesleutelcryptografie. Er is echter nog een ander quantumalgoritme dat zich leent voor het kraken van encryptie, en wel de symmetrische variant, waarbij encryptie en decryptie aan de hand van dezelfde sleutel plaatsvinden. Een voorbeeld daarvan is AES. Het quantumalgoritme in kwestie is in de jaren negentig ontwikkeld door Lov Grover en leent zich voor het versnellen van ongestructureerde zoekopdrachten. Daardoor is het veel breder inzetbaar dan de variant van Shor.

Lange zegt over het algoritme van Grover: “Het algoritme versnelt de zoektocht naar de geheime sleutel, maar die versnelling is niet dramatisch en het verdubbelen van de sleutellengte is voldoende om ervoor te compenseren. Preciezer betekent dit dat een aanval op 256bit-AES in het beste geval in 2¹²⁸ operaties uit te voeren is in plaats van in 2²⁵⁶.” Op de vraag of 256bit-AES daarom als quantum secure moet worden gezien, zegt Lange: “Ik zou nooit iets quantum secure noemen, omdat we misschien iets over het hoofd hebben gezien. Maar tenzij een grote groep mensen iets over het hoofd heeft gezien, komt een aanval met Grover uit op 2¹²⁸ operaties bij 256bit-AES.”

De gevolgen van de komst van quantumcomputers voor bepaalde vormen van encryptie, volgens Lange en Bernstein

Waar ontstaan risico’s?

Het probleem is dat ecc en rsa op dit moment nog alomtegenwoordig zijn. De vraag is dan ook waar op den duur de grootste risico's ontstaan. Lange zegt daarover: "De gevoeligste doelwitten zijn applicaties die data op de lange termijn moeten beveiligen, omdat alle gegevens die nu worden opgeslagen en versleuteld, over vijftien jaar door een aanvaller met een quantumcomputer gelezen kunnen worden, als hij tenminste de vooruitziende blik had om die gegevens op te slaan. Dus elke dag die we wachten, is een nieuwe dag met verloren data. Denk daarbij bijvoorbeeld aan gezondheidsgegevens, overheids- en militaire communicatie, dissidenten of journalisten. Een andere categorie zijn apparaten in langdurig gebruik die van software-updates worden voorzien. Een aanvaller zou bijvoorbeeld een kwaadaardige update kunnen installeren, omdat hij in staat is het authenticatieproces van de updates te kraken."

Ook Schaffner noemt digitale handtekeningen als voorbeeld en zegt dat er genoeg aanwijzingen zijn dat overheden grote hoeveelheden gegevens opslaan. Hij beaamt dat het nodig is om actie te ondernemen. "Mensen moeten zich ervan bewust worden dat dingen die ze nu opslaan en versleutelen, op grote schaal worden verzameld. Als je die gegevens voor langere tijd veilig wilt houden, dan is het nu eigenlijk al te laat."

Daarnaast noemt hij de blockchain als ander voorbeeld. Ook daar wordt momenteel over nagedacht, onder meer door onderzoekers van universiteiten in Frankrijk, Australië en Singapore. In een onlangs gepubliceerd onderzoek schrijven ze dat de digitale handtekeningen binnen de bitcoinblockchain afhankelijk zijn van encryptie op basis van elliptische krommen, zoals in ecdsa. Daardoor komen deze ook in het nauw zodra er een quantumcomputer is die het algoritme van Shor kan draaien. Het proof-of-workalgoritme van bitcoin loopt volgens de onderzoekers minder risico, omdat de tijdswinst die het algoritme van Grover oplevert bij het berekenen van hashes, kan worden opgevangen door de hoge snelheid van asics.

In de ogen van de onderzoekers heeft een aanval op een transactie de meeste gevolgen. Zo zou een aanvaller aan de hand van de publieke sleutel de privésleutel kunnen achterhalen die nodig is om een transactie uit te voeren. Doet hij dit snel genoeg, dus voordat de transactie in de blockchain is opgenomen, dan zou hij met de achterhaalde privésleutel een eigen transactie in de blockchain kunnen laten opnemen. De onderzoekers dragen daarom verschillende opties aan voor een alternatieve manier voor het uitwisselen van een publieke sleutel, die minder gevoelig is voor een aanval met een quantumcomputer.

De vraag is wat 'veilige' algoritmes anders doen dan de varianten die we nu gebruiken. Daarover zegt Lange: "Systemen voor post-quantumencryptie zijn gebaseerd op wiskundige problemen waarvoor nog niemand een manier heeft gevonden om het algoritme van Shor toe te passen. Aanvallen op ecc en rsa kunnen vertaald worden naar het vinden van een bepaalde frequentie waarmee zich iets herhaalt dat in verbinding staat met de geheime sleutel. Het algoritme van Shor is daar goed in."

Kijken we bijvoorbeeld naar een publicatie van NIST of aanbevelingen van het Pqcrypto-project, dan noemen deze documenten een aantal mogelijke kandidaten. Zoals we zagen, zijn de gevolgen voor symmetrische encryptie te overzien en voldoet het vergroten van de sleutelgrootte, bijvoorbeeld een 256bit-sleutel voor AES of Salsa20. Voor publiekesleutelcryptografie zijn er bijvoorbeeld lattice-based cryptosystems, oftewel systemen die gebruikmaken van een rooster en het shortest vector-probleem. Een voorbeeld is NTRU. Een andere mogelijkheid is het gebruik van een systeem als McEliece dat gebruikmaakt van foutherstellende codes. Voor digitale handtekeningen is er een mogelijkheid om over te gaan op handtekeningen die alleen zijn gebaseerd op het gebruik van hashfuncties, zoals Sphincs256.

Quantum key distribution

Hiervoor hebben we gekeken naar mogelijke kandidaten die de oplossing zoeken in andere vormen van de 'traditionele' sleuteluitwisseling. Het is echter ook mogelijk om daarvoor gebruik te maken van quantumeffecten, via quantum key distribution. Volgens Schaffner bestaat er over deze methode enige discussie, maar biedt zij een alternatieve oplossing voor het probleem van het uitwisselen van een sleutel. Deze methode laat twee partijen een sleutel uitwisselen door middel van een quantumkanaal, bijvoorbeeld door fotonen te versturen via glasvezel. Die kunnen ze vervolgens gebruiken om berichten via een ander kanaal te versleutelen. Schaffner zegt: "Deze vorm van versleuteling gaat niet uit van de aanname dat het oplossen van een bepaald wiskundig probleem moeilijk is, zoals bij traditionele publiekesleutelcryptografie." De kracht van deze techniek ligt er volgens de onderzoeker in dat een kwantumstaat niet zomaar te kopiëren is, vanwege het zogenaamde no-cloning theorem. Gebeurt dit wel door een actieve aanvaller, dan kunnen de communicerende partijen dit achteraf vaststellen.

Helaas!
De video die je probeert te bekijken is niet langer beschikbaar op Tweakers.net.

Schaffner over qkd op de CCC-conferentie in 2015

Er kleven wel bezwaren aan deze vorm van sleuteluitwisseling, omdat er bijvoorbeeld een infrastructuur aanwezig moet zijn en er maar een beperkte afstand overbrugd kan worden. Lange maakte haar bezwaren tegen deze vorm, ook wel qkd genoemd, onder meer kenbaar bij een consultatie over het zogenaamde Quantum Manifesto van de EU. Daar schrijft ze: "Quantumcryptografie werkt niet met bestaande netwerken, beveiligt niet bestaande gevoelige informatie en beschermt niet de last mile tussen de quantum node en het apparaat van de eindgebruiker." Daarnaast zou de techniek niet geschikt zijn voor authenticatiedoeleinden, zoals digitale handtekeningen.

De praktijk

Tweakers sprak met Joachim Schipper over wat de verwachte komst van quantumcomputers voor zijn werkzaamheden betekent. Schipper is principal research engineer bij Fox-IT en werkt daar onder meer als cryptograaf aan de beveiliging van Nederlandse staatsgeheimen. Over de komst van quantumcomputers zegt hij: "Ik ben heel sceptisch, maar ook dan moet je aan het werk. Als er één procent kans is dat er over dertig jaar een bruikbare quantumcomputer bestaat, is dat waarschijnlijk de grootste cryptodreiging voor onze staatsgeheimen. En zó klein is de kans op een quantumcomputer nou ook weer niet."

Een van die beveiligingstechnieken is een vpn. Schipper zegt: "Fox-IT werkt nú aan post-quantumcryptografie binnen bijvoorbeeld OpenVPN-NL. Dat is een door Fox onderhouden versie van de opensource-OpenVPN-software, die goedgekeurd is voor gebruik door de Nederlandse overheid. We volgen de ontwikkelingen in de post-quantumwereld al jaren nauwlettend. Zo waren we in 2016 een van de eerste commerciële partijen die de academische Pqcrypto-conferentie bijwoonden. En natuurlijk spreken we uitgebreid met onze partners bij de overheid."

Binnen de vpn-software wil Fox-IT bijvoorbeeld het eerder besproken McEliece gaan gebruiken. "Dat is een algoritme uit 1978 dat al vele aanvallen heeft doorstaan, maar als je mobieltje een beetje slechte verbinding heeft, zit je wel echt te wachten tot McEliece alle benodigde data heeft verstuurd. Alternatieven zijn veel zuiniger", aldus Schipper. Volgens de onderzoeker is het vakgebied van post-quantumcryptografie nog zeer in ontwikkeling. Over zijn verwachting voor de toekomst zegt hij: "Daarnaast zullen veilige implementaties in hard- en software meer aandacht krijgen, juist ook nadat NIST een standaard heeft gekozen. Een wiskundig sterk algoritme valt vaak tóch ten prooi aan zogenaamde side-channelaanvallen. Fox-IT doet, met onze Delftse collega’s van Riscure, actief onderzoek naar zulke aanvallen."

Schipper wijst erop dat momenteel stappen worden genomen in de academische wereld, bij grote bedrijven en bij de bescherming van staatsgeheimen. Op de vraag of dit ook de plekken zijn waar actie nodig is, antwoordt hij: "Dit zijn de juiste sectoren. Voor vitale infrastructuur zijn andere problemen dringender, maar de sectoren die dit soort dingen niet zélf kunnen ontwikkelen, moeten ook mee. Daarvoor is het belangrijk dat de academici en NIST een standaard ontwikkelen, en dat goede implementaties beschikbaar komen als kant-en-klare componenten."

De vraag of een quantumcomputer daadwerkelijk binnen handbereik is of niet, blijft moeilijk te beantwoorden. Desondanks staat vast dat als er eenmaal een geavanceerde quantumprocessor wordt gebouwd, deze een serieuze bedreiging vormt voor onze huidige varianten van publiekesleutelcryptografie. Het gebruik daarvan is wijd verspreid, waardoor de mogelijke risico's groot zijn. Gegevens die we nu versleutelen met kwetsbare encryptie, moeten volgens verschillende waarschuwingen nu al als 'verloren' worden beschouwd. Het algoritme van Shor brengt de grootste snelheidswinsten met zich mee bij het kraken van encryptie die gebaseerd is op grote priemfactoren. Het algoritme van Grover kan bij symmetrische encryptie een voordeel opleveren, maar dit is te ondervangen door grote sleutels te gebruiken.

Wetenschappers Grover en Shor

Daarom roepen wetenschappers al enige tijd op om nu al over te stappen op encryptievormen die betere bescherming bieden tegen quantumcomputers. Het Amerikaanse NIST heeft een competitie georganiseerd, waaruit geschikte kandidaten voor een standaard moeten voortkomen. Dit proces zal waarschijnlijk nog enkele jaren duren. Op dit moment bestaat daarom op veel plaatsen wel het bewustzijn dat er iets moet gebeuren, maar weten we nog niet precies waar de oplossingen liggen. De kans op de ontwikkeling van een quantumcomputer en het mogelijke risico dat deze systemen met zich meebrengen, is in elk geval groot genoeg om er serieus rekening mee te houden.