Werk in uitvoering: post-kwantumencryptie met McEliece

27 januari 2012

Wanneer we in de toekomst de beschikking zouden krijgen over kwantumcomputers, zijn de huidige asymmetrische cryptosystemen niet meer toereikend. De coderinggebaseerde versleuteling van McEliece lijkt een goede kandidaat te zijn voor de encryptie van de toekomst.

Asymmetrische of publieke cryptografie werd in de jaren zeventig uitgevonden als antwoord op het sleuteldistributieprobleem: hoe krijg je de geheime sleutel om ontvangen beveiligde berichten te decoderen zonder dat kwaadwillenden die bemachtigen? Je kunt hem niet open en bloot versturen, maar ook niet versleutelen: dan heeft de ontvanger opnieuw een sleutel nodig om de sleutel te decoderen. Asymmetrische cryptografie lost dit probleem op door twee sleutels te gebruiken: een publieke en een geheime privésleutel. De eerste is door iedereen op te vragen en alleen te gebruiken om een bericht om te zetten in een gecodeerde cijfertekst. Om deze weer te ontcijferen, is de tweede sleutel nodig, die alleen in het bezit is van de ontvanger.

Het algoritme dat hiervoor algemeen wordt gebruikt, heet RSA (naar de uitvinders Ron Rivest, Adi Shamir en Leonard Adleman). Het genereren van de sleutels is gebaseerd op de machtsverheffing van enorm grote getallen; het kraken ervan gaat door middel van ontbinding in factoren. De techniek is met de huidige computers vrijwel niet te kraken, terwijl het versleutelen en ontcijferen niet onevenredig veel rekenkracht kosten. RSA wordt ingezet in toepassingen uiteenlopend van digitale handtekeningen tot het opzetten van beveiligde VPN-verbindingen.

Maar RSA heeft waarschijnlijk niet het eeuwige leven. De wetenschappelijke wereld werkt momenteel hard aan de ontwikkeling van een kwantumcomputer, een systeem dat zeer efficiënt parallel berekeningen kan uitvoeren. Er is al een algoritme, het algoritme van Shor, dat met zo’n computer een groot getal snel in factoren kan ontbinden. RSA-encryptie is dan gemakkelijk te kraken.

Een leuk idee

Niet alle wiskundige problemen zijn echter zo uit te schrijven dat ze met massaal parallel rekenen oplosbaar zijn. Een groep is ongevoelig voor kwantumcomputers en Shor. McEliece-encryptie, een andere vorm van asymmetrische encryptie, valt in deze categorie. Volgens Christiane Peters, die aan de TUE promoveerde op McEliece-cryptografie en er nu aan de Technische Universiteit van Denemarken in Kopenhagen onderzoek naar doet, is het systeem een van de belangrijkste kandidaten om RSA op te volgen. ‘McEliece werd zo’n dertig jaar geleden uitgevonden. Iedereen vond het toen een leuk idee, maar nog niet erg praktisch. De laatste zes, zeven jaar is er echter steeds meer interesse in de techniek als oplossing in een post-kwantumwereld.’

Het McEliece-cryptosysteem is gebaseerd op het opsporen van fouten in een matrix. Een matrix is in dit geval een enorm raster van enen en nullen. Vervang je hierin willekeurig een nul door een een, dan introduceer je een fout. Wanneer een matrix geen structuur heeft, is het onmogelijk om erachter te komen welke enen en nullen precies zijn omgedraaid. Is die structuur er wel, dan kun je door te speuren naar onregelmatigheden erachter komen waar de fouten zitten in de matrix. Van dit principe maakt McEliece gebruik.

McEliece-cryptografie is een alternatieve vorm van asymmetrische cryptografie gebaseerd op foutcorrectiecodes. Alice genereert twee willekeurige matrices en een gestructureerde matrix waarin ze fouten eenvoudig kan opsporen. Dit trio houdt ze angstvallig geheim, maar het product ervan publiceert ze. Als Bob haar nu een beveiligde boodschap wil verzenden, vermenigvuldigt hij die met deze publieke matrix en voegt hij er vervolgens willekeurige fouten aan toe. Als een aanvaller het bericht wil achterhalen, zou hij elke foutcombinatie systematisch moeten uitproberen.

McEliece-encryptie werkt net als RSA met een openbare publieke sleutel en een geheime privésleutel. De privésleutel bestaat uit drie enorme matrices en een decodeeralgoritme. Twee van de drie matrices hebben geen structuur: de enen en nullen staan willekeurig in het raster. De derde matrix bevat echter veel structuur. Zou je daar enen en nullen omdraaien, dan kun je die er met een algoritme uit halen. In de regel wordt bij McEliece-encryptie een Goppa-code, een bekende methode om foutcorrecties op te sporen, ingezet om deze derde matrix structuur te geven. Het is echter ook mogelijk om andere vormen te gebruiken zoals die van Reed-Solomon of Gabidulin. Het product van de drie matrices is de publieke sleutel en voor iedereen op te vragen. Door de vermenigvuldiging lijkt het een ongestructureerde verzameling van getallen.

Wat gebeurt er nu wanneer je een berichtje versleutelt? Allereerst wordt de woordelijke tekst omgezet in een cijfertekst van enen en nullen. Deze wordt vervolgens vermenigvuldigd met de publieke sleutel. Het resultaat is een string van 1024 bits enen en nullen. Deze getallenreeks is nog allerminst versleuteld; door een vergelijking zou je met behulp van de publieke matrix gemakkelijk kunnen achterhalen hoe de originele cijfertekst er precies uitzag. Een derde stap introduceert daarom fouten in de 1024 bits: enen worden nullen, nullen worden enen. Een vergelijking opstellen om de originele cijfertekst te achterhalen, is nu onmogelijk geworden. Kwaadwillenden zullen alle mogelijke fouten moeten uitproberen om de vergelijking te vinden. Eén fout levert 1024 mogelijkheden op. Vijftig fouten, zoals gebruikelijk bij McEliece-encryptie, geeft 102450 mogelijkheden. Niet te kraken dus. Na toevoeging van de fouten is het bericht versleuteld en kan het over het netwerk worden verstuurd.

