Etikettarkiv: MD5

Testa lösenord via Twitter

Twitter är på många sätt en fantastisk tjänst. En av de bättre är hur enkelt det är att via Twitters programmeringsgränssnitt koppla program och maskiner som kan lyssna på tweets, skicka status och reagera på kommandon.

En sådan tjänst är Hash Cracking Robot. Detta är en tjänst som lyssnar på tweets riktade till sig som innehåller ett kryptografiskt kondensat skapat med olika typer av algoritmer såsom MD5, SHA-1, RIPEMD-160, WHIRLPOOL m.m.

Så här ser det ut när jag testar tjänsten genom att generera kondensat med MD5 för två olika strängar med OpenSSL.

Strängar för test av PlzCrack
Strängar för test av PlzCrack

Sedan postar jag strängarna riktade till @PlzCrack på Twitter (notera att postningarna är i omvändning ordning.):

Test av hashknäckning med Twitter
Test av hashknäckning med Twitter

Lägg märke till vad som händer. PlzCrack svarar mycket snabbt. Men det är bara strängar den känner till den kan knäcka rapportera. Egentligen är tjänsten en Twitterkoppling till regnbågstabeller. Detta innebär att det bara är strängar den känner till och har kondensat för som den kan hitta. Att skicka något till PlzCrack startar inte ett automatiskt försök att uttömmande söka efter en sträng som ger kondensatet, utan det är ren uppslagning i en tabell.

Twitter begränsar hur många tweets man kan göra inom en viss tidsperiod så att använda tjänsten för att testa en stor mängd kondensat går inte. Tjänsten är mer skoj och har nog ett rätt begränsat värde, men en fördel med PlzCrack är att du slipper att själv ha gigantiska regnbågstabeller eller att generera dessa tabeller. Sedan kan man fundera på hur bra det är att på ett bublikt forum leta efter strängar till kondensat…

Kollision hittad i MD5-meddelande

(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
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
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, 0x00 har blivit 0x02. I den andra byten är det bit åtta som växlat, 0x55 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.

Vilka algoritmer används i Internetstandarder

Internet Crypto en sida skapad av säkerhetsexperten David McGrew samlar information om användning av olika typer av kryptofunktioner på Internet.

David A. McGrew
David A. McGrew

Med Internet avses i det här fallet huvudsakligen de standarder (Request For Comments – RFC) och förslag till standarder (Internet Draft – I-D) som publiceras av Internet Engineering Task Force – IETF.

Jag tycker att Internet Crypto är en bra sida eftersom den på ett bra sätt samlar och kategoriserar upp den stora mängden standarder och dokument som finns och gör det lätt att hitta. Om du exempelvis vill få reda på vilka standarder det finns för att autenticera meddelanden (Message Authentication Code – MAC) går det lätt att hitta under sin kategori. Det som dock inte finns är rekommendationer om vilka koder som är bra eller dåligt att använda.

Internet Crypto

En sak som finns är intressant kryptostatistik. Statistiken är frekvensen för hur ofta olika typer av kryptostandarder refereras i RFC:er och drafts. Detta ger i alla fall en hum om hur populära vissa algoritmer är. Tio i topp-listan ser ut som följer:

  1. Hashfunktionen MD5
  2. Hashfunktionen SHA-1
  3. Meddelandeautenticeringskoden HMAC
  4. Nyckelutbytesalgoritmen Diffie-Hellman (DH)
  5. Hashfunktionen SHA-2
  6. Blockkruptot AES
  7. Blockkryptot 3DES
  8. Asymmetriska kryptot ECC
  9. Signaturalgotritmen DSA
  10. Asymmetriska kryptot RSA

Att listan domineras av hashfunktioner samt följs av några krypton och metoder för att utbyta nycklar är inte så förvånande – detta är arbetshästarna som skapar säkerheten på Internet. Vi ser även hur AES som blockkrypto verkligen har blivit den stora de facto-standarden bland symmetriska krypton.

Däremot blir jag en aning beklämd när man klickar på listans förstaplats och tittar närmare på MD5. Hashfunktionen MD5 är en algoritm som sedan flera år tillbaka anses vara helt trasig, en algoritm kryptologer och experter rekommenderar att inte använda. MD5 är en gammal algoritm med stor spridning. Att den därför finns i många standarder (RFC:er) är inte speciellt konstigt.

Vad som gör mig beklämd är att det är så många nya, aktiva drafts, alltså förslag till standarder som refererar till MD5. Några av dessa är så kallade informations-drafts. Detta innebär att dom dokumenterar någon form av funktion på Internet, exempelvis ett specifikt applikationsprotoll någon utvecklat. Vidare finns det drafts där MD5 tas upp som varnande exempel. Men tyvärr är det fortfarande ett antal standard-drafts där MD5 pekas ut som komponent att använda.

Vill vi komma bort från en algoritm vi vet inte är säker måste sluta bygga in nya beroenden av algoritmen i framtida standarder. Att 2011 designa något som använder MD5 är fel och det borde ringa varningsklockor. Massor med klockor. Högt och ljudligt. Om du ser någon som ritar, skissar, skriver in MD5 i en ny konstruktion – hjälp denne att komma på bättre tankar. Att byta ut en algoritm är mycket billigare när konstruktionen bara är på designstadiet, inte ute i fält i miljontals burkar i skogen. Att tänka efter före är inte lätt, men i fallet MD5 är det inte så svårt.

Samtidigt sprang jag på en informations-RFC, RFC 5218 – What Makes for a Successful Protocol? som försöker förklara och beskriva varför vissa standarder blir framgångsrika (som MD5 och IPv4). Utan att avslöja för mycket kan jag säga att bästa tekniken inte alltid vinner.