Message-Digest algorithm
Message-Digest algorithm je rozšířená rodina hašovacích funkcí, která vytváří ze vstupních dat výstup (otisk) fixní délky. Otisk je též označován jako miniatura, kontrolní součet (v zásadě nesprávné označení), fingerprint, hash (česky někdy psán i jako haš). Jeho hlavní vlastností je, že malá změna na vstupu vede k velké změně na výstupu, tj. k vytvoření zásadně odlišného otisku.
MD5
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í
MD5 je jednou ze série Kryptografických hašovacích funkcí navržených profesorem Ronald L. Rivestem pracujícím ve společnosti 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 nový algoritmus MD5. (Slabé stránky byly opravdu později nalezeny v MD4 Hansem Dobbertinem.)
V roce 1993, Den Boer a Bosselaers přinesli brzký, ačkoli limitovaný výsledek hledání "pseudo-kolize" v MD5 kompresní funkci, to znamená, že dva různé inicializační vektory, které produkují stejný výběr.
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 cryptografery, aby doporučili přechod na náhradu, například SHA-1 nebo RIPEMD-160.
Velikost hashe -128 bitů, je dost malá na to uvažovat použití narozeninového útoku. MD5CRK byl distribuovaný projekt zahájen v březnu 2004 s cílem demonstrovat, že MD5 je prakticky nebezpečný 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 úplný MD5. Podaly zprávu, že jejich analytický útok trval pouze jednu hodinu na IBM p690 klastru.
Arjen Lenstra, Xiaoyun Wang, a Benne de Weger dne 1. března 2005 prokázali výstavbu dvou X.509 certifikátů s rozdílnými veřejnými 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šený algoritmus, schopný provádět MD5 kolize během několika hodin na jediném notebooku. Dne 18. března 2006, Klíma publikoval algoritmus, který může najít kolizi během jedné minuty na jednom notebooku, tuto metodu pojmenoval tunelování.
V roce 2009, Spojené státy Cyber comand použilo MD5 hash na jejich misi jako součást svého oficiálního znaku.
24. prosince 2010, Tao Xie a Dengguo Feng oznámil první publikovaný blok MD5 kolize (dvě 64-bytové zprávy se stejnou MD5 hash byly dány do little endian zápisu). Objevy předchozích kolizí spoléhali na multi-blokové útoky. Z "bezpečnostních důvodů", Xie a Feng nezveřejnili nové metody útoku. Kriptografická komunita učinila nabídku 10.000$ prvnímu, kdo objeví jinou 64-bytovu 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
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 bezchybný). V roce 2004 byly nalezeny daleko větší chyby a od použití MD5 v bezpečnostních aplikacích se upouští.
Příklad kontrolního součtu MD5
Otisk 43 bajtového znakového řetězce (vyjádřený 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šný (např. změňme d na c):
MD5("The quick brown fox jumps over the lazy cog")
= 1055d3e698d289f2af8663725127bd4b
Zvýšení bezpečnosti
MD5 se často používá pro ukládání hesel. Přidáním soli k heslu se ztěžují útoky na získání hesla a účinnost slovníkových útoků s využitím předpočítaných 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 výsledný haš uložit a pak rychleji vyhledat v databáze srovnávaním s hašem, na který se útočí.
hash = MD5 (heslo . sul)
Pro jisté zvýš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šný, protože jejich uživatelská jména se určitě budou lišit. Další možností částečného zvýšení bezpečnosti je použití více hašovacích algoritmů najednou, například kombinace MD5 a SHA. Postup zajistí vyšší odolnost chránené informace v případě, že bude při jedné z funkcií nalezena kolize. Například:
SHA1(MD5("login").MD5("heslo"))
Související články
Externí odkazy
- SSL certifikáty využívající MD5 kompromitovány
- Kolize MD5 do jedné minuty
- MD5 Vyhledání – otevřené texty k některým MD5 otiskům