Https: nu ook bestand tegen de quantumcomputer

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.”

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’.

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.