MD5
Z Wikipedii
MD5 - algorytm z dziedziny kryptografii. Jest to szeroko stosowany algorytm haszujący, który z dowolnego ciągu danych generuje 128-bitowy skrót (w literaturze fachowej stosuje się również termin funkcja skrótu do określenia tego typu algorytmów). Ideą algorytmu jest zapewnienie unikalności wyników w taki sposób, aby nie było możliwe uzyskanie tego samego skrótu dla dwóch różnych wiadomości leżących "blisko siebie" w zbiorze wiadomości (czyli niewielka zmiana w wiadomości /np. zmiana jednej litery w całym akapicie/ powoduje całkowitą zmianę skrótu). Ponieważ skrót MD5 jest 128-bitowy, oczywiste jest, że istnieje wiele wiadomości które w wyniku działania algorytmu dadzą taki sam skrót. Do wygenerowania takiego skrótu wykorzystywana jest odpowiednia funkcja haszująca. MD5 jest skrótem od angielskiej nazwy Message-Digest algorithm 5 (co oznacza Skrót Wiadomości wersja 5), został opracowany przez Ronalda Rivesta (współtwórcę RSA) w 1991 roku. W roku 2004 znaleziono sposób na generowanie kolizji MD5, co obniża jego bezpieczeństwo w niektórych zastosowaniach (np. podpisywaniu plików). Podobne słabości odnaleziono również w SHA-0 i osłabionej wersji SHA-1.
Spis treści |
[edytuj] Przykład
Dość powszechnym zastosowaniem MD5 jest generowanie skrótów wszelkiego rodzaju plików udostępnianych publicznie (najczęściej w Internecie), dzięki czemu osoba która pobrała dany plik z sieci może od razu zweryfikować (generując skrót MD5 na swojej kopii i porównując wyniki) czy jest to ten sam plik który został zamieszczony przez jego autora lub czy nie nastąpiły przekłamania podczas samego procesu pobierania danych. Publikowana w takim przypadku wartość ma postać 32. znakowej liczby w zapisie szesnastkowym.
Wynik MD5 dla archiwum "linux-2.6.10.tar.bz2" o wielkości 35MB: cffcd2919d9c8ef793ce1ac07a440eda Wynik MD5 dla ciągu znaków "to jest test": 802442288890b5fad24112095a762b02;
[edytuj] Historia
MD5 jest jednym z serii algorytmów zaprojektowanych przez profesora Ronalda Rivesta z MIT (Rivest, 1994). Poprzednikiem był algorytm MD4, który w wyniku analizy przeprowadzonej przez Hansa Dobbertina okazał się zbyt mało bezpieczny. Jego bezpiecznym następcą był MD5 opracowany w 1991 roku.
W 1996 roku Dobbertin zaprezentował analizę kolizji funkcji haszującej algorytmu MD5. Chociaż nie był to jeszcze pełny atak na funkcję haszującą to jednak wystarczył, aby specjaliści w dziedzinie kryptografii zaczęli stosować silniejsze odpowiedniki, takie jak SHA-1 lub RIPEMD-160.
W marcu 2004 roku powstał rozproszony projekt nazywany MD5CRK. Twórcą projektu był Jean-Luc Cooke i jego współpracownicy. Miał on na celu wykazanie, że możliwe jest takie spreparowanie drugiej wiadomości na podstawie wiadomości wyjściowej aby obie dały ten sam skrót. Oczywiście obie wiadomości muszą być różne od siebie. Do tego celu wykorzystano sieć Internet oraz dużą liczbę komputerów biorących udział w projekcie. Projekt wykazał, że dysponując bardzo dużą mocą obliczeniową możliwe jest podrabianie generowanych podpisów.
Dopiero prace badawcze chińskich naukowców Xiaoyun Wang, Dengguo Fen, Xuejia Lai i Hongbo Yu w pełni wykazały słabość algorytmu. 17 sierpnia 2004 opublikowali oni analityczny algorytm ataku, dzięki któremu do podrobienia podpisu wystarczyła godzina działania klastrowego komputera IBM P690.
[edytuj] Algorytm
Algorytm MD5 jest następujący:
- Doklejamy do haszowanego ciągu bit 1
- Doklejamy tyle zer ile trzeba żeby ciąg składał się z 512-bitowych bloków, i ostatniego niepełnego - 448-bitowego
- Doklejamy 64-bitowy (zaczynając od najmniej znaczącego bitu) licznik oznaczający rozmiar wiadomości. W ten sposób otrzymujemy wiadomość złożoną z 512-bitowych fragmentów.
- Ustawiamy stan początkowy na 0123456789abcdeffedcba9876543210
- Uruchamiamy na każdym bloku (jest przynajmniej jeden blok nawet dla pustego wejścia) funkcję zmieniającą stan
- Po przetworzeniu ostatniego bloku zwracamy stan jako wynik funkcji haszującej
Funkcja zmiany stanu ma 4 cykle (64 kroki). Stan jest traktowany jako 4 liczby 32-bitowe, i w każdym kroku do którejś z tych liczb dodawany jest jeden z 16 32-bitowych fragmentów bloku wejściowego, pewna stała zależna od numeru kroku oraz pewna prosta funkcja boolowska 3 pozostałych liczb. Następnie liczba ta jest przesuwana cyklicznie o liczbę bitów zależną od kroku, oraz jest dodawana do niej jedna z pozostałych liczb.
Funkcje te to:
- W krokach 1 do 16 (cykl 1) funkcja F(x,y,z) = (x and y) or (neg x and z) (jeśli x to y, w przeciwnym wypadku z)
- W krokach 17 do 32 (cykl 2) funkcja G(x,y,z) = (x and z) or (y and neg z) (jeśli z to x, w przeciwnym wypadku y)
- W krokach 33 do 48 (cykl 3) funkcja H(x,y,z) = (x xor y xor z) (suma argumentów modulo 2, lub innymi słowy: czy występuje nieparzysta liczba jedynek w argumentach)
- W krokach 49 do 64 (cykl 4) funkcja I(x,y,z) = (y xor (x or neg z)) (jeżeli (z=1 i x=0) wtedy y, w przeciwnym wypadku nie y)
Podobną budowę mają funkcje haszujące MD4, SHA0 i SHA1 – różnią się one jedynie postacią funkcji zmieniającej stan, oraz rozmiarem stanu (160 bitów, czyli 5 32-bitowych rejestrów w SHA i SHA1, wobec 128 w MD4 i MD5).
128 bitów jest uważane za zbyt mało, żeby zabezpieczyć przed kolizjami, dlatego do większości zastosowań lepiej jest używać funkcji zwracającej co najmniej 160 bitów.
[edytuj] Kod źródłowy
Kod na podstawie RFC 1321 (RSA Data Security, Inc.).
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&z | y&~z)
#define H(x, y, z) (x^y^z)
#define I(x, y, z) (y^(x|~z))
#define FF(v, w, x, y, z, s, ac) { \
v += F(w, x, y) + z + (UINT4)(ac); \
v = ROTATE_LEFT(v, s) + w; \
}
#define GG(v, w, x, y, z, s, ac) { \
v += G(w, x, y) + z + (UINT4)(ac); \
v = ROTATE_LEFT(v, s) + w; \
}
#define HH(v, w, x, y, z, s, ac) { \
v += H(w, x, y) + z + ac; \
v = ROTATE_LEFT(v, s) + w; \
}
#define II(v, w, x, y, z, s, ac) { \
v += I(w, x, y) + z + ac; \
v = ROTATE_LEFT(v, s) + w; \
}
ROTATE_LEFT(x, s) oznacza przesunięcie cykliczne 32-bitowej liczby o s bitów w lewo.
Stałe przesunięć:
#define S11 7 #define S12 12 #define S13 17 #define S14 22 #define S21 5 #define S22 9 #define S23 14 #define S24 20 #define S31 4 #define S32 11 #define S33 16 #define S34 23 #define S41 6 #define S42 10 #define S43 15 #define S44 21
Transformacja bloku (x[i] to kolejne 32-bitowe fragmenty aktualnego bloku, w porządku little endian):
aa = a; bb = b; cc = c; dd = d; /* Cykl 1 */ FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */ FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */ FF(c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */ FF(b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */ FF(a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */ FF(d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */ FF(c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */ FF(b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */ FF(a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */ FF(d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */ FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */ FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */ FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */ FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */ FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */ FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */ /* Cykl 2 */ GG(a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */ GG(d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */ GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */ GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */ GG(a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */ GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */ GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */ GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */ GG(a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */ GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */ GG(c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */ GG(b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */ GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */ GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */ GG(c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */ GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */ /* Cykl 3 */ HH(a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */ HH(d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */ HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */ HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */ HH(a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */ HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */ HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */ HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */ HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */ HH(d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */ HH(c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */ HH(b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */ HH(a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */ HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */ HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */ HH(b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */ /* Cykl 4 */ II(a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */ II(d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */ II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */ II(b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */ II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */ II(d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */ II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */ II(b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */ II(a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */ II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */ II(c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */ II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */ II(a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */ II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */ II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */ 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);
