QED

De Technische Universiteit Eindhoven heeft zijn Afstudeerprijs 2008, een prijs voor de beste ingenieur van de TU/e, toegekend aan ir. Marc Stevens voor zijn afstudeerproject On collisions for MD5 waarop hij in juni 2007 afstudeerde met een 10. Het onderzoek van de wiskundig ingenieur gaat over het maken van botsingen voor de hashfunctie MD5. Een hashfunctie is een wiskundige functie die als invoer een rij bits van willekeurige lengte accepteert en als uitvoer een rij bits van vaste lengte oplevert, de zogenaamde hashwaarde. De bedoeling is dat een hashwaarde de invoer op unieke wijze kan representeren, als een soort digitale vingerafdruk. Een botsing voor een hashfunctie is een tweetal verschillende rijen bits met dezelfde hashwaarde. Een goede hashfunctie moet echter botsingbestendig zijn en veilige protocollen vereisen botsingbestendige hashfuncties. Het geldbedrag voor de afstudeerprijs is 2500 euro.

In het begin van dit jaar schreef ik in mijn rubriek “Focus op veiligheid” van het Nederlandse blad Linux Magazine over het werk van Stevens. Ondertussen werkt hij voor het Amsterdamse Centrum voor Wiskunde en Informatica. Samen met Arjen Lenstra van de Ecole Polytechnique Fédérale de Lausan en Benne de Weger van de Technische Universiteit Eindhoven heeft Stevens eind vorig jaar twee verschillende Windows-programma’s kunnen aanmaken met identieke MD5 hashwaarden. De onderzoekers hebben zo in hun project HashClash aangetoond dat MD5 voor het verifiëren van de integriteit of bron van software zo zijn problemen heeft.

In 2004 al toonde professor Xiaoyun Wang aan dat er voor MD5 botsingen kunnen gemaakt worden, maar haar constructie bleef theoretisch: het tweede bestand met dezelfde hashwaarde kon men in haar constructie niet willekeurig kiezen, zodat er weinig misbruik van kon gemaakt worden. Stevens, Lenstra en de Weger bouwden echter voort op Wangs aanval en slaagden erin om chosen-prefix collisions te construeren. Dit wil zeggen: voor elke twee willekeurige bestanden kan de aanval eenzelfde hashwaarde vinden door aan beide bestanden achteraan informatie toe te voegen. Heel wat bestandsformaten laten immers toe om achteraan het bestand willekeurige gegevens toe te voegen, die genegeerd worden. Zo ook bij uitvoerbare Windows-bestanden. Neem een onschuldig ‘Hello world’-programma, kies een schadelijk programma en voer de aanval uit die achteraan beide programma’s willekeurige bytes toevoegt totdat ze dezelfde MD5-hashwaarde hebben.

Voor een bestaand bestand met een bekende MD5-hashwaarde een bestand maken met dezelfde hashwaarde is nog niet mogelijk. Door middel van een brute force zoektocht kan men wel bijvoorbeeld de eerste drie en laatste drie bytes van de hashwaarde laten overeenkomen met het doelbestand. Aangezien veel mensen een MD5-waarde vlug controleren door een paar bytes te vergelijken, kan dit al effectief zijn. Stevens en zijn collega’s voerden de berekening overigens in twee dagen tijd uit op een PlayStation 3, die meerdere processorkernen heeft en op elke kern MD5 op verschillende gegevens tegelijk kan uitvoeren. De spelconsole is voor deze toepassing even krachtig als 30 pc’s, en dat hebben al meerdere onderzoekers ontdekt.