Message-Digest algorithm

Message-Digest algorithm je v kryptografii rodina hašovacích funkcí, která z libovolného vstupu dat vytváří výstup fixní délky, jenž je označován jako hash (česky někdy psán i jako haš), otisk, miniatura apod. (anglicky fingerprint). 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 kryptoanalýza

MD5 je kryptografická hašovací funkce navržená Ronaldem L. Rivestem z Massachusettského technologického institutu (MIT) v roce 1991 (Rivest, 1994). Vznikla jako nástupce funkce MD4 poté, co se objevily pochybnosti o její bezpečnosti; její slabiny byly později potvrzeny Hansem Dobbertinem.

V roce 1993 publikovali Bert Den Boer a Antoon Bosselaers dílčí výsledek týkající se tzv. "pseudo-kolize" v kompresní funkci MD5, kdy nalezli dva odlišné inicializační vektory produkující stejný výstup. V roce 1996 oznámil Hans Dobbertin kolizi kompresní funkce MD5 (Dobbertin, 1996). Ačkoli se nejednalo o přímý útok na celou hašovací funkci, vedlo to k doporučení kryptografické komunity přejít na jiné algoritmy, například SHA-1 nebo RIPEMD-160.

Délka výstupu MD5 činí 128 bitů, což je z hlediska moderních požadavků relativně málo na to, aby bylo možné uvažovat o použití tzv. narozeninového útoku. V březnu 2004 byl zahájen Distribuovaný projekt MD5CRK s cílem demonstrovat praktickou zranitelnost algoritmu nalezením kolize pomocí narozeninového útoku.

Dne 17. srpna 2004 oznámili Xiaoyun Wang, Dengguo Feng, Xuejia Lai a Hongbo Yu nalezení kolizí pro plnou hašovací funkci MD5. Uvedli, že jejich kryptoanalytický útok trval pouze jednu hodinu na klastru IBM p690.

Dne 1. března 2005 prokázali Arjen Lenstra, Xiaoyun Wang, a Benne de Weger možnost vytvoření dvou certifikátů X.509 s rozdílnými veřejnými klíči, avšak se stejnou hodnotou MD5. Konstrukce zahrnovala odpovídající soukromé klíče k oběma veřejným klíčům. Krátce poté publikoval Vlastimil Klíma zdokonalený algoritmus umožňující nalezení kolize během několika hodin na běžném notebooku. Dne 18. března 2006 zveřejnil další postup, označovaný jako "tunelování", který umožňoval nalezení kolize během jedné minuty na jediném přenosném počítači.

V roce 2009 použilo United States Cyber Command hašovací funkci MD5 ve svém svého oficiálním znaku (na vnitřním kruhu).

Dne 24. prosince 2010 oznámili Tao Xie a Dengguo Feng první publikovanou kolizi v rámci jednoho 64bajtového bloku (dvě různé 64bajtové zprávy se shodnou hodnotou MD5, uvedené v little-endian zápisu). Předchozí útoky využívaly vícero bloků. Autoři nezveřejnili detaily nové metody z bezpečnostních důvodů. Kryptografická komunita vypsala odměnu 10.000 $ pro prvního, kdo nalezne jinou 64bajtovu kolizi před 1. lednem 2013.

V roce 2011 byly v rámci procesu RFC zveřejněny aktualizace bezpečnostních doporučení týkajících se RFC 1321 (MD5) a RFC 2104 (HMAC-MD5), které upozorňují na omezenou bezpečnost těchto mechanismů.

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 použití MD5 se zásadně nedoporučuje.

Příklad kontrolního součtu MD5

Otisk 43bytové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

MD5 součet prázdného řetězce je d41d8cd98f00b204e9800998ecf8427e.

Zvýšení bezpečnosti

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í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ávání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á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

MD5 se používá v celém softwarovém světě, aby poskytovala jistotu, že přenášený 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 schopný porovnat s opravdu staženými daty. Unixové operační systémy obsahují aplikace pro výpoč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 stejným otiskem, čehož lze využít v různých útocích. V některých případech také nelze věřit kontrolním součtům (například pokud je kontrolní součet získán přes stejný kanál, jako stahovaný 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í velkých souborů.

MD5 se také často používá pro ukládání hesel. MD5 a další hashovací funkce se často používají v oblasti elektronických objevů, aby poskytovaly jedinečný identifikátor pro každý dokument, který se mění během právního procesu objevování. Tato metoda může být použita, aby nahradila Bates stamp číselný systém, který se po desetiletí využívá při výměně papírových dokumentů.

Související články

Externí odkazy