Spons gaat voor goud

19 januari 2012

Essentieel onderdeel van allerhande beveiligingsprotocollen is het genereren van een vingerafdruk van data met een hashalgoritme. De gebruikte standaarden vertonen haarscheurtjes in de veiligheid: een aanval zou een vals document voor echt kunnen laten doorgaan. In 2007 werd er daarom een wereldwijde zoektocht gestart naar een opvolger. Een Belgisch-Italiaans team wist door te dringen tot de finale met hun Keccak-voorstel.

Hoe controleer je de echtheid van digitale data? Dat is, kort door de bocht, de reden dat zogenaamde cryptografische hashfuncties zijn uitgevonden. Je stopt er een willekeurige hoeveelheid data in en de functie spuugt een korte reeks bits uit: een vingerafdruk van de data. Vanuit die vingerafdruk zijn de originele data niet terug te redeneren.

Cryptografische hashfuncties worden op vele verschillende manieren ingezet. Bij het versturen van data kan de ontvanger controleren of er niet met de boodschap is gerommeld, door de handtekening te genereren en te vergelijken met een meegestuurde digest. Hashfuncties vervullen dan ook een sleutelrol in digitale certificaten waarmee websites beveiligde verbindingen leggen. Ook voor bijvoorbeeld het veilig opslaan van wachtwoorden kan een cryptografische hash worden ingezet: in plaats van het wachtwoord zelf staat de hash weggeschreven in een bestand. Bij het inloggen wordt niet het ingetypte wachtwoord maar een hash ervan vergeleken met een opgeslagen versie. Komen ze overeen, dan kwamen ook de oorspronkelijke data overeen. En omdat er niet terug te redeneren is vanuit de hash naar het wachtwoord, staat het veilig opgeslagen - zelfs als iedereen het wachtwoordbestand kan lezen.

De digests zijn niet uniek voor elke verschillende input - met bijvoorbeeld een handtekening van 32 bits zijn er een dikke vier miljard verschillende hashes te maken, terwijl er praktisch oneindig veel verschillende inputs in gestopt kunnen worden. Die uniciteit hoeft ook niet, zolang er aan een belangrijke voorwaarde wordt voldaan: het moet (praktisch) onmogelijk zijn om een boodschap te maken die een vooraf bepaalde hash oplevert. Dan zou een kwaadwillende immers een gewijzigde boodschap kunnen opstellen die toch voor echt doorgaat. Ook moet het ondoenlijk zijn om twee boodschappen op te stellen die dezelfde hash opleveren, een collision.

Dat is precies waarom er de laatste decennia steeds nieuwe standaarden bedacht moesten worden. De oudere de facto standaarden als MD2 en MD4 (MD staat voor message digest) bleken lekken te bevatten waarmee het vrij eenvoudig is om een collision te berekenen. Ook opvolger MD5 bleek een beurse plek te bevatten. Die is niet eenvoudig uit te buiten, maar toch. In 2008 werd een aanval gedemonstreerd waarbij een digitaal certificaat dat met MD5 was opgesteld, werd nagemaakt - nadat een cluster van tweehonderd Playstation 3’s er een paar dagen op had staan rekenen overigens. Voor cryptografische toepassingen wordt het echter afgeraden nog langer MD5 te gebruiken.

Daarom ging het Amerikaanse Nist, dat de ontwikkeling van cryptografische standaarden overziet, op zoek naar een nieuwe methode. Dit leidde tot het Secure Hash Algorithm (Sha), kort daarop opgevolgd door Sha-1 om een rotte plek op te lossen. Toen daar ook weer gevoeligheden in werden gevonden, werd Sha-2 ontwikkeld. Deze versie is echter gebaseerd op dezelfde principes als Sha-1 en MD5, wat weinig vertrouwen geeft. Erg theoretisch en voor de de voorzienbare toekomst zonder enige praktische consequentie, maar het Nist startte voor de zekerheid toch alvast met een zoektocht naar Sha-3.

Figuur 1: Hashfuncties worden traditioneel opgesteld met de Merkle-Damgård-constructie, waarbij een compressiefunctie de boodschap stukje voor stukje verwerkt tot een digest. Deze constructie is in essentie eenvoudig en elegant, maar maatregelen tegen aanvallen maken hem ingewikkelder: het is nodig om de lengte van de streng mee te nemen (|m|) in de boodschap en om een extra compressieronde met alternatieve initialisatievector uit te voeren. Als langere hashes vereist zijn, moet de hele constructie zelfs een aantal keer worden gedupliceerd.

