MD5

MD5

Opšte
Projektant(i)	Ronald Lin Rivest
Datum objave	April 1992.
Serija	MD2, MD4, MD5, MD6
Detalji šifre
Veličina sažimanja	128 bita
Struktura	Merkl-Damgard konstrukcija
Runde	4
Najbolja javna kriptoanaliza
Napad u 2009. godini od strane Taoa Ksia i Dengoa Fenga razbio je MD5 otpornost na koliziju za 220.96 vreme. Napad je trajao nekoliko sekundi na običnom računaru.

MD5 (engl. Message-Digest algorithm 5) je kriptografski algoritam koji spada u grupu haš algoritama ili algoritama za sažimanje (ovi algoritmi se još nazivaju i digest, ireverizibilni ili algoritmi bez ključa ) i bio je veoma je primenjen u mnogim oblastima zaštite podataka, mada se danas smatra podložnim kriptografskim napadima tako da se ređe primenjuje u kriptografiji, ali je našao veoma čestu primenu u proveri integriteta većih fajlova zbog svoje brzine. Dužina digesta (digest se može prevesti kao sažetak) je 128 bita.

Nastanak algoritma

MD5 algoritam je razvio 1991. godine Ronald Rivest. Baziran je na MD4 algoritmu, i iako je nešto sporiji od MD4 algoritma, MD5 je mnogo sigurniji. Veličina digesta, kao i broj dodatnih bitova dodatih izvornoj poruci su ostali isti. Zbog razloga što je MD4 algoritam razvijen s namerom da bude najbrži algoritam, algoritam se nalazio „na samom rubu“ u pogledu rizika uspešnih kriptoanalitičkih napada. Pri razvoju MD5 algoritma, programeri su se odrekli određenog koeficijenta brzine izvođenja kako bi ostvarili veću sigurnost.

Razbijanje MD5 algoritma

Dužina digesta ovog algoritma je 128 bita, čemu mnogi kriptoanalitičari zameraju ovom algoritmu tako da se smatra da je podložan brute force birthday attack. Jedan takav projekat pod imenom MD5CRK je pokrenut 1. marta 2004. godine sa namerom da dokažu da ovaj algoritam nije siguran. Ne dugo zatim 17. avgusta 2004. objavljeno je da su Ksiaoun Vang, Denguo Feng, Ksuejia Lai i Ksongbo Ju (Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu) uspešno razbili algoritam odnosno da su pronašli koliziju na algoritmu. Za razbijanje ovog algoritma bilo im je potreban samo jedan sat na IBM p690 klasteru.

1. marta 2005. Arjen Lenstra, Ksiaoun Vang, i Bene de Veger demonstrirali su kreiranje dva X.509 sertifikata sa različitim javnim ključevima ali istim MD5 digestom. Nekoliko dana potom Vlastimil Klima je kreirao unapređeni algoritam koji je u stanju da na običnom lap topu za nekoliko sati kreira koliziju MD5 algoritma.

Primena

Zbog pronađenih nedostataka ovog algoritma, danas se sve ređe koristi u kriptografiji za potpisivanje digitalnih sertifikata i skladištenje šifri i umesto njega se najčešće koriste neki drugi algoritmi, kao na primer SHA-1, WHIRLPOOL, RIPEMD-160. Danas se ovaj algoritam najčešće primenjuje za proveru integriteta fajlova (engl. checksum, kontrolni zbir).

Opis algoritma

Slika 3. Jedna MD5 operacija - MD5 se sastoji od 64 ovih operacija, grupisanih u četri koraka od 16 operacija. F je nelinearna funkcija; jedna funkcija se koristi za svaki korak. M_i predstavlja 32-bitni blok ulazne poruke, i K_i predstavlja 32-bitnu konstantu, drugačiju za svaku operaciju.

MD5 algoritam kao ulaz koristi b-bitnu poruku gde je b proizvoljni nenegativni celi broj. Poruku možemo zamisliti kao niz bitova:

$m0m1m2...m{b-2}m{b-1}$

