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.[1] |
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ab/MD5.png/300px-MD5.png)
MD5 algoritam kao ulaz koristi b-bitnu poruku gde je b proizvoljni nenegativni celi broj. Poruku možemo zamisliti kao niz bitova:
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:
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 280 kombinacija što izgleda superiorno prema težini MD5 algoritma koja iznosi 264.
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
Izvori
- ↑ http://eprint.iacr.org/2009/223.pdf