(Uppdaterad 2012-01-03 med korrektur)
2010 publicerade säkerhetsforskarna Tao Xie och Dengguo Feng en artikel om att de funnit en kollision hos hasfunktionen MD5 mellan två meddelanden som bara är ett block stort.
En kollision innebär att två olika meddelanden ner dom används som indata till en hashfunktion ger samma hashvärde. MD5, precis som andra kryptografiska hashfunktioner delar upp ett meddelande i ett antal block med en fix storlek. För MD5 är blockstorleken 512 bitar. Innan Xie och Fengs artikel hade det presenterats kollisioner för meddelanden som är större än ett block. Detta är enklare då det ger utrymme för att bygga på ett meddelande med bitmönster som gör att en kollision uppstår. Men för ett meddelande som är exakt ett block finns inte den möjligheten. En kollision på ett block kräver att hashfunktionens förmåga att skydda mot att räkna ut indata från ett givet hashvärde har brutits. Hashfunktionen är inte längre en evägsfunktion.
Xie och Feng presenterade i sin artikel två meddelanden på exakt 512 bitar som gav samma hashvärde:
Xie och Fengs kollision från 2010
Det Xie och Feng däremot inte gjorde var att berätta hur dom lyckats skapa sin kollision. Författarna hänvisar till att dom av säkerhetsskäl stoppats från att berätta hur dom gjort. Dom skriver:
Today, in the last month (Dec,) of 2010, we have to make public a result of our 1-block collision attacks on MD5 in Table 1 as below, which was actually
obtained at the beginning of 2010, but for security reasons, the techniques are not allowed to be disclosed at the moment.
Intressant nog utmanar istället Xie och Feng sina kollegor i världen att återskapa deras resultat genom att hitta ett annat par av meddelanden ned en storlek på ett block som ger en kollision i MD5:
Here, we are calling for a challenge to the cryptology community that, any one who first gives a new different 1-block collision attack on MD5 will win 10,000 US dollars (about 50,000 RMB in Chinese Yuan) as a reward for his (her) excellent work. This call for challenge will be ended on Jan 1st, 2013. This announcement’s first affiliated unit will be responsible for this amount of reward when a new different 1-block collision attack is received and verified.
Det som hänt nu är att Marc Stevens ser ut att vara den första att möta utmaningen. I en artikel publicerad 29 januari i 2012 presenterar Marc sina meddelanden och den kollision som detta ger:
Marc Stevens meddelanden som ger kollision i MD5
Det första man kan lägga märke till är att det är andra meddelanden är de Xie och Feng använt. Notera även att det är två ställen i meddelandena som skiljer. I den första av dessa bytes är det bit två som växlat, 0×00 har blivit 0×02. I den andra byten är det bit åtta som växlat, 0×55 har blivit 0xd5.
Till skillnad från Xie och Feng tvekar inte Marc att berätta hur han gjort och i artikeln finns en redovisning av såväl bakomliggande teori och mekanismer samt den algoritm som Marc använt för att utföra sökningen av kollisionen. Enligt Marc skulle det med hans nya metod krävas 2**49.81, dvs ungefär 987 biljoner MD5-operationer för att hitta en kollision. Marc skattade att detta skulle ta maximalt fem veckors körtid, vilket innebär at han räknade med att kunna göra drygt 300 miljoner MD5-operationer per sekund. Detta var tillräckligt lite tid för att Marc skulle bedöma det som rimligt och startade därför sökningen. Med lite tur fick han träff efter tre veckor.
Skälet till att Marc lyckades och att MD5 är så svag är att lavineffekten hos MD5 är för svag och ojämnt fördelad över bitarna i det genererade hashvärdet. Lavineffekten innebär att en liten förändring av indata snabbt ska påverka många bitar i interntillståndet som i slutändan ger hashvärdet. Eller omvänt, varje bit i det genererade hashvärdet ska bero av många bitar i meddelandet. I fallet att meddelandet är lika stort som hashfunktionen innebär detta att varje bit i hashvärdet ska bero av många bitar i blocket. Tyvärr gäller inte detta för MD5. På grund av att den har så få iterationer sker inte en bra och jämn mixning. Vissa bitar i hashvärdet hos MD5 beror av väldigt få bitar. Detta kallas för en hashtunnel, ett begrepp och fenomen Vlastimil Klima presenterade 2006. Skillnaden i hur lavineffekten förklarar även den större varians jag fick för MD5 när jag gjorde bittester av hashfunktioner.
För den som själv vill pröva på att generera kollisioner hos meddelanden på enstaka block hos MD5 har Marc släppt ett program. Källkoden har Marc ännu inte släppts. Men koden, programmet, artikeln, meddelandena etc finns på Marcs egen sida.
Så vad är kontentan? Det första är att Xie och Fengs tävling har avgjorts och att Marc Stevens är att gratulera till ett bra utfört arbete. Förhoppningsvis får nu Xie och Feng chans att publicera information om hur dom gick tillväga. Att tvinga dom att hålla sin metod hemlig gav ett knappt års fördröjning av en publicerad metod. Att hemlighålla information om svagheter som ändå redan är kända har återigen visat sig inte vara en långsiktigt hållbar. Och någon får dessutom betala 10.000 USD.
För oss alla andra är väl detta bara ännu ett bevis på att MD5 inte skall användas och bör fasas ut till förmån för bättre hashfunktioner (exempelvis SHA-256). SHA-256 har inte bara fler iterationer och en bättre mixningsfunktion, den har även ett hashvärde på fler bitar – 256 bitar gentemot 128 bitar för MD5. Hashvärdet för MD5 är i dag så kort att det är inom gränsen för att praktiskt göra uttömmande sökningar och bygga upp tabeller med meddelanden och deras hashvärden, så kallade regnbågstabeller.
I dag fyller Piratpartiets grundare, Rick Falkvinge 40 år. Det vill vi så klart uppmärksamma här på hemsidan. Om Rick inte hade grundat partiet hade vi alla haft betydligt mer fritid, men å andra sidan hade det funnits mycket mindre hopp för världen och framtiden. :-)
