MD4

MD4

Opšte
Projektant(i)	Ronald Lin Rivest
Datum objave	Oktobar 1990.
Serija	MD2, MD4, MD5, MD6
Detalji
Veličina sažimanja	128 bita
Runde	4
Najbolja javna kriptoanaliza
Napad kolizijom, objavljen 2007. godine, može da nađe kolizije za manje od 2 heš operacije.

MD4 (Message-Digest algorithm 4) algoritam je haš funkcija, koja za ulazni tekst daje izlaz fiksne veličine - 128 bitova. Mala promjena u ulaznim podacima rezultovaće značajnim promenama na izlazu. MD4 se smatrao sigurnim, jer je zahtevao ogromnu količinu procesorske snage da se pronađe ulazni niz koji za izlaz daje neki poznati haš. Drugim rečima - ne postoji način da se dekriptira izlaz. No s vremenom su mu pronađeni nedostaci, te umesto njega (i verzije MD5) radije koristi SHA-1 algoritam koji rezultuje 160-bitnim izlazom.

Nastanak algoritma

Autor MD4 je profesor sa MIT-a Ronald Rivest, takođe i autor algoritama MD2 i MD5. MD2 je prilagođen izvođenju na 8-bitnim procesorima dok su MD4 i MD5 dizajnirani za 32-bitne procesore.

MD4 nastao je 1990. godine i najbrži je među njima. Pokazao se nepouzdanim i zato ga je nasliedio MD5 koji je vrlo sličan MD4 ali ima neke dodatne funkcije koje ga čine sporijim, ali zato puno sigurnijim. Na osnovama MD4 nastali su sledeći algoritmi: MD5,SHA-1,RIPEMD.

Opis algoritma

Pretpostavimo da imamo poruku dužine b bita.

Korak 1.

Poruka se proširi tako da je njena dužina u bitovima plus 64 deljiva sa 512. Poruka se uvijek produžuje, čak i kad je uslov deljivosti već zadovoljen. To se vrši na slijedeći način : Jedan bit vriednosti "1" dodamo na kraj poruke, a zatim dodajemo "0" sve dok dužina poruke plus 64 bita nije deljiva sa 512. Sveukupno možemo dodati najmanje jedan i najviše 512 bitova.

Korak 2.

Dužinu originalne poruke (tj. poruke pre nego što smo je proširili) b prikažemo sa 64 bita i taj broj dodamo na kraj proširene poruke koju smo dobili u prošlom koraku. Ako bi originalna poruka bila duža od 264 znakova tada se na kraj poruke dodaje samo nižih 64 bita. Bitovi se dodaju kao dve 32-bitne reči tako da se prvo doda reč koja sadrži niže bitove, a zatim reč koja sadrži više bitove. U ovom trenutku dužina poruke je 16 32-bitnih reči. Označimo sada svaku pojedinu reč sa

M[0 ... N-1] 

gde je N sadržalac 16.

Korak 3. Inicijalizacija MD bafera

Bafer dužine 4 reči (A, B, C, D) se koristi za izračunavanje sažetka poruke. A,B,C,D su 32-bitni registri sa sledećim početnim vrednostima zadanim heksadecimalno (najmanje važan oktet je A, najvažniji je D).

word A: 01 23 45 67
word B: 89 AB CD EF
word C: FE DC AB 98
word D: 76 54 32 10

Korak 4. Procesiranje poruke u blokovima od 16 reči

Prvo definišemo tri pomoćne funkcije tako da svaka koristi kao ulaz 3 reči dužine 32 bita kao izlaz daju jednu reč dužine 32 bita.

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XY v XZ v YZ
H(X,Y,Z) = X xor Y xor Z

Funkcija F se ponaša kao uslovna funkcija: ako X onda Y inače Z. Funkcija G se ponaša kao većinska funkcija : ako bilo koja 2 ulaza x,y ili z na nekoj bit poziciji imaju '1' onda će i izlaz na toj poziciji imati '1'. Funkcija H je XOR funkcija sa svojstvima sličnim funkcijama F i G.

Nakon toga izvršimo sledeći pseudokod :

 // procesiraj svaki blok poruke
 za i=0 do (N/16-1) čini
      // kopiraj blok i u X
      za j=0 do 15 čini
             X[j] = m[i*16+j]
      kraj
      // sačuvaj A,B,C,D
      AA=A
      BB=B
      CC=C
      DD=D
      // 1. KRUG
      // označimo sa [abcd k s] operaciju:
      //                                 a = (a + F(b,c,d) + X[k]) <<< s
      // '<<<s' je rotacija u levo za s bitova
      [ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
      [ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]
      [ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]
      [ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]
      // 2. krug
      // označimo sa [abcd k s] operaciju:
      //                                 a = (a + G(b,c,d) + X[k] + 5A827999) <<< s
      [ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13]
      [ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13]
      [ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13]
      [ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]
      // 3. krug
      // označimo sa [abcd k s] operaciju:
      //                              a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s
      [ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15]
      [ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15]
      [ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15]
      [ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
      // na kraju svaki registar uvećamo sa vrijedošću koju je
      // imao pre izvršenja ovog bloka programa
      A = A + AA
      B = B + BB
      C = C + CC
      D = D + DD 
      //kraj

Primer

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

MD4("The quick brown fox jumps over the lazy dog") = 1bee69a46ba811185c194762abaeae90

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

MD4("The quick brown fox jumps over the lazy cog") = b86e130ce7028da59e672d56ad0113df

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

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0