Gouden standaard

Het Nist zoekt zijn cryptografische standaarden via een open competitie: het instituut schrijft een opdracht uit waarop iedereen een voorstel mag insturen, en iedereen mag vervolgens proberen om deze voorstellen onderuit te halen. In een aantal rondes kunnen de inzenders dan nog proberen hun bijdrage te repareren of ze kunnen zich terugtrekken. Het winnen van de competitie levert geen geld op - de technologie moet zonder royalty’s of belemmeringen beschikbaar worden gesteld - maar wel bakken prestige. Wat het Nist uiteindelijk goedkeurt, wordt de gouden standaard binnen de cryptografie.

Het Nist kondigde de competitie voor Sha-3 aan in 2007. Een jaar later sloot het de inschrijving en selecteerde het 51 levensvatbare kandidaten. Na een aantal rondes zijn er nog vijf finalisten over, waarvan eentje afkomstig uit onze contreien: Keccak. De methode is uitgebroed door Gilles Van Assche, Guido Bertoni, Joan Daemen en Michaël Peeters. De cryptografen werkten oorspronkelijk alle vier voor STMicroelectronics: Bertoni in Italië, de andere drie in Zaventem. Peeters werkt vandaag de dag bij NXP verder aan Keccak.

Voor Keccak - de naam is gebaseerd op een Balinese dans - bedachten de vier een nieuwe aanpak die ze de sponsconstructie doopten. ‘Hij bestaat uit een absorbeerfase waarbij je er data in stopt en een uitknijpfase waar je er weer data uithaalt’, verklaart Daemen de naam.

Ongeveer de helft

Om te snappen hoe de spons werkt, moeten we eerst kijken naar hoe hashalgoritmes traditioneel worden opgebouwd (Figuur 1). Het hart ervan is een compressiefunctie. In de dop is dit al de hashfunctie: zij produceert een output met de juiste lengte. Het verschil is de input: deze functie verwerkt geen boodschappen van willekeurige lengte, maar twee inputs met elk een vast aantal bits als lengte, waarvan minstens eentje even groot als de output. De functie spuugt dus altijd minder bits uit dan erin gaan, vandaar de naam.

Om hier nu een volwaardige hashfunctie van te maken, moet de compressiefunctie in een groter geheel worden gehangen: de Merkle-Damgård-constructie. Het volledige bericht wordt eerst opgehakt in blokjes met de juiste grootte om aan de compressiefunctie te voeren. Het laatste blokje wordt simpelweg opgevuld met nullen als het te kort is (in de praktijk is het iets complexer). Vervolgens worden de blokjes een voor een door de compressiefunctie gehaald, samen met de output van de vorige stap als een van de inputs (voor de eerste stap wordt een vaste input genomen, de initialisatievector of IV). Op die manier wordt bij elke stap een stukje van de boodschap plus de digest van alle vorige stappen verwerkt tot een nieuwe vingerafdruk. Wat er na de laatste aanroep uitrolt, is de digest van de boodschap.

Met de Merkle-Damgård-constructie is het dus alleen zaak om een geschikte compressiefunctie te ontwerpen. Als die in orde is, is de hele hashfunctie ook in orde. ‘Alleen weet niemand hoe dat moet’, aldus Daemen. ‘Maar wat we wel kunnen ontwerpen, of althans wat we denken te kunnen ontwerpen, is een block cipher.’ Block ciphers zoals 3Des of AES zijn de meest gangbare manier om berichten te versleutelen. Net als bij Merkle-Damgård bestaan dergelijke algoritmes uit een constructie met een basisfunctie die op inputblokken van een vaste lengte werkt. En ook bij deze basisfunctie gaat er meer informatie in dan eruit komt: de input bestaat uit een blok data die gecodeerd moeten worden en een sleutel, de uitvoer is een een blok gecodeerde data met dezelfde lengte als de invoerdata.

