Tekst źródłowy strony MD5

{{Algorytm krypto infobox
 |nazwa          = MD5
 |inne nazwy     = 
 |grafika        = MD5 algorithm.svg
 |opis grafiki   = 
 |rodzaj         = [[funkcja skrótu|kryptograficzna funkcja skrótu]]
 |data           = [[1992]]
 |autorzy        = [[Ron Rivest]]
 |blok wejściowy = 
 |blok wyjściowy = 
 |klucz          = 
 |rundy          = 4
 |data złamania  = [[2004]]<ref>{{cytuj pismo |autor = Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu |tytuł = Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |url = http://eprint.iacr.org/2004/199 |czasopismo = Cryptology ePrint Archive Report 2004/199 |data = 16 Aug 2004 |data dostępu = 2010-06-25}}</ref>
 |złamany przez  = Xiaoyun Wang, Dengguo Fen, Xuejia Lai i Hongbo Yu
 |ataki          = 
}}
'''MD5''' (z {{ang.|Message-Digest algorithm 5}}) – [[algorytm]] [[Kryptologia|kryptograficzny]], opracowany przez [[Ron Rivest|Rona Rivesta]] (współtwórcę [[RSA (kryptografia)|RSA]]) w [[1991]] roku, będący popularną kryptograficzną [[funkcja skrótu|funkcją skrótu]], która z [[ciąg (matematyka)|ciągu]] danych o dowolnej długości generuje 128-[[bit]]owy skrót.

W [[2004]] znaleziono sposób na generowanie [[kolizja (kryptografia)|kolizji]] MD5, co obniża jego bezpieczeństwo w niektórych zastosowaniach (np. podpisywaniu plików).

Z powodu znanych [[kryptoanaliza|ataków kryptoanalitycznych]] funkcja MD5 zdecydowanie nie powinna być używana w zastosowaniach wymagających odporności na [[kolizja (kryptografia)|kolizje]], na przykład w [[podpis cyfrowy|podpisie cyfrowym]]. W innych, takich jak [[HMAC]], nadal może zapewniać satysfakcjonujący poziom bezpieczeństwa, choć stosowanie jej w nowych rozwiązaniach nie jest zalecane{{odn|RFC 6151}}.

== Przykłady ==
Skrót obliczony dla krótkiego tekstu:
<pre>MD5("Ala ma kota") = 91162629d258a876ee994e9233b2ad87</pre>

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

<pre>MD5("Ala ma koty") = 6a645004f620c691731b5a292c25d37f</pre>

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 [[Szesnastkowy system liczbowy|szesnastkowym]].

<pre>Wynik MD5 dla archiwum "linux-2.6.10.tar.bz2" o wielkości 35 MB: cffcd2919d9c8ef793ce1ac07a440eda</pre>

== Historia ==
MD5 jest jednym z serii algorytmów zaprojektowanych przez profesora [[Ron Rivest|Rona Rivesta]] z [[Massachusetts Institute of Technology|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ę [[kolizja (kryptografia)|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|RIPEMD-160]].

W marcu [[2004]] powstał [[Obliczenia rozproszone|rozproszony projekt]] nazywany {{link-interwiki|MD5CRK|tekst=MD5CRK (ang.)|Q=Q6715114}}. 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<ref>[http://cryptography.hyperlink.cz/index.html Vlastimil Klima].</ref> opublikował algorytm<ref>[http://cryptography.hyperlink.cz/MD5_collisions.html Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute].</ref>, który potrafił znaleźć kolizję w ciągu minuty, używając metody nazwanej {{J|en|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 [[Certyfikat klucza publicznego|certyfikatu]] [[Transport Layer Security|SSL]] w taki sposób, że zostanie on zaakceptowany przez wszystkie popularne [[Przeglądarka internetowa|przeglądarki internetowe]]. Do podrobienia certyfikatu wystarczyła [[moc obliczeniowa]] 200 [[Konsola gier wideo|konsol do gier]] [[PlayStation 3]]<ref>[http://www.win.tue.nl/hashclash/rogue-ca/ MD5 considered harmful today].</ref>.

Od lat 90. MD5 nie jest uważany za bezpieczny do większości zastosowań i w jego miejsce zaleca się stosowanie algorytmów z rodziny [[SHA-2]]<ref>{{Cytuj stronę |url=http://blog.securitystandard.pl/news/342130.html |tytuł=Aktualny poziom bezpieczeństwa funkcji skrótu |data=20 marca 2009 |opublikowany=Security Standard |archiwum=https://web.archive.org/web/20130528140757/http://blog.securitystandard.pl/news/342130.html |zarchiwizowano=2013-05-28 |data dostępu=2009-04-14 }}</ref> lub [[SHA-3]].

== Algorytm ==
[[Plik:MD5 algorithm.svg|thumb|250px|Schemat algorytmu MD5]]
Algorytm MD5 jest następujący:
# Doklejenie do wiadomości wejściowej bitu o wartości 1
# Doklejenie takiej ilości zer, by ciąg składał się z 512-bitowych bloków i ostatniego niepełnego – 448-bitowego
# Doklejenie 64-bitowego (zaczynając od [[Najmniej znaczący bit|najmniej znaczącego bitu]]) licznika oznaczającego rozmiar wiadomości; w ten sposób otrzymywana wiadomość złożona jest z 512-bitowych fragmentów
# Ustawienie stanu początkowego na 0123456789abcdeffedcba9876543210
# Uruchomienie na każdym bloku funkcji zmieniającej stan (istnieje przynajmniej jeden blok nawet dla pustego wejścia)
# Zwrócenie stanu po przetworzeniu ostatniego bloku 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 <code>F(x,y,z) = (x and y) or (neg x and z)</code>
: <math>F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})</math>
: (jeśli <math>x</math> to <math>y,</math> w przeciwnym wypadku <math>z</math>)
* W krokach 17 do 32 (cykl 2) funkcja <code>G(x,y,z) = (x and z) or (y and neg z)</code>
: <math>G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z})</math>
: (jeśli <math>z</math> to <math>x,</math> w przeciwnym wypadku <math>y</math>)
* W krokach 33 do 48 (cykl 3) funkcja <code>H(x,y,z) = (x xor y xor z)</code>
: <math>H(X,Y,Z) = X \oplus Y \oplus Z</math>
: (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 <code>I(x,y,z) = (y xor (x or neg z))</code>
: <math>I(X,Y,Z) = Y \oplus (X \vee \neg{Z})</math>
: (jeżeli (<math>z=1</math> i <math>x=0</math>) wtedy {{Mvar|y}}, w przeciwnym wypadku nie {{Mvar|y}})

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

Podobną budowę mają funkcje skrótu [[MD4]], [[SHA0]] i [[SHA-1]] – 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 [[kolizja (kryptografia)|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.

== Zobacz też ==
* [[md5sum]]
* [[SHA-1]]
* [[tęczowe tablice]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{RFC|6151}}
* [http://md5online.org/md5-encrypt.html Hasher MD5]
* [http://md5online.org/md5-decrypt.html Narzędzie do łamania MD5]
* [http://noweenergie.org/index.php?0/Article/63 MD5checker] - Narzędzie do sprawdzania integralności pliku na podstawie sumy kontrolnej MD5 w systemie [[Debian|Linux Debian]]

{{Kontrola autorytatywna}}

[[Kategoria:Funkcje skrótu]]