МД4

MD4

Опште
Пројектант(и)	Роналд Лин Ривест
Датум објаве	Октобар 1990.
Серија	MD2, MD4, MD5, MD6
Детаљи
Величина сажимања	128 бита
Рунде	4
Најбоља јавна криптоанализа
Напад колизијом, објављен 2007. године, може да нађе колизије за мање од 2 хеш операције.

MD4 (Message-Digest algorithm 4) алгоритам је хаш функција, која за улазни текст даје излаз фиксне величине - 128 битова. Мала промјена у улазним подацима резултоваће значајним променама на излазу. MD4 се сматрао сигурним, јер је захтевао огромну количину процесорске снаге да се пронађе улазни низ који за излаз даје неки познати хаш. Другим речима - не постоји начин да се декриптира излаз. Но с временом су му пронађени недостаци, те уместо њега (и верзије MD5) радије користи SHA-1 алгоритам који резултује 160-битним излазом.

Настанак алгоритма

Аутор MD4 је професор са МИТ-а Роналд Ривест, такође и аутор алгоритама MD2 и MD5. MD2 је прилагођен извођењу на 8-битним процесорима док су MD4 и MD5 дизајнирани за 32-битне процесоре.

MD4 настао је 1990. године и најбржи је међу њима. Показао се непоузданим и зато га је наслиедио MD5 који је врло сличан MD4 али има неке додатне функције које га чине споријим, али зато пуно сигурнијим. На основама MD4 настали су следећи алгоритми: MD5,SHA-1,RIPEMD.

Опис алгоритма

Претпоставимо да имамо поруку дужине б бита.

Корак 1.

Порука се прошири тако да је њена дужина у битовима плус 64 дељива са 512. Порука се увијек продужује, чак и кад је услов дељивости већ задовољен. То се врши на слиједећи начин : Један бит вриедности "1" додамо на крај поруке, а затим додајемо "0" све док дужина поруке плус 64 бита није дељива са 512. Свеукупно можемо додати најмање један и највише 512 битова.

Корак 2.

Дужину оригиналне поруке (тј. поруке пре него што смо је проширили) б прикажемо са 64 бита и тај број додамо на крај проширене поруке коју смо добили у прошлом кораку. Ако би оригинална порука била дужа од 264 знакова тада се на крај поруке додаје само нижих 64 бита. Битови се додају као две 32-битне речи тако да се прво дода реч која садржи ниже битове, а затим реч која садржи више битове. У овом тренутку дужина поруке је 16 32-битних речи. Означимо сада сваку поједину реч са

M[0 ... N-1] 

где је N садржалац 16.

Корак 3. Иницијализација МД бафера

Бафер дужине 4 речи (А, B, C, D) се користи за израчунавање сажетка поруке. A,B,C,D су 32-битни регистри са следећим почетним вредностима заданим хексадецимално (најмање важан октет је А, најважнији је 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

Корак 4. Процесирање поруке у блоковима од 16 речи

Прво дефинишемо три помоћне функције тако да свака користи као улаз 3 речи дужине 32 бита као излаз дају једну реч дужине 32 бита.

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

Функција F се понаша као условна функција: ако X онда Y иначе Z. Функција G се понаша као већинска функција : ако било која 2 улаза x,y или z на некој бит позицији имају '1' онда ће и излаз на тој позицији имати '1'. Функција Х је XOR функција са својствима сличним функцијама F и G.

Након тога извршимо следећи псеудокод :

 // 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

Пример

Пример примене MD4 алгоритма. Реченицу у ASCII формату "The quick brown fox jumps over the lazy dog" пустићемо кроз MD4 алгоритам и добићемо 128-битни излаз у хексадецималном облику

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

Чак и најмања промена тип једног слова у реченици имаће као резултат промену хексадецималног излаза. На пример променићемо d у c:

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

Излаз МД4 функције у случају празног стринга биће:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0