PROFILPELAJAR.COM

MD4
Rodzaj algorytmu	kryptograficzna funkcja skrótu
Data stworzenia	1990
Autorzy	Ron Rivest
Liczba rund	3
Data złamania	1995
Złamany przez	Hans Dobbertin

MD4 – funkcja skrótu zaprojektowana do zastosowań kryptograficznych. Została jednak złamana (kolizje można generować na typowym PC-cie w czasie rzędu sekund) i jest obecnie bezużyteczna do celów wymagających bezpieczeństwa.

MD4 została więc zastąpiona do praktycznie wszystkich zastosowań przez MD5 oraz inne funkcje skrótu.

MD4 a MD5

MD4 i MD5 mają bardzo podobną budowę:

Wiadomość jest uzupełniana do wielokrotności 512 bitów (szczegółowy algorytm w artykule MD5)

Ustala się pewien 128-bitowy stan początkowy (cztery 32-bitowe rejestry)

Dla każdego 512-bitowego bloku danych uruchamiana jest transformacja, która na podstawie aktualnego stanu oraz tego bloku wylicza nowy stan.

Po przerobieniu wszystkich bloków końcowy stan jest zwracany jako wynik funkcji

Najważniejsze różnice wobec MD5:

Transformacja ma tylko 3 rundy (48 kroków), zamiast 4 (64 kroków) jak MD5

Do wyniku każdego kroku nie jest dodawana zależna od numeru kroku stała, jedynie stała zależna od numeru rundy (tylko w rundach 2 i 3)

Nie występuje też dodawanie wartości jednego rejestru do drugiego

W krokach 17-32 używana jest inna funkcja: G(x,y,z) = (x and y) or (x and z) or (y and z)

Kod źródłowy

Kod na podstawie RFC 1320 ↓ (RSA Data Security, Inc.). Algorytm paddingu jest zawarty w artykule MD5.

W poniższym kodzie a, b, c i d oznaczają rejestry stanu.

Inicjalizacja:

  a = 0x67452301;
  b = 0xefcdab89;
  c = 0x98badcfe;
  d = 0x10325476;

Pomocnicze makra:

#define F(x, y, z) (x&y | ~x&z)
#define G(x, y, z) (x&y | x&z | y&z)
#define H(x, y, z) (x^y^z)

#define FF(v, w, x, y, z, s) { \
    v += F(w, x, y) + z; \
    v = ROTATE_LEFT(v, s); \
  }
#define GG(v, w, x, y, z, s) { \
    v += G(w, x, y) + z + 0x5a827999; \
    v = ROTATE_LEFT(v, s); \
  }
#define HH(v, w, x, y, z, s) { \
    v += H(w, x, y) + z + 0x6ed9eba1; \
    v = ROTATE_LEFT(v, s); \
  }

ROTATE_LEFT(x, s) oznacza przesunięcie cykliczne 32-bitowej liczby o s bitów w lewo.

Stałe przesunięć:

#define S11 3
#define S12 7
#define S13 11
#define S14 19
#define S21 3
#define S22 5
#define S23 9
#define S24 13
#define S31 3
#define S32 9
#define S33 11
#define S34 15

Transformacja bloku (x[i] to kolejne 32-bitowe fragmenty aktualnego bloku, w porządku little endian):

  aa = a;
  bb = b;
  cc = c;
  dd = d;

  /* Runda 1 */
  FF(a, b, c, d, x[ 0], S11); /* 1 */
  FF(d, a, b, c, x[ 1], S12); /* 2 */
  FF(c, d, a, b, x[ 2], S13); /* 3 */
  FF(b, c, d, a, x[ 3], S14); /* 4 */
  FF(a, b, c, d, x[ 4], S11); /* 5 */
  FF(d, a, b, c, x[ 5], S12); /* 6 */
  FF(c, d, a, b, x[ 6], S13); /* 7 */
  FF(b, c, d, a, x[ 7], S14); /* 8 */
  FF(a, b, c, d, x[ 8], S11); /* 9 */
  FF(d, a, b, c, x[ 9], S12); /* 10 */
  FF(c, d, a, b, x[10], S13); /* 11 */
  FF(b, c, d, a, x[11], S14); /* 12 */
  FF(a, b, c, d, x[12], S11); /* 13 */
  FF(d, a, b, c, x[13], S12); /* 14 */
  FF(c, d, a, b, x[14], S13); /* 15 */
  FF(b, c, d, a, x[15], S14); /* 16 */

  /* Runda 2 */
  GG(a, b, c, d, x[ 0], S21); /* 17 */
  GG(d, a, b, c, x[ 4], S22); /* 18 */
  GG(c, d, a, b, x[ 8], S23); /* 19 */
  GG(b, c, d, a, x[12], S24); /* 20 */
  GG(a, b, c, d, x[ 1], S21); /* 21 */
  GG(d, a, b, c, x[ 5], S22); /* 22 */
  GG(c, d, a, b, x[ 9], S23); /* 23 */
  GG(b, c, d, a, x[13], S24); /* 24 */
  GG(a, b, c, d, x[ 2], S21); /* 25 */
  GG(d, a, b, c, x[ 6], S22); /* 26 */
  GG(c, d, a, b, x[10], S23); /* 27 */
  GG(b, c, d, a, x[14], S24); /* 28 */
  GG(a, b, c, d, x[ 3], S21); /* 29 */
  GG(d, a, b, c, x[ 7], S22); /* 30 */
  GG(c, d, a, b, x[11], S23); /* 31 */
  GG(b, c, d, a, x[15], S24); /* 32 */

  /* Runda 3 */
  HH(a, b, c, d, x[ 0], S31); /* 33 */
  HH(d, a, b, c, x[ 8], S32); /* 34 */
  HH(c, d, a, b, x[ 4], S33); /* 35 */
  HH(b, c, d, a, x[12], S34); /* 36 */
  HH(a, b, c, d, x[ 2], S31); /* 37 */
  HH(d, a, b, c, x[10], S32); /* 38 */
  HH(c, d, a, b, x[ 6], S33); /* 39 */
  HH(b, c, d, a, x[14], S34); /* 40 */
  HH(a, b, c, d, x[ 1], S31); /* 41 */
  HH(d, a, b, c, x[ 9], S32); /* 42 */
  HH(c, d, a, b, x[ 5], S33); /* 43 */
  HH(b, c, d, a, x[13], S34); /* 44 */
  HH(a, b, c, d, x[ 3], S31); /* 45 */
  HH(d, a, b, c, x[11], S32); /* 46 */
  HH(c, d, a, b, x[ 7], S33); /* 47 */
  HH(b, c, d, a, x[15], S34); /* 48 */

  a += aa;
  b += bb;
  c += cc;
  d += dd;

Wynik to wartości kolejnych rejestrów w porządku little endian:

  printf("%08X%08X%08X%08X", a, b, c, d);

Przypisy

↑ Hans Dobbertin. Cryptanalysis of MD4. „Journal of Cryptology”, 1995. [dostęp 2010-06-28].
↑ Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu. Cryptanalysis of the Hash Functions MD4 and RIPEMD. „Advances in Cryptology – EUROCRYPT'05”, 2005. [dostęp 2010-06-28].