Gebroken codes

Een tot voor kort onbekende Chinese wiskundige heeft de afgelopen anderhalf jaar de cryptografie op zijn kop gezet. Zij kraakte beveiligingscodes die onkraakbaar leken. Rob van den Berg

Zelfs een bijna onkraakbaar geachte code van de Amerikaanse National Security Agency (NSA) blijkt niet veilig voor de Chinese wiskundige Xiaoyun Wang. In augustus 2004 werd al bekend dat ze een tot dan toe veel toegepast algoritme voor het beschermen van gegevens had weten te kraken. Nu blijkt ze dus een zwakke plek te hebben ontdekt in dat veel ingewikkelder algoritme van de NSA. Deze beveiligingscode wordt alom toegepast, bij het beschermen van 'veilige' internet-sites of het veilig opslaan van wachtwoorden, tot aan het uitwisselen van digitale handtekeningen. Sinds Xiaoyun ('klein wolkje') Wang, van de universiteit van Shandong zich heeft gemeld is dat allemaal minder veilig geworden.

Wang en haar onderzoeksgroep richten de aandacht op de zogeheten hash-algoritmen. Dit zijn wiskundige formules die uitgaan van een bestand van willekeurige lengte en vervolgens een reeks van minder dan tweehonderd enen en nullen produceren (een string) die karakteristiek is voor het betreffende bestand.

Een hash is echt een soort vingerafdruk; als je in het oorspronkelijke bestand ook maar één enkele bit verandert, verandert de hash ook', vertelt Benne de Weger, een cryptografie-onderzoeker van de Technische Universiteit Eindhoven. Daardoor stelt hij je in staat om te bepalen of er met documenten is geknoeid. Van een document wordt een hash berekend, die vervolgens met het document wordt meegestuurd. De ontvanger berekent dan zelf ook de hash en kan zo heel snel controleren of er met het document is geknoeid.'

Om dit soort bescherming te kunnen bieden moet een hash aan verschillende voorwaarden voldoen. Allereerst mag het niet mogelijk zijn om uit een hash de oorspronkelijke data terug te rekenen. De hash moet als een fuik fungeren: je kunt er wel in, maar niet uit. Daarnaast zouden er ook geen twee documenten mogen bestaan met dezelfde hash, iets wat in het jargon een botsing heet. Aan beide voorwaarden leek tot nu toe te worden voldaan. Tot Xiaoyun Wang zich ermee begon te bemoeien.

botsing

Er bestaan talloze manieren om data te hashen, maar de twee die Wang heeft gebroken, MD5 en SHA-1, zijn de bekendste. MD5, dat in 1991 is ontwikkeld door Ron Rivest van MIT in Boston, zou niet veel meer toegepast worden, maar De Weger vindt het nog verrassend vaak op websites terug. De Weger: Om voor MD5 waarvan de hash 128 bits lang is een botsing te vinden, moet iemand die willekeurig enen en nullen achter elkaar zet gemiddeld 2

Wang komt botsingen op het spoor door zorgvuldig na te gaan wat er gebeurt met de data tijdens het hashen. Wanneer je begint met twee documenten die aanvankelijk maar in een paar bits verschillen, en bijhoudt hoe die twee door het hash-algoritme lopen, kun je een gevoel krijgen wanneer botsingen optreden. Samen met haar student Hongbo Yu en anderen schreef ze zelfs een programma dat volautomatisch botsingen in MD5 opzoekt. De Weger: Wang publiceerde haar methode tijdens Eurocrypt 2005 in Aarhus in twee artikelen en ontving daarvoor de best paper award. In plaats van 264 willekeurige reeksen hoeft ze er maar 239uit te proberen. Dat zijn er nog altijd een heleboel maar met een snelle pc heb je dat binnen een dag voor elkaar.' Duitse wiskundigen publiceerden vlak daarna een methode om een valse digitale handtekening te zetten onder een postscript- of pdf-document. De Weger: Daarvoor maakten ze gebruik van het feit dat als je eenmaal twee botsende strings hebt, je er een willekeurig aantal bits achter aan kunt zetten zonder dat de botsing verloren gaat. Dat soort fraude is overigens wel op te sporen.'

zwakheden

Met hulp van Xiaoyun Wang ontwikkelde De Weger een methode om misbruik te maken van de door haar ontdekte zwakheden in hash algoritmen. Hij houdt zich al een tijd bezig met zogeheten certificaten. Dat zijn door een instantie als het Amerikaanse Verisign uitgegeven elektronische documenten waarmee een bedrijf kan aantonen dat zijn website te vertrouwen is.

De Weger: Als je via je browser contact zoekt met je bank om via het internet te kunnen bankieren, dan wil je zeker weten dat je écht met die bank verbonden bent, en niet met een crimineel die zich alleen maar als zodanig voordoet. Dat gebeurt via een certificaat waarin onder andere de cryptografische sleutel staat die je browser nodig heeft om met de bank te kunnen communiceren. (Je kunt zo'n certificaat als gebruiker inzien door te klikken op het slotje van een beveiligde website - RvdB). De digitale handtekening die aan het certificaat hangt garandeert dat de sleutel van de bank afkomstig is. Je browser heeft dan overigens al vastgesteld dat het om een gecertificeerde website gaat door de digitale handtekening van het certificaat via zijn hash te controleren.'

Sinds de doorbraak van Wang valt er met dergelijke certificaten te rommelen. Samen met zijn Eindhovense collega Arjen Lenstra wist De Weger twee verschillende certificaten te maken met een identieke hash. Ze deden dat met behulp van twee botsende strings die Xiaoyun Wang ze op bestelling had geleverd. De Weger: We wilden de botsende strings verstoppen in de cryptografische sleutel van het certificaat. Dan valt het niet op, want zo'n sleutel ziet er volkomen willekeurig uit. Zo'n sleutel moet echter wel voldoen aan allerlei voorwaarden, dus daar moest Xiaoyun rekening mee houden. Dat bleek geen enkel probleem. Ze had er maar één dag voor nodig.'

Wang ging ondertussen gewoon door. Tot ontzetting van veel cryptografen kondigde ze vorig jaar aan dat ze ook een zwakke plek SHA-1 had ontdekt en de aanval had ingezet. SHA-1 dat door het Amerikaanse NSA werd ontwikkeld heette veel veiliger te zijn dan MD5 en wordt daarom veel meer gebruikt. Het ligt ten grondslag aan het zogeheten Secure Sockets Layer (SSL) protocol dat de communicatie verzorgt met beveiligde sites en tevens gebruikt wordt om informatie als nummers van creditkaarten via het internet te versturen. Wangs aankondiging was dan ook aanleiding voor een heuse cryptografische crisis. Volgens de New York Times was dat de reden waarom ze in augustus vorig jaar geen visum meer kreeg om in de Verenigde Staten over haar onderzoek te komen vertellen.Het tekent de paniek die haar werk veroorzaakt.