In de basisfunctie van een block cipher heeft elke bit die erin gaat invloed op alle outputbits. Idealiter klapt ongeveer de helft van de outputbits om als er één invoerbit verandert. Dat is een belangrijke vereiste, want zo kan een aanvaller nooit systematisch proberen inputbitjes om te klappen om te kijken of hij in de richting komt van de output. Het is ook precies waar een hashfunctie aan moet voldoen. De compressiefunctie bij hashes is dus prima te baseren op de basisfunctie van een block cipher. Als sleutel wordt dan de input uit de vorige ronde gebruikt (of de IV aan het begin).

Nogal complex

Merkle-Damgård is aantrekkelijk vanwege zijn eenvoud en elegantie. Cryptografen kunnen de aanpak daardoor goed doorgronden, wat de kans op onvoorziene lekken reduceert. Helaas zitten er zwakke plekken in de basisvorm die het ongeschikt maakt als cryptografische hashfunctie. Om dit op te lossen, moet er het een en ander worden toegevoegd aan de constructie. En daarmee wordt de elegantie snel minder. ‘Om die verschillende aanvallen uit te sluiten, krijg je een opzet die alsmaar complexer wordt en weg beweegt van de elegante Merkle-Damgård-opzet’, zegt Van Assche. Bovendien is voor de meeste toepassingen een digest nodig die groter is dan de output van de hashfuntie. Dat kan met Merkle-Damgård, maar dan wordt de constructie weer een stap ingewikkelder. Het Keccak-team ging daarom op zoek naar een andere aanpak, eentje die simpel en elegant is en van nature bestand tegen aanvallen, en die ook langere digests kan produceren als dat nodig is - hoewel de Sha-3-standaard daar niet om vraagt.

De vier cryptografen besloten eind 2005 een team te vormen, toen de eerste aanvallen tegen Sha-1 werden gepubliceerd en geruchten over een Sha-3-competitie de kop opstaken. Een eerdere samenwerking was goed bevallen, dus ze stroopten de mouwen op en startten met de ontwikkeling van Radiogatún. Dit was bedoeld als verbetering van het Panama-algoritme dat Daemen tijdens zijn promotieonderzoek ontwikkelde, maar dat hopeloos lek bleek. ‘Radiogatún was nogal complex, met een belt en een mill en een gigantische interne toestand. In 2007 zagen we in dat het niet zou werken’, vertelt Daemen. Terwijl de deadline voor de Sha-3-competitie naderde, besloot het team het over een andere boeg te gooien.

Figuur 2: De compressiefunctie van hashalgoritmes wordt doorgaans gebaseerd op een block cipher, waar de data met behulp van een geheime sleutel in een aantal rondes wordt gemangeld. In elke ronde wordt de sleutel uit de vorige ronde bewerkt en vervolgens met een andere functie losgelaten op de data. Het is belangrijk dat de sleutel los van de data evolueert, anders is het bericht niet meer te ontcijferen. Bij hashfuncties is teruggaan echter taboe en is er een ingreep nodig om dat onmogelijk te maken: het resultaat gecombineerd met de oorspronkelijke data. Als teruggaan echter niet nodig is, is het ook niet nodig om de sleutel los van de data te muteren. Beide bewerkingen zijn dus te combineren tot een enkele functie. De input bestaat uit een sleutel en data die simpelweg achter elkaar worden geplakt.

Het inzicht kwam toen ze nog eens goed keken naar de op een block cipher gebaseerde compressiefuncties. In de basisfunctie wordt een bewerking een aantal rondes herhaald om de inputdata zo optimaal mogelijk te ‘verminken’ (Figuur 2). Vaak lukt het cryptografen nog wel om een paar rondes te ontcijferen, maar door dat aantal op te krikken, wordt het veiligheidsniveau sterk verhoogd. Elke ronde bestaat uit twee delen: eerst een permutatie van de sleutel uit de vorige ronde en vervolgens een permutatie van de data uit de vorige ronde gecombineerd met de nieuwe sleutel. Het is essentieel dat de sleutel onafhankelijk van de data wordt gemuteerd. Als die afhankelijk zou zijn, zou terugrekenen niet mogelijk zijn.

