河北省新闻出版广电局“双随机”抽查事项清单
Message-Digest algorithm je v kryptografii rodina ha?ovacích funkcí, která z libovolného vstupu dat vytvá?í vystup fixní délky, ktery je ozna?ován jako hash (?esky někdy psán i jako ha?), otisk, miniatura a podobně (anglicky fingerprint). Jeho hlavní vlastností je, ?e malá změna na vstupu vede k velké změně na vystupu, tj. k vytvo?ení zásadně odli?ného otisku.
MD5
[editovat | editovat zdroj]Algoritmus MD5 se prosadil do mnoha aplikací (nap?. pro kontrolu integrity soubor? nebo ukládání hesel). MD5 je popsán v internetovém standardu RFC 1321 a vytvá?í otisk o velikosti 128 bit?. Byl vytvo?en v roce 1991 Ronaldem Rivestem, aby nahradil d?ívěj?í ha?ovací funkci MD4.
Historie a de?ifrování
[editovat | editovat zdroj]MD5 je jednou ze série kryptografickych ha?ovacích funkcí, které navrhl profesor Ronald L. Rivest pracující v institutu MIT (Rivest, 1994). Kdy? analytická práce ukázala, ?e p?edchozí verze MD4 není pravděpodobně ji? dostate?ně bezpe?ná, byl v roce 1991 naprogramován novy algoritmus MD5 (slabé stránky byly v MD4 opravdu později nalezeny Hansem Dobbertinem).
V roce 1993, Den Boer a Bosselaers p?inesli brzky, a?koli limitovany vysledek hledání "pseudo-kolize" v MD5 kompresní funkci. To znamená, ?e nalezli dva r?zné inicializa?ní vektory, které produkují stejny vysledek.
Dobbertin v roce 1996 oznámil kolizi kompresní funkce MD5 (Dobbertin, 1996). Zatímco to nebyl útok na kompletní MD5 hash funkci, bylo to dost podstatné pro kryptografy, aby doporu?ili p?echod na náhradu, nap?íklad SHA-1 nebo RIPEMD-160.
Velikost hashe (128 bit?) je dost malá na to, aby bylo mo?né uva?ovat o pou?ití narozeninového útoku. Distribuovany projekt MD5CRK byl zahájen v b?eznu 2004 s cílem demonstrovat, ?e MD5 je prakticky nebezpe?ny tím, ?e najde kolizi s pou?itím narozeninového útoku.
MD5CRK skon?ilo krátce po 17. srpnu 2004, kdy? Xiaoyun Wang, Dengguo Feng, Xuejia Lai a Hongbo Yu oznámili kolize pro úplny MD5. Podali zprávu, ?e jejich analyticky útok trval pouze jednu hodinu na IBM p690 klastru.
Arjen Lenstra, Xiaoyun Wang, a Benne de Weger dne 1. b?ezna 2005 prokázali vystavbu dvou X.509 certifikát? s rozdílnymi ve?ejnymi klí?i a stejnou MD5 hash funkci. Konstrukce obsahuje soukromé klí?e pro oba ve?ejné klí?e. O několik dní později, Vlastimil Klíma popsal vylep?eny algoritmus, schopny provádět MD5 kolize během několika hodin na jediném notebooku. Dne 18. b?ezna 2006, Klíma publikoval algoritmus, ktery m??e najít kolizi během jedné minuty na jednom notebooku, tuto metodu pojmenoval tunelování.
V roce 2009 United States Cyber Command pou?ilo MD5 hash ve svém svého oficiálním znaku (na vnit?ním krou?ku).
24. prosince 2010, Tao Xie a Dengguo Feng oznámil první publikovany blok MD5 kolize (dvě 64bajtové zprávy se stejnou MD5 hash byly dány do little endian zápisu). Objevy p?edchozích kolizí spoléhaly na multi-blokové útoky. Z "bezpe?nostních d?vod?", Xie a Feng nezve?ejnili nové metody útoku. Kryptografická komunita u?inila nabídku 10.000$ prvnímu, kdo objeví jinou 64bajtovu kolizi p?ed 1. lednem 2013. V roce 2011 RFC schválila aktualizaci bezpe?nostních otázek ohledně RFC 1321 (MD5) a RFC 2104 (HMAC-MD5).
Bezpe?nost
[editovat | editovat zdroj]V roce 1996 byla objevena vada v návrhu MD5, a p?esto?e nebyla zásadní, kryptologové za?ali raději doporu?ovat jiné algoritmy, jako je nap?íklad SHA (i kdy? ani ten ji? dnes není pova?ován za bezchybny). V roce 2004 byly nalezeny daleko vět?í chyby a pou?ití MD5 se zásadně nedoporu?uje.
P?íklad kontrolního sou?tu MD5
[editovat | editovat zdroj]Otisk 43bytového znakového ?etězce (vyjád?eny v hexadecimálním zápisu):
MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6
Sta?í malá změna vstupního ?etězce, aby byl otisk úplně odli?ny (nap?. změňme d na c):
MD5("The quick brown fox jumps over the lazy cog")
= 1055d3e698d289f2af8663725127bd4b
MD5 sou?et prázdného ?etězce je d41d8cd98f00b204e9800998ecf8427e.
Zvy?ení bezpe?nosti
[editovat | editovat zdroj]MD5 se d?íve ?asto pou?ívalo pro ukládání hesel. P?idáním soli k heslu se ztě?ují útoky na získání hesla a ú?innost slovníkovych útok? s vyu?itím p?edpo?ítanych tabulek (anglicky rainbow table attack). Tento postup lze pou?ít i pro jakékoli kryptografické ha?ovací funkce, které lze dop?edu "p?edpo?ítat", jejich vysledny ha? ulo?it, a pak rychleji vyhledat v databáze srovnáváním s ha?em, na ktery se úto?í.
hash = MD5 (heslo . sul)
Pro jisté zvy?ení bezpe?nosti je mo?né kombinovat nap?íklad heslo a u?ivatelské jméno, v takovém p?ípadě pokud dva u?ivatelé pou?ijí toto?né heslo, otisk (ha?) jejich hesel bude zásadně odli?ny, proto?e jejich u?ivatelská jména se ur?itě budou li?it. Dal?í mo?ností ?áste?ného zvy?ení bezpe?nosti je pou?ití více ha?ovacích algoritm? najednou, nap?íklad kombinace MD5 a SHA. Postup zajistí vy??í odolnost chráněné informace v p?ípadě, ?e bude p?i jedné z funkcí nalezena kolize. Nap?íklad:
SHA1(MD5("login").MD5("heslo"))
Pou?ití v praxi
[editovat | editovat zdroj]MD5 se pou?ívá v celém softwarovém světě, aby poskytovala jistotu, ?e p?ená?eny soubor dorazí beze změny. Nap?íklad souborové servery ?asto nabízejí p?edem spo?ítanou hodnotu MD5 (známé jako md5sum), kterou je u?ivatel schopny porovnat s opravdu sta?enymi daty. Unixové opera?ní systémy obsahují aplikace pro vypo?et MD5 sumy v jejich distribu?ních balí?cích, zatímco u?ivatelé Windows jsou nuceni pou?ít aplikace t?etích stran.
Av?ak nyní, kdy? je celkem jednoduché generovat MD5 kolize je mo?né vytvo?it dva soubory se stejnym otiskem, ?eho? lze vyu?ít v r?znych útocích. V některych p?ípadech také nelze vě?it kontrolním sou?t?m (nap?íklad pokud je kontrolní sou?et získán p?es stejny kanál, jako stahovany soubor). V tomto p?ípadě MD5 nabízí pouze kontrolu chyb: MD5 bude rozpoznávat p?eru?ené, nebo nedokon?ené stahování, které je pravděpodobněj?í během stahování velkych soubor?.
MD5 se také ?asto pou?ívá pro ukládání hesel. MD5 a dal?í hashovací funkce se ?asto pou?ívají v oblasti elektronickych objev?, aby poskytovaly jedine?ny identifikátor pro ka?dy dokument, ktery se mění během právního procesu objevování. Tato metoda m??e byt pou?ita, aby nahradila Bates stamp ?íselny systém, ktery se po desetiletí vyu?ívá p?i vyměně papírovych dokument?.