MD4
Rodzaj algorytmu | |
---|---|
Data stworzenia | |
Autorzy | |
Liczba rund | 3 |
Data złamania | |
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
- Ustala się pewien 128-bitowy stan początkowy (cztery 32-bitowe rejestry)
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)
- 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)
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.
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].
Linki zewnętrzne
- R. Rivest , The MD4 Message-Digest Algorithm, RFC 1320, IETF, kwiecień 1992, DOI: 10.17487/RFC1320, ISSN 2070-1721, OCLC 943595667 (ang.).