MD5

	MD5
Rodzaj algorytmu	kryptograficzna funkcja skrótu
Data stworzenia	1992
Autorzy	Ron Rivest
Liczba rund	4
Data złamania	2004
Złamany przez	Xiaoyun Wang, Dengguo Fen, Xuejia Lai i Hongbo Yu

MD5 (z ang. Message-Digest algorithm 5 - Skrót wiadomości wersja 5) - algorytm z dziedziny kryptografii. Jest to popularna kryptograficzna funkcja skrótu, która z dowolnego ciągu danych generuje 128-bitowy skrót.

Algorytm został opracowany przez Ronalda Rivesta (współtwórcę RSA) w 1991. W 2004 znaleziono sposób na generowanie kolizji MD5, co obniża jego bezpieczeństwo w niektórych zastosowaniach (np. podpisywaniu plików).

[edytuj] Przykłady

Skrót obliczony dla krótkiego tekstu:

MD5("Ala ma kota") = 91162629d258a876ee994e9233b2ad87

Nawet niewielka zmiana w tekście (w tym przypadku zamiana a na y) powoduje (z bardzo dużym prawdopodobieństwem) powstanie zupełnie innego skrótu MD5

MD5("Ala ma koty") = 6a645004f620c691731b5a292c25d37f

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 35 MB: cffcd2919d9c8ef793ce1ac07a440eda

[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.

W 1996 Dobbertin zaprezentował analizę kolizji algorytmu MD5. Chociaż nie był to jeszcze pełny atak na funkcję skrótu to jednak wystarczył, aby specjaliści w dziedzinie kryptografii zaczęli stosować silniejsze odpowiedniki, takie jak SHA-1 lub RIPEMD-160.

W marcu 2004 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 wyznaczenie wiadomości różnej od zadanej, która ma taką samą wartość skrótu. 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.

W marcu 2005 Arjen Lenstra, Xiaoyun Wang i Benne de Weger zaprezentowali metodę umożliwiającą znalezienie kolizji dla algorytmu MD5 i przeprowadzenie ataku polegającego na wysłaniu dwóch różnych wiadomości chronionych tym samym podpisem cyfrowym. Kilka dni później Vlastimil Klima opublikował algorytm, który potrafił znaleźć kolizję w ciągu minuty, używając metody nazwanej tunneling.

Pod koniec 2008 roku niezależni kalifornijscy specjaliści ds. bezpieczeństwa, we współpracy z ekspertami z Centrum voor Wiskunde en Informatica, Technische Universiteit Eindhoven oraz Ecole Polytechnique Fédérale de Lausanne odkryli lukę w MD5 umożliwiającą podrobienie dowolnego certyfikatu SSL w taki sposób, że zostanie on zaakceptowany przez wszystkie popularne przeglądarki internetowe. Do podrobienia certyfikatu wystarczyła moc obliczeniowa 200 konsoli do gier PlayStation 3^[2].

Obecnie algorytm MD5 nie jest uważany za bezpieczny i w jego miejsce zaleca się stosowanie algorytmów z rodziny SHA-2^[3].

[edytuj] Algorytm

Schemat algorytmu MD5

Algorytm MD5 jest następujący:

Doklejamy do wiadomości wejściowej bit o wartości 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 obliczony skrót wiadomości

Funkcja zmiany stanu ma 4 cykle (64 kroki). Stan jest traktowany jako 4 liczby 32-bitowe. W każdym kroku do jednej 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 obracana (przesuwana cyklicznie z najstarszymi bitami wsuwanymi w najmłodsze pozycje) 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)

$F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{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)

$G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \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)

$H(X,Y,Z) = X \oplus Y \oplus 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))

$I(X,Y,Z) = Y \oplus (X \vee \neg{Z})$

(jeżeli ( $z=1$ i $x=0$ ) wtedy y, w przeciwnym wypadku nie y)

Aby otrzymać wartość stałej w i-tym kroku, należy wziąć 32 najstarsze bity z części ułamkowej wyrażenia $| \sin\ i |$ .

Podobną budowę mają funkcje skrótu 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).

Skróty 128-bitowe są zbyt krótkie, żeby zabezpieczyć przed generowaniem kolizji w oparciu o atak urodzinowy. Z tego powodu do większości zastosowań lepiej jest używać skrótów co najmniej 160-bitowych.

[edytuj] Kod źródłowy

Kod na podstawie RFC 1321 (RSA Data Security, Inc.).

W poniższym kodzie h0, h1, h2, h3 oznaczają tymczasowe wartości funkcji skrótu, natomiast a, b, c i d oznaczają rejestry w czasie przetwarzania pojedynczego bloku.

Inicjowanie:

  h0 = 0x67452301;
  h1 = 0xefcdab89;
  h2 = 0x98badcfe;
  h3 = 0x10325476;

Pomocnicze makra:

#define ROTATE_LEFT(x, s) ((x << s) | (x >> (32 - s)))
 
#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 + ac; \
 v = ROTATE_LEFT(v, s) + w; \
 }
#define GG(v, w, x, y, z, s, ac) { \
 v += G(w, x, y) + z + 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 liczby 32-bitowej 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):

  a = h0;
  b = h1;
  c = h2;
  d = h3;
 
  /* 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 */
 
  h0 += a;
  h1 += b;
  h2 += c;
  h3 += d;

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

  printf("%08X%08X%08X%08X", h0, h1, h2, h3);

Delphi/Pascal Implementation

Przypisy

↑ Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. „Cryptology ePrint Archive Report 2004/199”, 16 Aug 2004. [dostęp 2010-06-25].
↑ MD5 considered harmful today
↑ Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009.

[edytuj] Zobacz też

[0] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. „Cryptology ePrint Archive Report 2004/199”, 16 Aug 2004. [dostęp 2010-06-25].

[1] MD5 considered harmful today

[2] Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009.

[1]

[2]

[3]

MD5

Spis treści

[edytuj] Przykłady

[edytuj] Historia

[edytuj] Algorytm

[edytuj] Kod źródłowy

Przypisy

[edytuj] Zobacz też

Osobiste

Przestrzenie nazw

Warianty

Widok

Działania

Szukaj

Nawigacja

Dla czytelników

Dla wikipedystów

Narzędzia

Drukuj lub eksportuj

W innych językach

MD5

Rodzaj algorytmu	kryptograficzna funkcja skrótu
Data stworzenia	1992
Autorzy	Ron Rivest
Liczba rund	4
Data złamania	2004^[1]
Złamany przez	Xiaoyun Wang, Dengguo Fen, Xuejia Lai i Hongbo Yu