Naar de content

Https: nu ook bestand tegen de quantumcomputer

Google gaat deel internetverkeer nu al dubbel beveiligen

@annedejong314

Cryptografen van het CWI in Amsterdam en de Radboud universiteit Nijmegen kregen een door Facebook gesponsorde prijs voor een methode om internetverkeer bestand te maken tegen aanvallen met de quantumcomputer. Google gaat nu met hun methode een deel van het eigen internetverkeer extra beveiligen. Opmerkelijk omdat de quantumcomputer nog niet eens bestaat.

15 september 2016
@annedejong314

Iedere keer als je naar een webpagina gaat met in de adresbalk het icoontje van een slot en https://…, zet je browser een ingewikkelde procedure in werking, TLS (Transport Layer Security), dat met die website afspraken maakt over de beveiliging van de data die heen en weer gaan. Een belangrijk onderdeel daarvan is een zogeheten _handshake_-protocol. Dat is een soort voorgesprekje tussen jouw browser en die website. Aan het einde daarvan beschik je beide over dezelfde geheime sleutel om de data die je daarna verstuurt te vercijferen.

Goocheltruc

Hoe wonderlijk het ook klinkt: die geheime sleutel hoef je elkaar niet te vertellen, en dat moet ook niet, want op het internet ben je er nooit zeker van dat je niet wordt afgeluisterd. Een geheime sleutel uitwisselen met iemand die je nog nooit ontmoet hebt, zonder dat je die sleutel aan de ander hoeft te vertellen, is een cryptografische goocheltruc die voor het eerst is gepubliceerd in de jaren zeventig, namelijk de Diffie-Hellman sleuteluitwisseling (zie kader verderop).

Dat werkt al jaren prima, maar donkere wolken pakken zich samen aan de beveiligingshorizon: de quantumcomputer komt eraan. De veiligheid van ‘Diffie-Hellman’ berust op de praktische onmogelijkheid om een wiskundig probleem op te lossen, het zogeheten ‘discrete logaritme probleem’. Met computers zoals wij die nu hebben, lukt dat inderdaad niet, maar een quantumcomputer zal dat wel kunnen. Het kraken van ‘Diffie-Hellman’ komt in wezen neer op het uitproberen van een enorm aantal mogelijkheden voor de sleutel. Een klassieke computer moet die sleutels stuk voor stuk uitproberen, terwijl een quantumcomputer die in zekere zin allemaal tegelijk uitprobeert, waarna de enige juiste oplossing overblijft.

In een sterk versimpelde beeldspraak: stel, je hebt een enorme berg kaartjes met nummers erop, en je moet het enige kaartje hebben met nummer 31.415.926.535. Voor een normale computer is de enige mogelijkheid: al die kaartjes gaan lezen, totdat je de juiste tegenkomt. Maar een quantumcomputer weet dat het enige juiste kaartje rood is, en alle andere wit. Dus de quantumcomputer spreidt die hele berg kaartjes uit op de vloer, waarna het kaartje met nummer 31.415.926.535 er meteen uitspringt.

En hoewel een werkende quantumcomputer nog niet bestaat, zijn onderzoeksgroepen over de hele wereld, waaronder in Delft, druk bezig onderdelen ervan te bouwen. Zodra de quantumcomputer realiteit wordt, is geen enkele https-pagina meer veilig. Leo Ducas: “Dat het mogelijk wordt om een quantumcomputer te bouwen is nog lang geen algemeen geaccepteerd feit. Maar gezien de enorme hoeveelheid infrastructuur die afhankelijk is van cryptografie, is zelfs een minuscule kans dat dit gebeurt reden genoeg om al tegenmaatregelen te nemen.”

Peter Schwabe: “Grote geheime diensten, van de Verenigde Staten en waarschijnlijk ook China en Rusland, slaan nu al vercijferde boodschappen op, al zijn ze nog niet te ontcijferen. Als er over dertig jaar een quantumcomputer bestaat, breken ze wel de codes en gaan ze terugkijken. Daar moeten mensenrechtenactivisten in China zich nu al zorgen over maken.”

Arnout Jaspers voor Kennislink

Quantum-upgrade

Vier cryptografen, waaronder Leo Ducas van het Centrum Wiskunde & Informatica in Amsterdam en Peter Schwabe van de Radboud Universiteit Nijmegen hebben nu de veiligheid van ‘https’ een quantum-upgrade gegeven, die ze New Hope noemden. Facebook was er zo van onder de indruk, dat ze er op de recente USENIX-conferentie, in juni 2016, een prijs van 100.000 dollar voor kregen, eerlijk te verdelen over de vier auteurs. Google heeft al besloten om een klein deel van zijn data-verkeer zowel op de klassieke manier als met New Hope te beveiligen.

