MD4

Z Wikipedii

MD4 to 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 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 w rundach 2 i 3, ani też nie występuje dodawanie wartości jednego rejestru do drugiego

Używana jest inna funkcja w krokach 17-32, G(x,y,z) = (x and y) or (x and z) or (y and z)

[edytuj] 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);

[edytuj] Linki zewnętrzne

• Generator hashy MD2, MD4, MD5