Poruka se mora nadopuniti bitovima kako bi njena dužina (u bitovima) odgovarala broju 448 moduo 512. Drugim rečima, poruka se mora proširiti tako da joj nedostaju 64 bita da njena ukupna dužina u bitovima bude deljiva sa 512.

Najčešći način proširivanja poruke je da se prvo poruci doda jedan „1“ bit, a zatim slijede bitovi „0“. Tako će se poruci u najmanju ruku dodati samo jedan bit, a u najgorem slučaju 512 bita.

Nakon proširenja poruke, poruci je potrebno dodati 64-bitnu reprezentaciju broja b (b je dužina izvorne poruke pre njenog proširenja). U slučaju da se dužina poruke ne može prikazati pomoću 64 bita, poruci se dodaju samo nižih 64 bita. Bitovi reprezentacije broja b se dodaju poruci kao dve 32-bitne reči, pri čemu je reč manje težine prva pridodata.

Nakon proširenja poruke i dodavanja bitova reprezentacije dužina poruke mora biti deljiva sa 512. Odnosno, poruka mora imati dužinu deljivu sa 16 (32-bitnih) reči. Sada poruku možemo prikazati kao:

$M[0,1,...,N-1]$
gde je N deljivo sa 16.

Nakon što je poruka pripremljena za MD5 algoritam, potrebno je inicijalizirati 128-bitni MD bafer. MD bafer se sastoji od četiri 32-bitnih reči A, B, C i D. Kao inicijalne vrednosti reči u heksadecimalnom sistemu se koriste: A=67452301, B=EFCDAB89, C=98BADCFE i D=10325467.

Posle inicijalizacije pokreće se MD5 algoritam koji se ponovo izvodi za svakih sledećih 512 bita poruke. Samo jezgro algoritma predstavlja kompresijska funkcija koja se sastoji od četiri ciklusa. Svaki od četiri ciklusa ima sličnu strukturu, ali svaki koristi drugačiju primitivnu logičku funkciju F, G, H ili I. Konačan rezultat predstavljaju vrednosti u registrima A, B, C i D koje se zbrajaju sa njihovim inicijalnim vrednostima. Svaki od tih četiri registara predstavlja jednu četvrtinu digesta ulazne poruke.

Primer

Primer primene MD5 algoritma. Rečenicu u ASCII formatu „The quick brown fox jumps over the lazy dog“ pustićemo kroz MD5 algoritam i dobićemo 128-bitni izlaz u heksadecimalnom obliku

MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6

Čak i najmanja promena tip jednog slova u rečenici imaće kao rezultat promenu heksadecimalnog izlaza. Na primer promenićemo d u c:

 MD5("The quick brown fox jumps over the lazy cog") = 1055d3e698d289f2af8663725127bd4b

Izlaz MD5 funkcije u slučaju praznog stringa biće:

 MD5("") = d41d8cd98f00b204e9800998ecf8427e

Upoređenje MD5, SHA-1 i RIPEMD-160 algoritma

32 bita duži digest SHA-1 i RIPEMD-160 algoritama su glavne prednosti tih algoritama u odnosu na MD5. Težina dobijanja identičnog digesta za dve različite poruke tim algoritmima sa 2⁸⁰ kombinacija što izgleda superiorno prema težini MD5 algoritma koja iznosi 2⁶⁴.

Upoređenja SHA-1 algoritma sa MD5 algoritmom pokazuju da je SHA-1 algoritam sigurniji od MD5 algoritma.

	MD5	SHA-1	RIPEMD-160
Dužina digesta	128 bitova	160 bitova	160 bitova
Dužina bloka	512 bitova	512 bitova	512 bitova
Broj koraka	64 (4 x 16)	80 (4 x 20)	160
Najveća dužina poruke	-	2^64-1 bitova	2^64-1 bitova
Primitivnih logičkih funkcija	4	4	5
Broj konstanti	64	4	9
Zapis bitova	Little endian	Big endian	Little endian

3