Dat doet Google waarschijnlijk niet omdat ze geloven dat er al ergens op de wereld een quantumcomputer hun e-mail leest maar om het systeem in de praktijk te testen en de kinderziektes eruit te halen. “Als je New Hope toepast samen met het bestaande systeem, duurt die handshake ongeveer twee keer zo lang,” aldus Schwabe. Daar merkt de doorsnee gebruiker niets van, omdat zo’n handshake maar een paar milliseconden duurt.

Geheimen delen in het bijzijn van luistervinken.

Het Diffie-Hellman-protocol voor sleuteluitwisseling presteert het schijnbaar onmogelijke: twee partijen Alice en Bob die niet veilig – zonder dat anderen meeluisteren – kunnen communiceren, slagen er toch in om het eens te worden over een geheime sleutel. In de praktijk is dat vaak een getal van 256 bits, ongeveer tachtig decimale cijfers. Het protocol zit zo vernuftig in elkaar, dat Alice en Bob elkaar die geheime sleutel niet hoeven te vertellen.

En dat moet ook, want ze kunnen er immers nooit zeker van zijn dat ze niet worden afgeluisterd. Met gebruik van die sleutel kunnen ze elkaar vervolgens veel langere boodschappen sturen in een geheimschrift dat niemand anders kan lezen.

De wiskundige vertaling van het maken van een gemeenschappelijke, geheime mengkleur gebeurt iedere dag talloze malen op het internet, telkens als een webbrowser contact maakt met een https-site. Als regel wordt bij ieder bezoek een nieuwe sleutel gemaakt, en wordt die gewist zodra je de https-site verlaat.

De veiligheid van deze procedure berust er op, dat het in de praktijk onmogelijk is om een pot gemengde verf te splitsen in de twee zuivere kleuren. Wiskundig komt dit overeen met de praktische onmogelijkheid om het ‘discrete logaritme probleem’ op te lossen. Cryptografen zijn er van overtuigd dat de huidige, klassieke computers dit inderdaad niet kunnen. Maar er bestaat al een algoritme (rekenprocedure) waarmee een quantumcomputer het discrete logaritme probleem wel kan kraken. Zodra de eerste werkende quantumcomputer is gebouwd, wordt alle internetverkeer met https-sites onveilig.

Een fraaie illustratie van dit principe zijn Alice en Bob die elkaar potten verf sturen met een mengkleur. Eventuele pottenkijkers kunnen alleen zien wat er in het midden van de illustratie gebeurt, dus niet wat Alice en Bob aan hun eigen kant doen. Hoewel Alice en Bob elkaars pure kleur niet weten, en iedereen de mengkleuren mag zien die ze elkaar sturen, kan niemand, behalve Alice en Bob, weten welke kleur het eindproduct heeft. De kleur van het eindproduct staat symbool voor de geheime sleutel.

Quantumalgoritmes

Hoe je internetbeveiliging een quantum-upgrade geeft, was in principe bekend: niet ieder wiskundig probleem is met de quantumcomputer te kraken. Sterker nog, het is alsof de duivel er mee speelt: een groot deel van de internetbeveiliging is gebaseerd op slechts twee wiskundeproblemen. Namelijk discrete logaritmes en het factoriseren van grote getallen. Die twee behoren nu juist tot de weinige problemen waarvoor al quantum-algoritmes ontdekt zijn om ze te kraken.

Een paar jaar eerder was door anderen ontdekt, dat een quantum-bestendig probleem, Ring Learning with Errors (RLWE), in theorie ook geschikt is voor sleuteluitwisseling. Schwabe: “Wij hebben laten zien hoe je dit systeem in de praktijk kunt toepassen.” Bij het oorspronkelijke RLWE moest een zeker getal, A, voor eens en voor altijd gekozen worden en aan iedereen bekend gemaakt. Schwabe: “Maar als je dan een kamer vol cryptografen binnenloopt, zullen die allemaal zeggen: hoe ga jij een A kiezen zodat alle gebruikers geloven dat er geen ‘achterdeur’ in zit?”.

Achterdeur

De ‘achterdeur’ is een zwakheid van geheimschriften waarvoor cryptografen een gezonde paranoïa ontwikkeld hebben. Veel geheimschriften werken prima voor bijna alle lange sleutelgetallen die je kiest. Maar vaak bestaat ook een aantal zwakke sleutelgetallen, die het heel makkelijk maken om het systeem te kraken, als het ware via een ‘achterdeur’.