‘In ons geval hoeven we echter niet terug te kunnen rekenen. Sterker nog: we wíllen niet terug kunnen rekenen’, merkt Daemen op. In Merkle-Damgård wordt dat opgelost door de data-input te Xor’en bij de output na elke ronde. Maar eigenlijk kan het een stuk simpeler: in plaats van twee aparte functies voor het manipuleren van de sleutel en de data is één functie die één interne toestand muteert toereikend. ‘Je hebt nu niet langer een sleutel- en een datagedeelte. Je hebt alleen een linker- en rechtergedeelte, maar waar je die grens legt, is arbitrair’, legt Daemen uit. ‘In plaats van een block cipher spreken we nu liever van een permutatie.’

Deze aanpak heeft een aantal interessante eigenschappen. Zo is er niet langer een expliciete input en output. Om gegevens toe te voegen, kunnen deze tussen twee permutaties door ge-Xord worden aan de toestand. Sterker nog: de permutaties kunnen door blijven gaan zelfs als er geen data worden toegevoegd. De output bestaat uit een deel van de toestand na de permutatie.

En dat is in feite de sponsconstructie (Figuur 3). In de absorbeerfase beginnen de permutaties te lopen op een aanvankelijk lege toestand, waarbij de brokjes van de boodschap per permutatie ge-Xord worden. Daarna volgt de uitknijpfase, waarbij een deel van de toestand wordt gebruikt als digest. Mocht deze niet lang genoeg zijn, dan worden de permutaties gewoon voortgezet en na elke stap weer een deel van de output afgeroomd.

Speelgoedversies

‘We hebben nu dus een simpele constructie die een permutatie aanroept, die op zijn beurt ook weer simpel is. De permutatie is gebaseerd op een block cipher, maar zonder sleutelgedeelte. En dat is juist het slechtst begrepen gedeelte van block ciphers’, stelt Daemen.

Essentieel is dat het toevoegen en uitknijpen van data steeds op een deel van de toestand gebeurt, niet op het geheel. Op het andere deel heeft een aanvaller geen vat. De veiligheid van het algoritme groeit exponentieel met de grootte van dit gedeelte. ‘Dat is interessant, want de grootte hiervan kun je variëren, een vrijheid die je niet hebt bij Merkle-Damgård. Dus je kunt een afweging maken tussen efficiency en het beveiligingsniveau. Als je dat getal groter maakt, moet je de permutatie vaker uitvoeren om je hash op te stellen en wordt het allemaal trager, maar heb je een groter veiligheidsniveau’, aldus Daemen. De sponsconstructie is bovendien op verschillende manieren bruikbaar: voor normale hashes, maar ook voor hashes met een salt of een sleutel en zelfs voor het genereren van een sleutelstroom voor stream ciphers.

Toen het idee van de spons eenmaal geboren was, was het nog een kwestie van het vinden van een juiste permutatiefunctie: eentje die de inputbits zo veel mogelijk vermengt met alle andere inputbits en zo veel mogelijk uitsmeert over de output. Dat is in feite wat de Keccak-specificatie behelst: de beschrijving van een permutatie. Of liever gezegd: zeven verschillende permutaties, elk met een andere grootte van de interne toestand om tegemoet te komen aan de verschillende soorten hardware. De reeks bestaat uit 25-, 50-, 100-, 200-, 400-, 800- en 1600-bit-uitvoeringen. ‘Die kleinste zijn speelgoedversies, daar kun je geen echte cryptografie mee bedrijven’, zegt Daemen. ‘De grens ligt bij 100 of 200 bits, dat is afhankelijk van de toepassingen’, vult Van Assche aan. Overigens is voor Sha-3 alleen de 1600-bit-uitvoering van belang. Dat betekent minstens 200 bytes geheugen. Voor een smartcard nét te doen.

Met name voor hardware-implementaties blijkt Keccak zich goed te lenen. Uit een studie van Virginia Tech waarbij de vijf finalisten op dezelfde chip werden gezet, bleek de Belgisch-Italiaanse inzending een van de kleinste te zijn. Bovendien stak ze met kop en schouders uit als werd gekeken naar het energieverbruik per hash. Natuurlijk hebben ook de andere inzendingen zo hun merites. Bij software-implementaties blijven de prestaties van Keccak juist weer achter, met name op de high-end Intel-processoren.

Tien keer meer rekenkracht

