MHASH_MD5

Md5 je jednosměrná hashovací funkce, kteoru vyvinul Ronald Rivest z MIT (Massachusetts Institute of Technology) v roce 1991. Algoritmus hashovací funkce MD5 byl vyvinut, aby nahradil starší funkci MD4. Postupně bylo v této funkci nalezeno několik vad, ale funkce je stále používána. V roce 2004 byli nalezeny další závažnější bezpečnostní chyby, nicméně i přesto všechno je tato hashovací funkce stále velmi používaná a plnohodnotně se vyrovná například funkci SHA-1.

Md5 je jednosměrná hashovací funkce, kteoru vyvinul Ronald Rivest z MIT (Massachusetts Institute of Technology) v roce 1991. Algoritmus hashovací funkce MD5 byl vyvinut, aby nahradil starší funkci MD4. Postupně bylo v této funkci nalezeno několik vad, ale funkce je stále používána. V roce 2004 byli nalezeny další závažnější bezpečnostní chyby, nicméně i přesto všechno je tato hashovací funkce stále velmi používaná a plnohodnotně se vyrovná například funkci SHA-1.

Název MD5 vznikl z anglického Message-Digest algorithm 5 a v současné době je popsána v internetovém standartu RFC 1321. Hlavní využití této funkce spočívá v malých aplikacích, například pro ověřování hesel v databázi.

Při hashování je generována, na základě vstupních dat, Hash Value, která je většinou kratší než vstupní text, a je tvořena takovým způsobem, že je velmi nepravděpodobné aby některý další text generoval stejnou Hash Value. Pokud by i přesto měli dva různé vstupní řetězce stejnou Hash Value, jednalo by se o kolizi. Jestliže tedy pomocí této funkce vytvoříte hash pro dva podobné řetězce, musí být otisk plně odlišný.

Všimněte si, že řetězce na vstupu jsou téměř identické. Na výstupu musíme ale dostat dva maximálně odlišné řetězce:

Jak MD5 pracuje

MD5 vždy pracuje s daty, která mají celkovou délku v bitech násobku 512-ti. Pokud není velikost násobkem tohoto čísla, musí se doplnit na požadovanou velikost.

Doplňuje se následně:

– jeden byt hodnoty 1 je přidán tak, že délka zprávy je o 64 bitů menší než je konečný násobek 512

– chybějících 64 bytů má potom své uplatnění jako uchování délky zprávy pře doplněním, aby nebyla toto informace stracena.

Doplňování se provádí vždy, tedy i v případě, že je velikost násobkem 512-ti.

Když je vstupní řetězec upraven, nic nám nebrání zjistit Value hodnotu:

Tato hodnota závisí na opakované modifikaci 128-bitové hodnoty popisující stav.

Pro zpracování každého 128-bitového stavu je tento stav rozdělen na 4 bloky po 32 bitech, označených A, B, C, D a na začátku se každému z nich nastaví výchozí hodnoty.

Každý z techto 4 bloků je potom zpracován nezávisle na ostatních a různě modifikován, přičemž modifikace probíhají ve 4 stupních, které se nazývají kola. Jednotlivá kola se skládají z 16 operací, což je celkem (4*16) 64 operací pro každý blok dat.512-bitový blok dat je rozdělen na 16 datových slov. (každé obsahuje 32 bitů) a uvnitř každého kola je jedna z následujících operací:

Každá z těchto funkcí má jako vstupní parametr tři 32 bitové slova a návratová hodnota je pak jedna 32 bitová hodnota.

Tyto operace probíhají v každém kole a bloky A, B, C, D jsou postupně modifikovány. V závislosti na počátečním vstupu jsou využita k vypočtení koncové Value Hodnoty. Výsledek každého stupně je použit pro výpočet v dalším stupni.

Jak jsme si již řekli, v ideální hashovací funkci nesmí docházet ke kolizím. Bohužel ve funkci MD5 ke kolizím dochází.

V roce 2004 byl vytvořen algoritmus čínskými vědci, který hledal kolize.

Algoritmus sice zveřejněn nebyl, ale byl zveřejněn kolizní řetězec:

Po pozorném prozkoumání obou řetězců zjistíte že se liší, výsledný řetězec je však v obou případech:

Celý algoritmus zřejmě závisí na inicializačním vektoru a pro výpočet na notebooku IBM P690 trval výpočet asi jednu hodinu.

V této době laboratoře RSA doporučili přejít na algoritmus SHA-1.

Nicméně je hashovací algoritmus MD5 stále hojně užíván. Sice byly nalezeny kolize, ale stále patří k velmi bezpečným řešením.

Louskání hesla

MD5 je tedy hashovací funkce, která se většinou používá pro ukládání hesel v databázi.

Pokud by jste v praxi získali takové heslo, zakódované jednou funkcí MD5, a pokud není složeno z různých alfanumerických znaků, ale pouze z malých písmen a číslic, a víte o něm, že není dlouhé, není pro vás zase takový problém jej prolomit.

Můžete použít například program Cain&Abel (programů je celá spousta) a prolomení takového hesla o délce 5 znaků je potom otázka opravdu na několik minut i pro Brute-Force Attack. Na příkladu si ukážeme slovo „heslo”jehož hash je „955db0b81ef1989b4a4dfeae8061a9a6”. Prolomení tohoto hesla trvá opravdu jenom několik málo okamžiků i na podprůměrném počítači:

Nastavili jsme testování hesel, o délce od 4 do 6 znaků. Vidíte že počet kombinací při použití znaků „abcdefghijklmnopqrstuvwxyz1234567890” je otázka 13 minut, přičemž počitač tetuje rychlostí 2 748 622 hesel za sekundu.

Takový program není aní složité naprogramovat. Stačí vytvářet řetězce o požadované délce, které budou složeny z předem zadaných znaků. Jediné co potřebujete je knihovna pro kódování MD5. Program je potom v například v jazyce C otázkou několika řádků a kvalitního algoritmu.

Bohužel u hesel delších než nějakých 8 znaků, nebo heslo složené z malých a velkých znaků abecedy by se doba pro prolomení zvýšila na několik dní až desítky nebo stovky let. To je pro nás nepřijatelné. Ale nezoufejte. Můžete vyzkoušet cracknout heslo pomocí „Dictionary attack”

Jedná se o druh útoku, při kterém využíváte určitý předem vytvořený seznam hesel. Tento seznam postupně procházíte a každé slovo zakódujte pomocí MD5.

Pro útok zase můžete použít zase program Cain&Abel, nebo si program opět vytvořit. Stačí číst ze vstupního souboru jednotlivé slova a testovat jejich hash s výsledným hashem, který se pokoušíme rozlousknout.

Podobny skript by jsme si mohli zpracovat i v PHP. Budeme mít tabulku se slovy a jejich md5 hash. Při hledání budeme prohledávat tabulku a hledat stejný hash slova.

Nejprve si tedy musíme vytvořit tabulku, ve které budou uloženy všechna slova. Dále formulář pro vkládání a hledání slov.

Celý skript může vypadat takto:

V příštím článku se podíváme na MHASH_SHA1.