Ring Learning with Errors (RLWE) is een alternatief voor Diffie-Hellman sleuteluitwisseling, dat ook bestand is tegen aanvallen met een toekomstige quantumcomputer. De wiskunde erachter is gecompliceerd, maar ook hier gaat informatie heen en weer tussen Alice en Bob, waaruit ze ieder de gemeenschappelijke, geheime sleutel samenstellen. Iemand in het midden, die de communicatie afluistert, beschikt niet over de privé-informatie van Alice of Bob die nodig is om de geheime sleutel te reconstrueren. RLWE is wiskundig merkwaardig, omdat het doelbewust errors (fouten, of ‘ruis’) toevoegt aan de data die Alice en Bob elkaar sturen. Zonder die ruis – de letters e, e’ en e” in de formules – zou het systeem makkelijk te kraken zijn.

AJ voor Kennislink

Achterdochtig

Als je willekeurig een getal van 256 bits als sleutel kan kiezen, is de kans dat dit een zwak sleutelgetal is verwaarloosbaar. Maar als de ontwerper van een geheimschrift jou vertelt dat je, naast je eigen sleutel, ook een door hem gekozen getal A moet gebruiken, zou je dan niet achterdochtig worden? Er gaan geruchten dat de Amerikaanse National Security Agency een nu verouderd geheimschrift, DES, op een vergelijkbare manier in het geniep van een achterdeur voorzien had, zodat die al die tijd elk met DES vercijferd bericht heeft kunnen lezen.

Schwabe en zijn collega’s hebben daar nu iets op gevonden. Schwabe: “De oplossing is, dat de browser iedere keer als hij contact legt met een website een nieuwe A aanmaakt.” En die A wordt gewist zodra de sessie afgelopen is. Een andere innovatie was: een veel simpeler manier om ‘ruis’ (de errors in RLWE) aan de verzonden berichten toe te voegen, wat noodzakelijk is voor de veiligheid van het systeem. Oorspronkelijk werd die ruis toegevoegd door random getallen te kiezen uit een bepaalde statistische verdeling, de ‘discrete Gauss-verdeling’. Schwabe: “Software-bouwers haten de discrete Gauss-verdeling, die is moeilijk veilig in te bouwen, en het maakt de software langzaam.”

Verdere verbeteringen om het systeem praktisch bruikbaar te maken waren een kwestie van fine-tuning: uit een grondige analyse door de vier cryptografen bleek dat je kunt kiezen voor een wat minder zware versie van het RLWE-probleem, die de software een stuk sneller maakt zonder dat het veiligheidsniveau significant omlaag gaat.

Met een quantumcomputer de beveiliging kraken van het internetverkeer is vrijwel onmogelijk dankzij een nieuw cryptosysteem.

Brian Klug, Flickr.com, CC 2.0.

Tanden stuk bijten

Hoe weten cryptografen zo zeker dat een geheimschrift bestand is tegen een aanval, met een gewone of met een quantumcomputer? Hoe kun je nu al weten wat iemand over tien of twintig jaar aan slims verzint om een systeem te kraken? Voor ‘Diffie-Hellman’ geldt, dat het al decennialang alle kraakpogingen doorstaan heeft. Het staat vrijwel vast, dat elke gewone computer er ook in de toekomst zijn tanden op stuk zal bijten. Maar hoe staat het met RLWE? Het idee om RLWE te gebruiken voor sleuteluitwisseling is een jaar of vijf oud, maar het meer algemene probleem, Learning With Errors, wordt al langer bestudeerd. Niettemin is in het kraken van RLWE tot nu toe minder energie gestoken dan in ‘Diffie-Hellman’ of andere veel gebruikte cryptosystemen.

De vier onderzoekers hebben een van de quantumalgoritmes bekeken waarmee RLWE aan te vallen is, en met grote veiligheidsmarges geschat wat dan nodig zou zijn om RLWE echt te kraken als je een flink lange sleutel gebruikt. Onder die aannames is RLWE quantum-resistent, maar: “het is discutabel of dit de best mogelijke aanval is”, stelt Schwabe. Ducas: “Er zijn recent verbeteringen gevonden in quantumalgoritmes voor RLWE, maar er zijn nog steeds goed bekende obstakels waarvoor geen oplossing gevonden is. Wiskundig bekeken, weet je het nooit zeker: geen enkel cryptografisch systeem van dit type is onvoorwaardelijk onkraakbaar.”

Cryptografen, en bedrijven als Google, beseffen dat je sommig dataverkeer eigenlijk nu al quantum-resistent moet maken. Want ongetwijfeld zijn geheime diensten al bezig om berichten op te slaan die ze nog niet kunnen ontcijferen, in afwachting van de quantumcomputer. Als die er is, kraken ze Diffie-Hellman en gaan ze terugkijken – geen prettig vooruitzicht voor iedereen die zich nu te weer stelt tegen een dictatoriaal regime. Schwabe: “Van cryptografie zijn mensenlevens afhankelijk.”

Bronnen
ReactiesReageer