Volgend jaar zal blijken welke van de vijf finalisten wordt verkozen tot Sha-3-standaard. Daemen en Van Assche schatten hun kansen redelijk in. De jongste ontwikkelingen hebben al een lek onthuld in een van de vijf eindkandidaten, JH. ‘We denken dat die eruit ligt’, speculeert Daemen. Of Keccak daarmee naar de voorgrond schuift, is echter niet zeker. ‘Algemeen is het idee nu dat de Skein-inzending er heel goed voor staat omdat die eigenlijk niet zo slecht is en ook vanwege de mensen die erin zitten.’ De inzending is onder meer opgesteld door Bruce Schneier - een beetje een popster in de beveiligingswereld - en ook Intel en Microsoft zijn erbij betrokken. ‘Dat zal niet op geweldig veel weerstand stuiten. Alleen in de academische wereld een beetje, die nemen Bruce Schneier niet helemaal serieus’, vertelt Daemen.

Wat wel nog een rol kan spelen, denken de leden van het Keccak-team, is dat ze bij hun permutatie niet hebben gekozen voor ARX: een methode om de bits te manipuleren waarbij (modulaire) additie, (bit)rotatie en Xor worden gebruikt. ‘De hele Sha-famillie is hierop gebaseerd, Sha-2 zelfs exclusief’, weet Van Assche. De Sha-3-kandidaten zijn alle gebaseerd op ofwel ARX ofwel Rijndael. Alleen Keccak gebruikt een alternatieve aanpak. Dat kan een rol spelen bij de uiteindelijke keuze: blijkt er een lek te zitten in een van de bestaande aanpakken, dan is Keccak waarschijnlijk nog steeds veilig.

Figuur 3: Een sponsconstructie bestaat uit een absorbatiefase, waarin de boodschap wordt ‘opgezogen’, en een uitknijpfase, waarin de digest wordt uitgeknepen. De constructie is ook te gebruiken voor wachtwoordbeveiligde en ge-salt-e hashes voor het ondertekenen van documenten, voor het genereren van pseudowillekeurige getallen en stream ciphers.

‘Die keus heeft trouwens ook te maken met side-channel attacks’, zegt Van Assche. Hierbij kijkt een kwaadwillende niet naar het algoritme zelf, maar bijvoorbeeld naar de elektromagnetische straling of het energiegebruik tijdens het hashen om zo wat van de interne toestand te achterhalen. ‘Als je hiertegen wilt beschermen, randomiseer je je data door ze op te delen en je bewerkingen op die delen uit te voeren. De interne data betekenen dan op zichzelf niet veel, maar alleen in combinatie met andere data. Maar voor additie- en Xor-bewerkingen heb je twee verschillende manieren van opdelen nodig, en het converteren tussen die twee is traag en kostbaar: dat kan wel tien keer meer rekenkracht vragen.’ Keccak kent die grote overhead niet.

Uiteindelijk beslist het Nist en alleen het Nist welke inzending het stempel ‘Sha-3-standaard’ zal krijgen. Enige willekeur speelt daarbij een rol. De prioriteit ligt eerst en vooral bij de veiligheid, maar de aanspraak die de algoritmes op de computerbronnen maken, speelt ook een belangrijke rol. Enkele kandidaten uit de tweede ronde werden afgeschoten omdat ze simpelweg te zwaar bleken. En dan zijn er nog allerlei zijdelingse overwegingen. Bij de selectie van de vijf finalisten gaf de organisatie toe een zeer goed presterende inzending zonder duidelijke veiligheidsproblemen te hebben afgeschoten vanwege het gevoel dat er toch iets niet helemaal klopte. Ook algoritmes waar te weinig over gepubliceerd werd door derden werden uitgesloten, evenals inzendingen die te veel tweaks vereisten om gevonden probleempjes op te lossen - dit gaf niet voldoende zekerheid dat ze voldoende waren uitgekristalliseerd. Ook de diversiteit van aanpakken was een factor bij de selectie van de vijf eindkandidaten. En dan wordt als het goed is gekozen voor het algoritme dat het minste weerstand oproept. ‘Ze willen een hashfunctie die nergens echt slecht in is, niet per se de beste en zeker niet eentje die goed is op één gebied maar minder in andere’, legt Van Assche uit. Deamen: ‘Ik geloof dat de uitdrukking was: een algoritme that does not suck at anything.’

Pieter Edelman

Terug naar overzicht