Bij het ontsleutelen maak je gebruik van de alleen aan jou bekende hulpmiddelen: de drie matrices en het decodeeralgoritme. Eerst haal je hiermee de fouten uit het gecodeerde berichtje. Dat levert een van fouten gezuiverde cijfertekst op. In een tweede stap kun je met behulp van lineaire algebra de originele cijfertekst achterhalen.

Drie maanden

De berekeningen in McEliece-encryptie zijn door een computer sneller uit te voeren dan het geval is bij RSA. Toch is de methode nooit populair geworden. Dat komt doordat de matrixsleutels erg groot zijn. ‘Voor kleine platforms zoals smartcards speelt niet alleen snelheid maar vooral ook de grootte van de sleutel een rol’, verklaart Peters. ‘Om hetzelfde veiligheidsniveau als RSA met 3248 bits te krijgen, heb je voor een McEliece-matrix 192.192 bytes nodig. Crypto met elliptische krommen vergt zelfs maar 256 bits voor de publieke sleutel. Er zijn coderinggebaseerde crypto-implementaties op smartcards en 8 bit microcontrollers, maar daar moet nog meer gebeuren om echt te kunnen concurreren met RSA of elliptische krommen.’

Peters onderzocht voor haar promotieonderzoek welke aanvallen mogelijk succesvol zouden kunnen zijn tegen een McEliece-encryptiesysteem. In 2008 slaagde ze erin met hulp van haar begeleider Tanja Lange en Daniel Bernstein van de University of Illinois in Chicago een aanval te ontwerpen waarmee één gecodeerd bericht in een tijdsbestek van drie maanden kon worden vertaald. Dit was de eerste en tegelijk de laatste succesvolle aanval. De groep publiceerde nieuwe richtlijnen waarmee het cryptosysteem kan worden opgebouwd. Nog grotere matrices en meer benodigde fouten. Net wat je niet wilt.

Momenteel werkt Peters in Kopenhagen vooral aan alternatieve set-ups voor coderinggebaseerde cryptografie om deze geschikt te maken voor praktisch gebruik. Doel is de wiskunde van McEliece-encryptie zo aan te passen dat die met kleinere matrices toekan zonder aan veiligheid in te boeten. Ze werkt daarbij nauw samen met ingenieurs die de door haar bedachte cryptosystemen moeten toepassen. Zij bedenken de systeemeisen waaraan het systeem moet voldoen.

Peters wil bijvoorbeeld onderzoeken of er wellicht een andere code kan worden gebruikt om de fouten uit de cijfertekst te halen. In het verleden werden bijvoorbeeld Reed-Solomon en Gabidulin gebruikt in plaats van Goppa. Maar hoewel deze codes kleinere matrices opleveren, is het niet mogelijk om hiermee een adequaat veiligheidsniveau te halen. ‘Door een aantal vergelijkingen op te lossen, kun je zien welke Reed-Solomon-code precies is gebruikt. Dan heb je echt de geheime sleutel en kun je ineens alle cijferteksten ontsleutelen.’

Een andere mogelijkheid is om Goppa-codes met een speciale structuur te gebruiken. ‘Goppa-codes met een specifieke verhouding tussen matrixlengte en hoeveelheid corrigeerbare fouten kunnen worden herschreven tot een string van bits van waaruit de matrix kan worden gegenereerd. Een apparaat dat de decryptie zou moeten uitvoeren, moet dan wel een extra rekenslag maken en is dan ook iets duurder. Je hoeft dan echter niet zo veel informatie op te slaan op de harde schijf’, aldus Peters. Toch is deze oplossing ook niet voor alle parameters veilig gebleken. Aanvallers waren in staat om uit de cijfertekst te achterhalen welke matrix nodig was om de string van fouten te zuiveren.

Een derde voorstel van Peters beoogde niet alleen enen en nullen maar ook andere waardes toe te laten in de codeermatrices. De methode levert inderdaad kleinere matrices op, maar in dit geval liggen de ingenieurs dwars. ‘Ik kan dan wel met grotere getallen aankomen, maar als ik dat op een smartcard wil implementeren, worden de ingenieurs daar niet zo blij van. Het apparaat wordt een stuk langzamer, omdat je met complexe parameters aan het werk moet.’

Volgens Peters zal het naar schatting nog zeker vijf jaar duren eer coderinggebaseerde encryptie praktisch toepasbaar is. Of bedrijven dan ook massaal McEliece gaan gebruiken, is maar de vraag. Banken en andere grote commerciële partijen hebben vooralsnog weinig interesse getoond voor deze encryptie. Veiligheidsdiensten, zoals het Duitse BSI en het Amerikaanse Nist, hebben wel interesse. Deze instellingen publiceren veiligheidsstandaarden die uiteindelijk door de industrie zullen worden gevolgd. ‘Doelstelling van mijn onderzoek is om in een jaar of twee bij die richtlijnen te worden genoemd’, zegt Peters. ‘Ik denk dat het al een heel goed teken is als de nationale veiligheidsinstituten belangstelling tonen. Als die ons op het programma zetten, zijn we geaccepteerd.’

Bram Semeijn

Terug naar overzicht