På konferensen Fast Software Encytption 2006 (FSE 2006) som hölls i Graz i förra veckan presenterades ännu fler attacker mot MD5.

John Black, Martin Cochran och Trevor Highland presenterade artikeln A Study of the MD5 Attacks: Insights and Improvements. Enligt sammanfattningen för artikeln beskriver föfattarna:

MD5 is a well-known and widely-used cryptographic hash function. It has received renewed attention from researchers subsequent to the recent announcement of collisions found by Wang et al. To date, however, understanding the method used by researchers in this work has been fairly difficult to grasp. In this paper we conduct a study of all attacks on MD5 starting from Wang. We explain the techniques used by her team, give insights on how to improve these techniques, and use these insights to produce an even faster attack on MD5. Additionally, we provide an “MD5 Toolkit” implementing these improvements that we hope will serve as an open-source platform for further research. Our hope is that a better understanding of these attacks will lead to a better understanding of our current collection of hash functions, what their strengths and weaknesses are, and where we should direct future efforts in order to produce even stronger primitives.

De senaste två åren har det kommit flera olika nya metoder att attackera olika kryptofunktioner. Några som suttit illa till är kryptgrafiska enväfsfunktioner – hashfunktioner. Speciellt arbetshästarna MD5 och SHA-1 har drabbats av flera attacker.

Hashfunktioner är funktioner där indata av godtycklig längd ger upphov till utdata av en given längd – en signatur för indatat. Hashfunktioner används inom ett stort antal områden inom elektronik och IT, exempelvis som nycklar i databaser, uppslagningar i cacheminnen, routrar och mycket mer. Eftersom indatat kan vara längre än den genererade signaturen är hashfunktionen väsentligen en många till en-funktion.

Det som gör den kryptografiska hashfunktionen speciell är att det från en given signatur är omöjligt att komma fram till vilken insignal som ger upphov till signaturen. Den kryptografiska hashfunktionen kallas därför för envägsfunktion – den går inte att backa. Det är i alla fall det som är tanken. En attack mot en envägsfunktion går ut på att på olika sätt hitta indata som ger upphov till en given signatur. Och nu har det kommit en del resultat.

Det finns ett projekt som heter HashClash som letar efter kollisioner i MD5. Som en del i arbetet med HashClash har man nu hittat en metod dom gör att man med en PC kan hitta kollisioner inom ca en minut, och med viss information om storlek på indatat inom några få sekunder. Den korta tid det tar att hitta en kollision med deras metod gör att MD5 nu verkligen bör uteslutas som kryptografisk hashfuntion. Det finns en artikel av Marc Stevens som förklarar den nya metoden och mer information inklusive källkod finns på den här webbplatsen.

Och i stort sett samtidigt som Marc Stevens publicerade sina resultat dök ännu en artikel upp som presenterar en metod för att snabbt hitta kollisioner för MD5. Artikeln i fråga heter Tunnels in Hash Functions: MD5 Collisions Within a Minute och metoden som presenteras hittar kollisioner på i stort sett samma tider som de som Marc Stevens presenterade.

Det är spännande men samtidigt skrämmande hur fort utvecklingen har gått vad gäller att förbättra tiderna för att hitta kollisioner. Tyvärr är det som jag uppfattat det oklart om hur väl SHA-2-familjen är skyddade mot attacker, den workshop NIST arrangerade i höstas gav som tolkade informationen inga klara besked. Hashfunktioner är en vital del av modern, säker kommunikation, så vi behöver säkra funktioner.

NIST har släppt ett förslag till en uppdatering av standarden för digitala signaturer (DSS). Den nuvarande standarden är FIPS 186-2. I förslaget till det som kommer att bli FIPS 186-3 definieras ett antal nya signaturer baserade på hashfunktionerna i SHA-2 (FIPS 180-2). De nya signaturerna är:

• 1024-bit nyckel, 160-bit hash (nuvarande DSA)


• 2048-bit nyckel, 224-bit hash (baserad på SHA-224)


• 2048-bit nyckel, 256-bit hash (baserad på SHA-256)


• 3072-bit nyckel, 256-bit hash (baserad på SHA-256)

Det är bra att NIST tar fram en uppdaterad version DSS, inte så mycket för att få fram signaturer med längre nycklar. Nej som jag ser det är den stora vinsten att komma bort från beroendet av SHA-1. Sedan kvarstår långsiktigt frågeställningen om SHA-2 verkligen är pålitliga, både som envägsfunktioner och som bas i signaturalgoritmer.