VYSOKÉ U Č ENÍ TECHNICKÉ V BRN Ě
BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH
TECHNOLOGIÍ
ÚSTAV TELEKOMUNIKACÍ
FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF TELECOMMUNICATIONS
HASHOVACÍ FUNKCE A JEJICH VYUŽITÍ P Ř I AUTENTIZACI
HASH FUNCTION AND THEIR USAGE IN USER AUTHENTICATION
DIPLOMOVÁ PRÁCE
MASTER´S THESIS
AUTOR PRÁCE Bc. IGOR PILLER
AUTHOR
VEDOUCÍ PRÁCE Ing. JAN HAJNÝ
SUPERVISOR
BRNO 2009
Abstrakt
Práce se zabývá hashovacími funkcemi a jejich využitím při autentizaci. Obsahuje základní teorii o hashovacích funkcích a popis jejich základních konstrukčních prvků.
Konkrétně se práce zaměřuje na hashovací funkce LMHash, MD4, MD5 a funkce z rodiny SHA, které porovnává z hlediska bezpečnosti. Práce obecně popisuje nejpoužívanější útoky na hashovací funkce, poukazuje na slabiny současné konstrukce a nabízí výhled do budoucnosti hashovacích funkcí.
Dále práce nastiňuje problematiku autentizace a popisuje použití hashovacích funkcí v této oblasti.
V praktické části je realizován obecný autentizační rámec v programovacím jazyce C#.
Výsledkem realizace jsou klientská a serverová aplikace, na kterých byly úspěšně vyzkoušeny dvě vybrané autentizační metody. Při realizaci bylo dbáno na flexibilitu řešení a možné budoucí využití jiných metod autentizace.
Klíčová slova:
hash, hashovací funkce, autentizace, LMHash, MD4, MD5, SHA
Abstract
This thesis concerns with hash functions and their usage in authentication. It presents basics of hash functions theory and construction elements.
In particular the thesis focuses on LMHash, MD4, MD5 and SHA family hash functions, which are compared from the security point of view. The thesis describes in general the most frequently used hash function attacks, points out the weaknesses of current construction and mentions the future perspective of hash functions.
Furthermore the thesis outlines the area authentication and describes usage of hash functions in the area.
Practical part of the thesis contains an implements of a general authentication framework implemented in programming language C#. The result is client and server applications, in which two selected authentication methods were successfully tested. The result implementation is flexible with respect to the possible future use of other authentication methods.
Keywords:
Hash, hash function, authentication, LMHash, MD4, MD5, SHA
Citace práce
PILLER, I. Hashovací funkce a jejich využití při autentizaci. Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, 2009. 68s. Vedoucí diplomové práce Ing. Jan Hajný.
PROHLÁŠENÍ:
Prohlašuji, že svoji diplomovou práci na téma „hashovací funkce a jejich využití při autentizaci“ jsem vypracoval samostatně pod vedením vedoucího diplomové práce a s použitím odborné literatury a dalších informačních zdrojů, které jsou všechny citovány v práci a uvedeny v seznamu literatury na konci práce.
Jako autor uvedené diplomové práce dále prohlašuji, že v souvislosti s vytvořením této diplomové práce jsem neporušil autorská práva třetích osob, zejména jsem nezasáhl nedovoleným způsobem do cizích autorských práv osobnostních a jsem si plně vědom následků porušení ustanovení § 11 a následujících autorského zákona č. 121/2000 Sb., včetně možných trestněprávních důsledků vyplývajících z ustanovení § 152 trestního zákona č. 140/1961 Sb.
V Brně dne... ...
podpis autora
POD Ě KOVÁNÍ
Děkuji vedoucímu diplomové práce Ing. Janu Hajnému, za velmi užitečnou metodickou pomoc a cenné rady při zpracování diplomové práce.
V Brně dne ……… ………
(podpis autora)
Seznam zkratek
AES – Advanced Encryption Standard
ASCII – American Standard Code for Information Interchange DES – Data Encryption Standard
HDN – Hash Double Net
HMAC – Hash Message Authentication Code LANMAN – LAN Manager
LMHash – LAN Manager hash MD – Message-Digest
MDC – Modification detection codes
MIT – Massachusetts Institute of Technology
NIST – National Institute of Standards and Technology NTLM – NT LAN Manager
OS – Operační systém
PIN – Personal identification number POV – Point of verification
RIPEMD – RACE Integrity Primitives Evaluation Message Digest SHA – Secure Hash Algorithm
SNMAC – Special Nested Message Authentication Code XOR – Exkluzivní logický součet
OBSAH
1 ÚVOD...10
2 ZÁKLADNÍ KONSTRUKČNÍ PRVKY HASHOVACÍCH FUNKCÍ ...11
2.1 DEFINICE HASHOVACÍ FUNKCE...11
2.2 ROSTOUCÍ POŽADAVKY KLADENÉ NA HASHOVACÍ FUNKCE...11
2.3 KONSTRUKČNÍ PRVKY...13
2.4 POUŽITÍ HASHOVACÍCH FUNKCÍ...17
3 NÁSTROJE A METODY PRO ZLOMENÍ ...19
3.1 ÚTOKY METODOU HRUBÉ SÍLY...19
3.2 SLOVNÍKOVÝ ÚTOK A RAINBOW TABLES...19
3.3 KRYPTOANALÝZA...21
4 SOUČASNÉ HASHOVACÍ FUNKCE...22
4.1 LMHASH...22
4.2 MD4...23
4.3 MD5...25
4.3.1 Konstrukce MD5, bezpečnost...25
4.3.2 Tunelování...27
4.4 SHA-0 A SHA-1...27
4.5 RODINA SHA-2 ...29
5 BUDOUCNOST HASHOVACÍCH FUNKCÍ...31
5.1 PROBLÉMY KONSTRUKCE DNEŠNÍCH HASHOVACÍCH FUNKCÍ...31
5.1.1 Generické problémy iterativních hashovacích funkcí...31
5.1.2 R-násobná kolize s nižší složitostí...31
5.1.3 Kaskádovitá konstrukce...32
5.1.4 Nalezení druhého vzoru u dlouhých zpráv snadněji než se složitostí 2n.33 5.2 NIST, SOUTĚŽ SHA-3...33
5.3 HASHOVACÍ FUNKCE HDN TYPU SNMAC ...34
5.3.1 Nové kryptografické primitivum...35
5.3.2 Hashovací funkce nové generace SNMAC ...36
5.3.3 Hashovací funkce HDN ...36
6 HASHOVACÍ FUNKCE A AUTENTIZACE ...37
6.1 AUTENTIZACE...37
6.2 HASHOVACÍ FUNKCE A UKLÁDÁNÍ HESEL...37
6.2.1 Ukládání hesel v OS Windows ...38
6.2.2 Ukládání hesel v OS Linux ...39
6.3 AUTENTIZAČNÍ PROTOKOLY...39
6.3.1 Přímé ověření ...39
6.3.2 Nepřímé ověření...41
7 REALIZACE OBECNÉHO AUTENTIZAČNÍHO RÁMCE ...42
7.1 ROZBOR APLIKACE...42
7.1.1 Výběr programovacího jazyka ...42
7.1.2 Zadání, hlavní myšlenka realizace ...42
7.1.3 Schémata jednotlivých tříd, provázání tříd důležitých pro autentizaci...43
7.1.4 Logování, načítání dat z textového souboru...45
7.2 SERVER, UŽIVATELSKÉ ROZHRANÍ...47
7.3 CLIENT, UŽIVATELSKÉ ROZHRANÍ...48
7.4 TŘÍDA AUTHENTICATIONPROCEDURE...49
7.5 TŘÍDA SIMPLEPROCEDURE, OBYČEJNÁ METODA AUTENTIZACE...50
7.6 TŘÍDA ADVANCEDPROCEDURE...51
7.7 TŘÍDY HASHFUNCTION,IDENTITYFUNCTION,MD5,SERVER,CLIENT,MAINFORM.53 7.8 PŘIDÁNÍ AUTENTIZAČNÍ METODY A HASHOVACÍ FUNKCE...54
7.9 UKÁZKA KOMUNIKACE...59
8 ZÁVĚR ...61
POUŽITÁ LITERATURA...63
SEZNAM OBRÁZKŮ...66
OBSAH CD ...68
Úvod
Stránka 10 z 68
1 Úvod
Hashovací funkce jsou nedílnou součástí moderní kryptologie už po mnoho let. S rozvojem Internetu se jejich důležitost ještě mnohokrát znásobila a jejich využití je opravdu široké, používajíc různé vlastnosti těchto funkcí.
V posledních několika letech je vidět zvýšený zájem o studium těchto funkcí. Za největší zviditelnění můžeme považovat úspěšné útoky na hashovací funkce MD5, SHA-0, SHA-1.
Díky těmto útokům se o hashovací funkce začalo zajímat mnohem více lidí a panuje všeobecný názor, že tyto funkce nebyly dostatečně studovány, přestože jim přikládáme takovou důležitost. I neodborná veřejnost se pak na základě vysvětlujících populárních článků začala zajímat a povědomí o těchto funkcích tak začíná stoupat.
V první části této diplomové práce se podíváme co vlastně hashovací funkce je, jaké má vlastnosti, jaké chceme, aby měla vlastnosti, z čeho je složena a k čemu se používá.
V další části jsou uvedeny obecně některé možné útoky na tyto funkce.
Ve třetí části jsou rozebrány nejpoužívanější dnešní hashovací funkce, kterými jsou LMHash, MD4, MD5, SHA-0, SHA-1 a funkce z rodiny SHA-2. U funkce MD5 je pak krátce rozebrán nový způsob kryptoanalýzy hashovacích funkcí, tzv. „tunelování“, které se ukázalo být velice efektivním útokem.
Čtvrtá část se zabývá problémy dnešních hashovacích funkcí, popisuje dosud známé odhalené slabiny konstrukce dnešních iterativních hashovacích funkcí. V této části jsou ale také popsány návrhy budoucích hashovacích funkcí, které by tyto problémy mohly vyřešit.
V páté části jsou zmíněny souvislosti autentizace a použití hashovacích funkcí.
Nakonec poslední část obsahuje dokumentaci k přiloženému praktickému řešení obecného autentizačního rámce.
Základní konstrukční prvky hashovacích funkcí
Stránka 11 z 68
2 Základní konstruk č ní prvky hashovacích funkcí
2.1 Definice hashovací funkce
Jako hashovací se dříve označovaly takové funkce, které pro libovolně velký vstup přiřadily krátký hashový kód s pevně definovanou délkou. Dnes se termínem hashovací funkce označují kryptografické hashovací funkce, u nichž je navíc požadováno, aby byly jednosměrné a bezkolizní.
Hashovací funkce vychází hlavně z pojmu „jednosměrná funkce“. To je funkce, kterou lze snadno vyčíslit, ale je výpočetně nemožné z výsledku funkce odvodit její vstup. Tedy funkce f: X→Y, pro kterou je snadné z jakékoliv hodnoty x∈X vypočítat y=f(x), ale při znalosti y∈f(X) nelze najít její vzor x∈X tak, aby y=f(x), tedy vypočítat inverzní funkci je výpočetně nemožné v krátkém čase. Vzor přitom existuje, nebo je jich dokonce velmi mnoho. Kromě hashovací funkce je dalším příkladem jednosměrné funkce součin dvou velkých prvočísel, který získáme velmi snadno, kdežto zpětně jej faktorizovat je pro nás již výpočetně nemožné.
2.2 Rostoucí požadavky kladené na hashovací funkce
Mimo schopnosti přiřadit libovolně velkému vstupu hashový kód o pevně definované délce se během času začaly na hashovací funkce klást větší a větší požadavky. Nejdůležitější zde uvedu. (Pozn.: V definici se uvádí „libovolně velký vstup“, ve skutečnosti se však používá většinou vstup maximální délky D = 264–1bitů, abychom takové číslo mohli vyjádřit pomocí 64 bitů.)
Jednosměrnost
Též se uvádí jako pojem „odolnost argumentu“. Pro danou zprávu M je velmi jednoduché spočítat h=H(M), ale pro dané h je výpočetně nemožné vypočítat M. Tato vlastnost je velmi žádoucí a využívá se například při ukládání hesel. Neukládáme a neschraňujeme samotné heslo, ale ukládáme pouze hashový kód. Při autentizaci se pak místo přímého porovnávaní zadaného a uloženého hesla porovnávají jejich hashové kódy.
Odolnost proti kolizi prvního řádu
Dalším požadavkem kladeným na hashovací funkce začala být „bezkoliznost“, jinak v literatuře nazývaná i „slabá odolnost proti kolizi“, nebo „odolnost proti kolizi prvního řádu“.
Požadujeme, aby bylo výpočetně nemožné najít různé M a M’, tedy M≠M’ (byť dvě naprosto nesmyslná M a M’) tak, že h(M)=h(M’). Jinak řečeno, pokud najdeme dva různé vstupy, které mají stejný hashový kód, tak řekneme, že jsme našli kolizi a můžeme použitou hashovací funkci považovat za prolomenou.
Základní konstrukční prvky hashovacích funkcí
Stránka 12 z 68
Pokud totiž nejsme schopni takovou kolizi najít (vypočítat), můžeme libovolnou velkou zprávu z velmi velké množiny 2D+1–1 reprezentovat hashovým kódem malé velikosti, například 128, 256, 512, apod. bitů, tzn. množiny velikosti 2128, 2256, 2512 bitů, apod. Tedy je to pro nás jednoznačné zobrazení, i když matematicky samozřejmě není. Kolizí existuje obrovské množství, ale díky výpočetní složitosti není snadné takové kolize najít, takže můžeme hashový kód považovat za jednoznačné zobrazení. Jinak řečeno, libovolně dlouho zprávu můžeme reprezentovat malým hashovým kódem.
Tato vlastnost se využívá například u digitálního podpisu, kdy nepodepisujeme přímo celou zprávu (protože ta může být i velmi dlouhá), ale podepisujeme právě jen její hashový kód, protože víme, že najít jakoukoliv jinou (i nesmyslnou) zprávu se stejným hashovým kódem je výpočetně nemožné.
Obecně je nalezení kolize prvního řádu lehčí, než nalezení kolize druhého řádu, protože útočník hledá jakékoliv M a M’, které by měly mít stejný hashový kód, a při tomto hledání existuje tzv. „narozeninový paradox“. Tento název byl inspirován otázkou, jak velkou skupinu lidí potřebujeme, abychom měli alespoň 50% pravděpodobnost, že v ní najdeme dva lidi se stejným dnem narozenin. Výpočtem dostaneme, že P(365,23) = 0,507. Tedy stačí nám jen 23 lidí. Pokud máme skupinu 30 lidí, pravděpodobnost stoupne již na P(365,30) = 0,706, tedy 71%. Kdežto kdybychom chtěli k jednomu konkrétnímu člověku najít dalšího se stejným datem narození s alespoň 50% pravděpodobností, potřebovali bychom polovinu z množiny všech možností, tedy 356/2 = 178 lidí. Analogie s hashovacími funkcemi je zřejmá, díky tomuto paradoxu je nalezení kolize prvního řádu řádově snazší než nalezení kolize druhého řádu. Bez zajímavosti jistě není, že většina uživatelů si tyto odolnosti plete a pokud je nějaká hashovací funkce prolomena, lidé si myslí, že funkce není odolná právě proti kolizi druhého řádu, přičemž první útoky na hashovací funkce bývají na odolnost prvního řádu.
Obr. 1: Odolnost proti kolizi prvního řádu h
h h(M)=h(M’)
M
M’
?
?
?
?
Množina velikosti 2D+1–1
Množina velikosti např. 2128 bitů
Základní konstrukční prvky hashovacích funkcí
Stránka 13 z 68 Odolnost proti kolizi druhého řádu
Jinak také zvaná „odolnost proti nalezení druhého vzoru“, „bezkoliznost druhého řádu“ nebo
„silná odolnost proti kolizi“. Hashovací funkce je odolná proti kolizi druhého řádu, pokud pro daný náhodný vzor M je výpočetně nemožné nalézt druhý vzor M’≠M tak, že platí h(M)=h(M’). Jinak řečeno, je pro nás výpočetně nemožné nalézt k jedné dané zprávě jinou (byť i nesmyslnou) se stejným hashovým kódem. Pokud hashovací funkce není odolná proti kolizi druhého řádu, tak představuje velká bezpečnostní rizika. Taková funkce není doporučena k používání.
Obr. 2: Odolnost proti kolizi druhého řádu Náhodné orákulum
Na hashovací funkce se začal klást požadavek, aby výstup byl co nejvíce náhodný. Tedy aby se co nejvíce podobaly tzv. „náhodnému orákulu“. Náhodné orákulum, jinak též „stroj podivuhodných vlastností“, je orákulum, které má dvě vlastnosti:
• Na tentýž vstup vždy odpovídá stejným výstupem, tedy pamatuje si jen ty vstupy, na které už odpovědělo a odpovídá na ně stejně.
• Na vstupy, na které ještě neodpovídalo, vybírá z množiny výsledku výstup zcela náhodným výběrem, tedy je to dokonalá náhodná funkce.
2.3 Konstrukční prvky
Vzhledem k tomu, že vstupní data mohou mít délku až 264–1 bitů, je zřejmé, že hashovací funkce musí velké zprávy zpracovávat po částech. Musíme tedy zprávy rozdělit do bloků, ale navíc ještě musíme zarovnat vstupní zprávy na celistvý počet bloků [1].
h
h h(M)=h(M’)
M
M’
?
?
Množina velikosti 2D+1-1
Množina velikosti např. 2128 bitů
h-1
?
Základní konstrukční prvky hashovacích funkcí
Stránka 14 z 68 Zarovnání
Hashovací funkce zpracovává vstupní data sekvenčně po blocích určité délky. Je tedy nutné doplnit vstupní zprávu o takové množství bitů, aby délka zprávy byla dělitelná velikostí bloku. Zarovnání ale musí umožňovat jednoznačné odejmutí. Protože pokud bychom například doplňovali jen nulovými bity, nebylo by poznat, kde končí zpráva a kde začíná zarovnání. To by vedlo k mnohonásobným kolizím, protože například již doplněná zpráva ...1010000000 by mohla vzniknout ze zpráv končících …101, …1010, …10100, atd.
a všechny by měly stejný hashový kód. Zarovnání se tedy u moderních hashovacích funkcí řeší přidáním bitu 1 a poté potřebným počtem nulových bitů. To umožňuje jednoznačné odejmutí přebývajících bitů.
Damgård-Merklova konstrukce
Tento princip používají drtivá většina dnes používaných hashovacích funkcí. Algoritmus je založený na opakovaném použití kompresní funkce f, která je tak vlastně jádrem hashovacích funkcí.
Proces iteračního výpočtu hashového kódu h je možné vyjádřit v následujícím tvaru [3]:
( )
n
i i i
h h
n i pro M h f h
h IV
=
≤
≤
=
=
−1, 1
0
Samotnou kompresní funkci pak: f :
{ }
0,1hΧ{ }
0,1m →{ }
0,1hTo tedy znamená, že kompresní funkce má dva vstupy a jeden výstup. Zpracovává aktuální blok zprávy Mi a hodnotu hi–1. Výstupem je určitá hodnota hi označovaná jako kontext. Tento kontext je pak použit jako vstup do kompresní funkce v dalším kroku.
Počáteční hodnota kontextu h0 je nazývána inicializačním vektorem IV. Ten určuje blok bitů vstupující do první kompresní funkce a zahajuje tak vlastní hashování.
Kompresní funkce má přiléhavý název, protože je vidět, že zpracovává širší vstup na mnohem kratší hi. Blok zprávy Mi se funkčně promítne do kontextu hi, jehož šířka ale zůstává stejná, čímž dochází ke ztrátě informace. Kontextem pak bývá většinou několik 16bitových nebo 32bitových slov. Příkladem jsou čtyři slova u hashovací funkce MD5.
Dohromady tvoří 128 bitů, což je šířka kontextu. Výsledný hashový kód pak je buď část, nebo většinou celý poslední kontext hN.
Základní konstrukční prvky hashovacích funkcí
Stránka 15 z 68
Obr. 3: Damgård-Merklova konstrukce s vyznačenou kompresní funkcí
Damgård-Merklovo zesílení
Damgård-Merklovo zesílení bylo nezávisle oběma autory navrženo na konferenci Crypto 1989. Na závěr zprávy M se mimo zarovnání ještě rezervuje 64 bitů, které vyjadřují počet bitů původní zprávy M. 64bitové vyjádření je proto, abychom mohli hashovat zprávy až do délky D=264 –1 bitů. Do hashového kódu se tedy funkčně promítne i délka zprávy. Toto zesílení je z bezpečnostního hlediska velmi důležité, protože složitost nalezení kolize bez tohoto opatření je řádově snazší.
Konstrukce kompresní funkce
Pokud máme zprávu o délce jen jednoho bloku, vidíme, že již kompresní funkce musí být bezkolizní, aby byla bezkolizní samotná hashovací funkce. Bezkoliznost kompresní funkce tedy implikuje bezkoliznost hashovací funkce. Damgård a Merkle dokázali, že pokud je použita kompresní funkce, která je bezkolizní, tak i celá jejich konstrukce je bezkolizní.
Jak ale takovou funkci vlastně vytvořit? Taková funkce musí být jednocestná a těch moc známo není. Kryptologové si tedy pomohli znalostmi z oblasti blokových šifer. Kvalitní bloková šifra Ek(x) se totiž při stejném klíči k chová jako náhodné orákulum. I když známe spoustu vzorů a obrazů, tak nejsme schopni určit klíč a nejsme schopni zjistit zbytek zobrazení. Na známé vstupy odpovídá šifra stejnými výstupy, ale pro další vstupy nám to nijak nepomůže. Známe-li jakoukoliv množinu vstupů a výstupů, stejně nemůžeme pomocí nich, kvůli výpočetní složitosti, určit klíč k. Bloková šifra se tedy chová jako náhodné orákulum a vzhledem ke klíči k je jednocestná. Z této úvahy již konstrukce hashovací funkce
f hi-1 f f
M1 Mi … Mn
IV hi hn
Kompresní funkce f
Základní konstrukční prvky hashovacích funkcí
Stránka 16 z 68
vyplývá. Místo klíče k použijeme blok zprávy a šifrujeme pomocí něj kontext. Jinak zapsáno takto: hi = Emi(hi –1), kde E je kvalitní bloková šifra.
Obr. 4: Porovnání použití blokové šifry u šifrování a hashování Davies-Meyerova konstrukce kompresní funkce
Tato konstrukce zesiluje vlastnost jednocestnosti kompresní funkce, a to přičtením vzoru před výstupem. Formálně zapsáno[3]: Hi = f(Hi –1, mi) = Emi(Hi –1) xor Hi –1.
Výstup je tedy ještě více zamaskován, protože jej ovlivňuje i přičtení samotného vzoru.
Obr. 5: Davies-Meyerova konstrukce kompresní funkce Kontext hi-1
Kontext hi
Blok
zprávy Mi Ek
Ek
Klíč k
Otevřený text
Tato cesta je výpočetně nemožná Šifrovaný text
Šifrování
Ek
Blok zprávy Mi
Kontext hi-1
Tato cesta je výpočetně nemožná Kontext hi
Hashování
Základní konstrukční prvky hashovacích funkcí
Stránka 17 z 68 2.4 Použití hashovacích funkcí
Hashovací funkce mají v praxi řadu různorodých využití, například:
Kontrola integrity (MDC – Modification Detection Codes) – Pomocí hashovacích funkcí se kontroluje shodnost velkých souborů dat (zejména na záznamových médiích) a v telekomunikaci se používají pro získání kontrolních součtů přenášených dat.
Ukládání a kontrola přihlašovacích hesel – Velmi často se využívají hashovací funkce k uložení hesel. Tzn. že se neukládají přímo hesla, ale jen jejich hashové kódy. Toho se využívá v přihlašovacích a autentizačních systémech.
Jednoznačná identifikace dat – Využívá se hlavně vlastnosti bezkoliznosti.
Jakémukoliv bloku dat přiřadí jednoznačný identifikátor. Danému využití se říká různě, například jednoznačná reprezentace vzoru, digitální otisk dat nebo jednoznačný identifikátor dat. Využívá se u digitálních podpisů.
Porovnávání obsahu databází – lze vypočítat hashový kód obou databází a jen pomocí něj porovnávat shodnost databází. Přenášíme tak jen malý hashový kód a nemusíme pro porovnání posílat celou databázi.
Prokazování znalosti – Příkladem je konstrukce HMAC, která zpracovává pomocí hashovací funkce nejen zprávu M, ale i nějaký tajný klíč k. Toho lze využít k autentizaci, tedy prokázání znalosti tajného klíče k tak, že dotazovatel odešle výzvu, tzv. „challenge“, a od prokazovatele obdrží odpověď, tzv. „response“: response = HMAC(challenge, k)
Tímto postupem prokazovatel prokázal, že zná hodnotu tajného klíče k, přičemž útočníkovi odposlouchávajícímu komunikační kanál hodnota response nijak nepomůže.
Mimochodem tuto konstrukci považujeme za nedotčenou současnými útoky na odolnost proti kolizím, neboť není známo žádné oslabení funkce autentizačního kódu.
Autentizace původu dat – Konstrukce HMAC umí detekovat chybu při přenosu zprávy, čímž zabraňuje útočníkovi zprávu změnit, a tak zaručuje autentizaci původu dat.
Pseudonáhodné funkce při tvorbě klíčů z hesel – jinak také nazývané derivace klíčů. Hashovací funkce se v této konstrukci využívá k tvorbě pseudonáhodného šifrovacího klíče z hesla. Princip je v podstatě jednoduchý, získáme hashový kód původního hesla, a ten ještě mnohonásobně zhashujeme. Doporučuje se minimálně tisíckrát. Pak z výsledného hashového kódů využijeme tolik bitů, kolik zrovna potřebujeme. Tuto konstrukci považujeme také za nedotčenou současnými útoky na odolnost proti kolizím.
Pseudonáhodné generátory – Používají se hlavně v případech, kdy máme k dispozici nějaký řetězec dat (tzv. „seed“) s dostatečnou entropií a potřebujeme z tohoto vzorku získat
Základní konstrukční prvky hashovacích funkcí
Stránka 18 z 68
posloupnost o větší délce, třeba i delší, v řádech gigabajtů apod. Jako seed pak lze použít například předchozí příklad, u internetového bankovnictví se využívá například záznam pohybu myši apod. Rozdíl oproti předchozímu použití není velký. Jen místo vstupu nepoužijeme heslo, ale právě náhodný, námi zvolený zdroj a výsledek se nehashuje stále dokola, ale vzniká dlouhá posloupnost jako výstup. Ani tuto konstrukci nepovažujeme za dotčenou současnými útoky na odolnost proti kolizím.
Nástroje a metody pro zlomení
Stránka 19 z 68
3 Nástroje a metody pro zlomení
3.1 Útoky metodou hrubé síly
Jinak také nazývané útoky metodou totálních zkoušek, jsou zaměřené hlavně na odolnost hashovacích funkcí proti kolizím. Pokud totiž není hashovací funkce prolomena pomocí kryptoanalýzy, závisí bezpečnost hashovací funkce hlavně na délce hashového kódu. Nechť je výstup z hashovací funkce, délka hashového kódu, n bitů. Poté potřebujeme vyzkoušet 2n kombinací pro nalezení kolize druhého řádu. Pro hashovací funkci s délkou kódu 160 bitů (například SHA-1) je to tedy 2160 kombinací. Nalezení kolize druhého řádu je díky narozeninovému paradoxu snazší, stačí nám 2n/2 kombinací. Pro uvedenou hashovací funkci tedy 280 kombinací. Příkladem takového útoku byl například projekt MD5crack, který se snažil o nalezení kolize pomocí hrubé síly u hashovací funkce MD5. Cílem bylo přesvědčit bezpečnostní architekty, aby od používání MD5 upustili. V roce 2004 však byl projekt zastaven, protože čínský tým vedený profesorkou Wangovou publikoval zprávu [4], kde dokázala, že pomocí kryptoanalýzy lze nalézt kolize u MD5 mnohem efektivněji.
Útok hrubou silou lze ale aplikovat i jiným způsobem. Pokud je totiž někde uložené heslo ve formě hashového kódu a není pozměněno tzv. solí, tak můžeme z tohoto hashového kódu získat heslo také pomocí tohoto útoku. Většina uživatelů totiž volí jednoduchá hesla bez kombinace číslic a speciálních znaků, a tak je výpočetně možné vyzkoušet všechny kombinace například velkých a malých písmen, pomocí hashovací funkce získat jejich hashový kód, a ten porovnat s uloženým. Doba potřebná k odhalení hesla je pak závislá na délce hesla, jakou uživatel zvolil, a na tom, jestli v heslu použil například i číslice či speciální znaky.
3.2 Slovníkový útok a Rainbow tables
Vzhledem k tomu, že uživatelé často používají jako hesla běžně používaná slova, je možný i slovníkový útok. Připravíme nebo stáhneme již připravený slovník, který běžně obsahuje desetitisíce nejpoužívanějších slov v jednom nebo více jazycích a poté z těchto slov vytvoříme hashové kódy, které při útoku porovnáme s hashovými kódy, ze kterých chceme zjistit hesla..
Jakousi kombinací dvou předchozích metod útoků je útok pomocí Rainbow tables. Tento útok využívá předem připravených tabulek, ve kterých jsou uložena hesla a hashové kódy.
Tyto hashové kódy ale nejsou přímým výsledkem hashovaní hesel, ale mezi heslem a uloženým hashovým kódem dojde několikrát k takzvané redukci a opětovnému hashování.
Princip ukládání a vyhledávání v takové tabulce se pokusím vysvětlit pomocí Obr. 6.
Nástroje a metody pro zlomení
Stránka 20 z 68
Obr. 6: Princip ukládání tabulky u útoku Rainbow Tables
Hlavním trikem u Rainbow Tables je nadefinování a používání tzv. redukční funkce R, která převádí hashový kód zpět na jiné možné heslo. Jedno z hesel z množiny možných se vybere a vypočítá se jeho hashový kód pomocí hashovací funkce H, tento se převede pomocí redukční funkce R zpátky na jiné možné heslo, opět se vypočítá jeho hashový kód a toto se opakuje tolikrát, kolikrát si určíme. Konečný hashový kód poté uložíme. Pro další řádek tabulky vybereme další heslo z množiny možných a celý postup opakujeme.
Při vyhledávání hesla pomocí takové tabulky je nejběžnějším postupem porovnat hashový kód, z kterého chceme získat heslo, s konečnými hashovými kódy v tabulce. Pokud tabulka námi vyhledávaný hashový kód neobsahuje, pomocí redukční funkce R vypočítáme další možné heslo a z něj pomocí H hashový kód. Ten opět porovnáváme s hashovým kódy v tabulce, tento postup opakujeme. Pokud tabulka hashový kód obsahuje, vezmeme heslo ze stejného řádku a vypočítáváme z něj hashové kódy pomocí H a možná hesla pomocí R a zpět hashové kódy tak dlouho, dokud nenarazíme na námi vyhledávaný hashový kód. Heslo, z kterého jsme tento hashový kód vypočítali je pak heslem, které hledáme. Útok pomocí Rainbow Tables je tedy jakýmsi kompromisem, mezi útokem s předem připravenou tabulkou všech možných hesel, což je velice paměťově náročné a útokem pomocí hrubé síly, což je velice výpočetně náročné. Tabulka u metody Rainbow Tables je několikrát menší, než předem připravená tabulka všech možných hesel a jejich hashových kódů a zároveň je mnohem rychlejší, než útok hrubou silou.
Metody útoku pomocí Rainbow tables využívají například programy Ophcrack1, RainbowCrack2, Cain3 a jiné.
1 WWW: http://ophcrack.sourceforge.net/
2 WWW: http://project-rainbowcrack.com/
3 WWW: http://www.oxid.it/cain.html možná hesla
hashové kódy
začátek
konec
H H
H R
R
Nástroje a metody pro zlomení
Stránka 21 z 68
Navíc je možno takovouto předem připravenou tabulku k útoku na konkrétní hashovací funkci získat z Internetu. Dokonce existují stránky, kde lze přímo do formuláře na www stránkách vložit hashový kód, který se na serveru porovná s uloženou databází hashových kódů a ta téměř okamžitě vrátí výsledek – tomuto útoku se také někdy říká „on-line cracking“.
Vzhledem k tomu, že jsou využívané počítače, které jsou vyhrazené pouze pro počítání dalších a dalších kombinací, vznikají velice rozsáhlé databáze hashových kódů a jim odpovídajících hesel.
Tento útok je tedy velice efektivní a je hlavním důvodem, proč by se měly hashové kódy uživatelských hesel ukládat pouze s tzv. solí. Viz. kapitola 6.2 Hashovací funkce a ukládání hesel.
3.3 Kryptoanalýza
Kryptoanalýza hashovacích funkcí je zaměřena na vnitřní strukturu komprimační funkce f.
Cílem kryptoanalýzy je pak najít kolizi alespoň u jedné realizace kompresní funkce f. Její vnitřní struktura je totiž známá, a navíc je založena na známých blokových šifrách.
Diferenciální kryptoanalýza pak je relativně efektivní nástroj sloužící nejen k útokům na hashovací funkce, ale i na různé blokové šifry. Princip diferenciální kryptoanalýzy by se dal jednoduše shrnout jako hledání rozdílů mezi vstupem do kompresní funkce a výstupem z ní. Výstupy a hlavně nalezené anomálie se pak statisticky vyhodnocují. Příkladem kryptoanalýzy je například takzvaná metoda tunelování, popsána v kapitole 4.3 MD5.
Současné hashovací funkce.
Stránka 22 z 68
4 Sou č asné hashovací funkce.
4.1 LMHash
Název je zkratkou LAN Manager hash. Tato hashovací funkce byla používána k ukládání uživatelských hesel kratších než 15 znaků především v operačních systémech Windows až do verze Windows XP. V novějších Windows Vista je ve výchozím nastavení tato funkce z bezpečnostních důvodů vypnuta, ale pro zpětnou kompatibilitu je stále dostupná.
Hashový kód hashovací funkce LM hash [2] se počítá následovně: 1. Uživatelské heslo je konvertováno na velká písmena.
2. Heslo, pokud je potřeba, je doplněno nulami do velikosti 14 bajtů. 3. Takto doplněné heslo je rozděleno na dvě 7bajtové hodnoty.
4. Tyto hodnoty jsou použity pro vytvoření dvou DES klíčů. Zašifrováním konstant pomocí těchto klíčů pak vzniknou dva kryptogramy.
5. Hashový kód vznikne spojením těchto dvou kryptogramů.
Přestože je tato hashovací funkce založena na velmi dobře známé blokové šifře DES, lze velice jednoduše provést útok díky dvěma zásadním slabinám. První slabinou je skutečnost, že hashovací funkce heslo delší než 7 znaků rozdělí na dvěčásti, a každou část hashuje separátně. Druhá slabina pak je důsledkem větší uživatelské přívětivosti. Pro případ, že by uživatel měl při vytváření hesla například aktivovanou klávesu Caps Lock, jsou před samotným hashováním všechna malá písmena převedena na písmena velká.
Pokud by tyto dvě slabiny tato funkce neměla, tak by možných hesel teoreticky bylo 9514, tedy 95 znaků ASCII a délka hesla 14 znaků. Vzhledem k rozdělení na půlky však můžeme útočit na každou část separátně, a stačí nám tedy vyzkoušet 957 kombinací. Díky převedení znaků na velká písmena však musíme počet znaků redukovat už jen na 69. Stačí nám tedy již vyzkoušet jen 697 kombinací, což je přibližně 243 kombinací, a to moderní počítač zvládne pomocí útoku hrubou silou během několika hodin. Vzhledem k tomu, že tato hashovací funkce nepodporuje tzv. „zasolení“, můžeme si všechny možné kombinace předem spočítat, nebo použít běžně dostupné programy jako RainbowCrack, L0phtCrack, CAIN a jiné. Pak je odhalení hesla z hashového kódu záležitostí řádově sekund. Z bezpečnostního hlediska je tedy používání této funkce vyloženě nebezpečné.
Současné hashovací funkce.
Stránka 23 z 68 Ukázka 14 místného hashového kódu:
• Vstup: UkazkaHashKodu
• Výstup: 34E3C1DB803D174A535F9A93DD9B8922
Dalším příklad demonstruje druhou popsanou slabinu, tedy že velikost písmen nemá na výsledný hashový kód vliv:
• Vstup: UkAzKaHaShKoDu
• Výstup: 34E3C1DB803D174A535F9A93DD9B8922
První slabinu lze také velice jednoduše demonstrovat. Díky doplnění vstupu nulami do velikosti 14 bajtů a rozdělení na půlky je druhá část hesla složeného ze 7 písmen vlastně jen zhashovaných sedm nul, takže druhá část kódu je u obou vstupů stejná:
• Vstup1: prvnipr
• Výstup1: E75881017480121EAAD3B435B51404EE
• Vstup2: druhypr
• Výstup2: 710A766B0F43C931AAD3B435B51404EE 4.2 MD4
Hashovací funkce MD4 [5]byla navržena již v roce 1990 profesorem Ronaldem Rivestem z MIT (Massachusetts Institute of Technology). Na svojí dobu měla pokročilou konstrukci, která se stala inspirací i pro další hashovací funkce jako MD5, funkce z rodiny SHA nebo RIPEMD.
Vstupní data jsou rozdělena na bloky dat o velikosti 512 bitů, zarovnána potřebným počtem bitů a doplněna v posledních 64 bitech posledního bloku o informaci o délce zprávy.
MD4 pak pracuje s délkou kontextu 128 bitů rozděleným na čtyři 32 bitová slova A, B, C a D.
Každý blok výpočtu se skládá ze 3 rund, z nichž každá obsahuje 16 operací s nelineárními funkcemi F, bitovým xor a levou bitovou rotací. Na Obr. 7 je ukázka jedné takové operace.
Výsledný hashový kód je stejně dlouhý jako kontext, tedy 128 bitů.
Současné hashovací funkce.
Stránka 24 z 68
Obr. 7: Ukázka jedné operace hashovací funkce MD4
Ukázka hashového kódu MD4:
• Vstup: UkazkaHashKodu
• Výstup: A1FB04EA608E56E4BF2E0D25FA8D9A32 Bezpečnost MD4
První slabiny MD4 byly publikovány již rok po uvedení, tedy v roce 1991. První kolize pak byla nalezena roku 1996 [6]. Čínský tým soustředěný kolem profesorky Wangové našel velice efektivní způsob, jak generovat u této funkce kolize [4]. Postup byl dále zefektivněn a na dnešních počítačích je možné generovat kolize již v řádu sekund i méně. Z uvedeného je patrné, že dnes již je tato funkce z bezpečnostního hlediska nepoužitelná.
A B C D
<<<
A B C D
Mi ki
F
Současné hashovací funkce.
Stránka 25 z 68 Svět v roce 1996 oblétl velice výmluvný příklad [6] kolize:
Obr. 8: Kolize u MD4
Jak je vidět, tyto zprávy se liší velice málo, ale přesto mají stejný hashový kód.
4.3 MD5
4.3.1 Konstrukce MD5, bezpečnost
Poté co se ukázaly slabiny MD4, navrhl Ronald Rivest již v roce 1991 [7] funkci MD5. MD5 je vlastně jen optimalizovaná funkce MD4, která se snaží odstranit kritické chyby. Používá navíc jedinečnou aditivní konstantu v každém cyklu výpočtu kontextu, takže oproti třem konstantám v MD4 jednu přidává.
Konstrukčně jsou MD4 a MD5 velice podobné. Změna je, že blok výpočtů se neskládá ze tří rund jako MD4, ale navíc jednu rundu přidává. Každá runda také obsahuje 16 operací.
Celkově je tedy u MD5 na jeden blok potřeba 64 operací, oproti 48 operacím u MD4. Ukázka jedné takové operace a vyznačený rozdíl oproti MD4 – viz Obr. 9.
********************
CONTRACT
At the price of $176,495 Alf Blowfish sells his house to Ann Bonidea. ...
********************
CONTRACT
At the price of $276,495 Alf Blowfish sells his house to Ann Bonidea. ...
Současné hashovací funkce.
Stránka 26 z 68
Obr. 9: Ukázka jedné operace funkce MD5 s vyznačeným rozdílem od MD4
Ukázka hashového kódu MD5.
• Vstup: UkazkaHashKodu
• Výstup: F98A108F4CCFC291EBDEE7B0BDDDFA8C Bezpečnost
Již v roce 1994 navrhli pánové P. van Oorschot a M. Wiener paralelně pracující stroj na vyhledávání kolizí, ten by však měl tehdy cenu 10 miliónů dolarů. Tvrdili, že kolizi by uměl vyhledat přibližně za 24 dnů. V roce 1996 na konferenci Eurocrypt prezentoval Dobbertin [8] kolizi kompresní funkce MD5. Demonstroval nalezení h, X a X’ tak, že f(h, X)
= f(H, X’). Přesto však mohla být funkce dále používána.
V roce 2004 ale čínský tým vedený profesorkou Wangovou prezentoval na konferenci Crypto 2004 kolize funkcí MD4, MD5, HAVAL-128 a RIPEMD [4]. Nalezli metodu, pomocí níž lze nalézt kolizi dvou 1024 bitových zpráv v řádu několika hodin. Postup spočívá v tom, že se naleznou dva různé 512bitové bloky M1 a M2. To trvalo na 32procesorovém počítači zhruba hodinu. Poté je potřeba nalézt k nim další dva bloky N1 a N2 tak, že po složení mají zprávy (M1 ,N1) a (M2 ,N2) stejný hashový kód.
Na začátku března 2005 pak Vlastimil Klíma publikoval zprávu [9], ve které popisuje způsob jak nalézt kolizi dokonce na běžně dostupném notebooku, pro libovolnou inicializační
A B C D
<<<
A B C D
Mi ki
F
rozdíl oproti MD4
Současné hashovací funkce.
Stránka 27 z 68
hodnotu, a to ještě efektivněji, než se to povedlo čínskému týmu. Průměrná doba nalezení kolize na notebooku s procesorem Pentium 1,6 GHz pak činila 8 hodin. Poté Vlastimil Klíma přišel s myšlenkou tzv. tunelování [10]. Tunelování nahradilo metodu mnohonásobné modifikace zpráv a zkrátilo čas potřebný pro generování kolizí jen na přibližně 17 sekund na běžném počítači (Pentium 4 – 3,2 GHz).
4.3.2 Tunelování
Tuto metodu bych tu chtěl krátce zmínit, protože je velice revoluční, otevřela novou možnost pro kryptoanalýzu hashovacích funkcí a představuje již dnes, ale hlavně v dohledné budoucnosti další bezpečnostní problém dnešních hashovacích funkcí. Autor Vlastimil Klíma je přesvědčen, že se naleznou způsoby, jak konstruovat diferenční schémata (pro hashovací funkce jako jsou MD5, SHA-0, SHA-1, SHA-2, ale i jiné), která již budou zaměřena přímo na existenci využitelných tunelů v nich obsažených.
První kolize u hashovací funkce MD5 byly nalezeny pomocí metody mnohonásobné modifikace zpráv [4]. Tato metoda vede k naplňování množiny postačujících podmínek od začátku zprávy až do dosažení tzv. bodu verifikace (POV), za kterým již nejsme schopni nic ovlivnit. Vzhledem k tomu, že za tímto bodem již nejsme schopni ovlivnit výpočty, je pro nalezení kolize potřeba najít velké množství takových bodů, aby se náhodně splnily i všechny dostačující podmínky. U hashovací funkce MD5 je to konkrétně 229 bodů POV. Jeden z těchto bodů POV bude splňovat i zbývající postačující podmínky, a ten je pak použit pro kolizi.
Metoda tunelování naproti tomu začíná až v bodě POV. Několika tzv. tunely z takovéhoto bodu vytvoří geometrickou řadou dostatečné množství dalších POV, aniž přitom narušíme počáteční podmínky před bodem POV. Těchto tunelů je například u MD5 známo více, tyto mají tzv. „sílu“ n a vytvoříme pomocí nich 2n bodů POV. Tunely se dají navíc kombinovat, takže z jednoho původního bodu POV lze vytvořit jedním tunelem 2n1 bodů POV, a z každého z nich pak získat dalším tunelem 2n2 dalších bodů POV. U MD5 je například známa kombinace tunelů, která dohromady dává sílu n = 24. Z každého jednoho bodu POV tak jsme schopni vytvořit 224 dalších bodů POV. Stačí tedy vygenerovat jen 25 = 32 nestejných bodů POV pro nalezení kolize. To je velice malé číslo oproti 229 potřebných bodů POV u metody mnohonásobné modifikace zpráv.
4.4 SHA-0 a SHA-1
Jedná se o hashovací funkce přímo vycházející z konstrukce funkcí MD4 a MD5. SHA-0 byla publikována úřadem NIST již v roce 1993 [11]. Tato verze však byla kvůli blíže nespecifikované chybě stažena a jako standard byla schválena v roce 1995 pokročilejší verze
Současné hashovací funkce.
Stránka 28 z 68
SHA-1 [12]. SHA-1 se liší od původní SHA-0 přidáním jedné bitové operace do expanzní funkce vstupních dat, jež je součástí kompresní funkce.
Délka vstupu může být až 264 –1. Vstup je zarovnán a rozdělen na bloky o délce 512 bitů. Výstupní hashový kód má délku 160 bitů. Pracuje tedy s kontextem o velikosti 160 bitů, který je rozdělen na pět 32bitových slov: A, B, C, D a E. Výpočet se pak skládá z 4 rund, z nichž každá obsahuje 20 operací založených na nelinearních funkcích F, bitovém xor a levé bitové operaci. Viz Obr. 10.
Ukázka hashového kódu SHA-1.
• Vstup: UkazkaHashKodu
• Výstup: FB8F0B19C9D24AA7033D7638701119F8E48D8714
Obr. 10: Kompresní funkce SHA-1 Bezpečnost
SHA-0 je již považována za prolomenou. Již v roce 1998 byl publikován způsob [13], jak lze generovat kolizi se složitostí 261. Čínský tým pod vedením profesorky Wangové pak vydal v roce 2005 zprávu[13], v níž ukazují plnou kolizi SHA-0. To vše se složitostí jen 239 operací.
SHA-1 je v současné době stále velmi používanou hashovací funkcí. Soustředí se na ní tedy velká pozornost. NIST doporučil tuto funkci přestat používat do roku 2010. V únoru
A B C D E
A B C D E
<<<RL5
Wt
kt
<<<RL30
ft
Současné hashovací funkce.
Stránka 29 z 68
2005 tým profesorky Wangové publikoval zprávu [14], kde dokazují, že lze nalézt kolizi se složitostí 269, kdežto teoretická složitost pro nalezení prvního vzoru by měla být 2n/2, tedy 280. V říjnu téhož roku pak publikovali další zprávu [15], kde metodu ještě vylepšili – složitost nalezení prvního vzoru snížili na 263. To je pořád velmi vysoké číslo a žádná kolize ještě nebyla veřejně demonstrována, vzhledem k narůstajícím rychlostem počítačů se však soudí, že při použití distribuovaného výpočtu je útok dosažitelný již dnes. Z bezpečnostního hlediska tedy nelze považovat tuto funkci za bezpečnou. Vývojáři ji však pravděpodobně budou používat nadále, minimálně do doby, než bude veřejně představena alespoň jedna kolize této funkce.
4.5 Rodina SHA-2
Tato rodina hashovacích funkcí [16] obsahuje několik variant – SHA-224, SHA-256, SHA- 384 a SHA-512. SHA-2 je jejich souhrnné označení. Číslo za názvem algoritmu značí délku výstupu v bitech. Složitost nalezení prvního vzoru je tedy pro tyto funkce 2112, 2128, 2192 a 2256.
Tyto funkce lze rozdělit na dvě podskupiny, kdy SHA-224 je vlastně jen varianta SHA-256 s kratším výstupním hashovým kódem a jinými inicializačními vektory. Podobně i funkce SHA-384 je odvozena od SHA-512. Výstup odvozených funkcí vznikne jen zkrácením výstupu funkcí, ze kterých jsou odvozeny. Protože mají jiné inicializační vektory, mají rozdílný hashový kód, takže například výstupní hashový kód funkce SHA-224 není pouze kusem hashového kódu funkce SHA-256.
Algoritmus u funkcí SHA-224 a SHA-256 pracuje s kontextem 256 bitů. Ten se rozdělí na osm 32 bitových slov A, B, C, D, E, F, G a H. V kompresní funkci pak zpracovává bloky dat o velikosti 512 bitů, pomocí kterých modifikuje kontext. Každý blok výpočtu se pak skládá z 64 operací založených na operacích +, and, or, xor, shr a rotr. Velikost vstupních dat může mít délku až 264–1 bitů.
SHA-384, SHA-512 se od předchozích dvou liší samozřejmě velikostí výstupního hashového kódu a tím i velikostí kontextu, který u těchto funkcí má velikost 512 bitů. Ten se rozdělí na osm 64 bitových slov A, B, C, D, E, F, G a H. V kompresní funkci pak zpracovává bloky dat o velikosti 1024 bitů, pomocí kterého modifikuje kontext. Každý blok výpočtu se pak skládá z 80 operací založených opět na operacích +, and, or, xor, shr a rotr.
Velikost vstupních dat pak může mít délku dokonce až 2128 –1 bitů. Bezpečnost
Co se týče konstrukce, jsou tyto hashovací funkce velice podobné funkci SHA-1 a starším.
Pracují však se složitějšími funkcemi a širšími vstupy, poskytují tak větší odolnost proti kolizi a jsou považovány za bezpečné. Začínají se objevovat první útoky na tyto funkce. Například
Současné hashovací funkce.
Stránka 30 z 68
nalezené kolize pro až 23 a 24 kroků funkce SHA-256 se složitostí přibližně250 a 253 [17].
Tyto útoky však zatím nepředstavují reálné riziko.
Ukázka hashového kódu funkce SHA-512:
• Vstup: UkazkaHashKodu
• Výstup:
F9DAE2F23CADC5D90CB279E5FC3F38FBA72E26F33350222DCBFC5C133 C434860
Budoucnost hashovacích funkcí
Stránka 31 z 68
5 Budoucnost hashovacích funkcí
5.1 Problémy konstrukce dnešních hashovacích funkcí
Čím dál více se ukazuje, že všechny současné hashovací funkce jsou už ze své podstaty slabé.
Objevuje se čím dál více postupů, jak různé hashovací funkce oslabit. Proč tomu tak je?
Vzhledem k tomu, že hashovací funkce musí plnit svoji funkci a zachovávat si všechny vlastnosti i při hashování jediného bloku, můžeme si vlastně zkoumání zjednodušit pouze na zkoumání kompresní funkce.
Všechny dnešní hashovací funkce používají v kompresních funkcích blokové šifry. Jenže předpokladem u konstrukce blokové šifry bylo, že obsahuje hodnotu, kterou útočník buď nezná, nebo nemůže modifikovat – šifrovací klíč. Pomocí této neznámé hodnoty pak utajuje způsob převodu otevřeného textu na zašifrovaný a naopak. Jenže u hashovacích funkcí může manipulovat se všemi vstupy. A to je základní bezpečnostní nedostatek dnešních hashovacích funkcí, žádná klasická bloková šifra není připravena na situaci, kdy útočník zná šifrovací klíč.
U hashovacích funkcí je však klíčem zpráva, kterou hashujeme. Klíč je tedy útočníkovi volně k dispozici a může jej dokonce libovolně modifikovat, na to nejsou blokové šifry vůbec připraveny. Jak uvádí Vlastimil Klíma [18], přestože by snad blokové šifry teoreticky pro bezpečnou kompresní funkci použít šly, nelze to udělat efektivně. Hashovací funkce ale musí být efektivní, a tak se tento problém se dostává do rozporu s bezpečností.
Bohužel podmínky a kritéria nově vznikajícího standardu SHA-3 jsou nastaveny velice konzervativně a při pohledu na zaslané příspěvky je patrné, že tento koncept zůstane zachován, což může do budoucna znamenat velké problémy.
5.1.1 Generické problémy iterativních hashovacích funkcí
Posledních několik let se ukazuje [19][20], že dokonce samotná iterativní konstrukce hashovacích funkcí implikuje odlišnost těchto funkcí od náhodného orákula, a že tato konstrukce má svoje slabiny. Sama o sobě generuje problémy, protože bez ohledu na to, co je uvnitř hashovací funkce, umožňuje generovat multikolize a kaskádovitá konstrukce u ní pozbývá smyslu.
5.1.2 R-násobná kolize s nižší složitostí
Jednu z prací na toto téma prezentoval Joux [19] na konferenci Crypto 2004. Uvádí se v ní, že generovat mnohonásobné kolize je mnohem jednodušší, než ve srovnání s náhodným orákulem. Nalezení mnohonásobné kolize by mělo mít matematicky složitost 2n(r –1)/r, ale Joux ukázal, že lze tyto kolize produkovat jednodušeji, a to bez ohledu na to, co je uvnitř hashovací funkce.
Budoucnost hashovacích funkcí
Stránka 32 z 68
Obr. 11: Ukázka nalezení multikolize s nižší složitostí
Princip je až překvapivě jednoduchý. Vezmeme inicializační vektor IV, produkujeme kolizi, vedoucí na kontext se stejným hashovým kódem, což umíme se složitostí 2n/2. Poté produkuje druhou kolizi, vedoucí z jednoho kontextu na druhý, což umíme opět se složitostí 2n/2. Tento postup opakujeme k-krát až dostaneme kontext hk.
Trik spočívá v tom, že si lze vybrat u kolizí vždy jednu z cest u nalezených kolizí jednotlivých kontextů. Dostaneme tedy 2k multikolizí. Složitost by měla být zhruba 2n, ale místo toho je k.2n/2. U tohoto postupu je naprosto jedno, jaký je vnitřek hashovací funkce.
Jediná záchrana tedy je dostatečně složitá hashovací funkce, která by zaručila, aby tento postup byl výpočetně nemožný.
5.1.3 Kaskádovitá konstrukce
Když se ukázalo, že i používané hashovací funkce jako MD5, SHA-0 a SHA-1 jsou prolomeny, předpokládalo se, že jejich nepoužitelnost oddálí využití kaskádovité konstrukce.
Myšlenkou je zřetězení dvou hashovacích funkcí jako například MD5 a SHA-1. Výstupní hashový kód této konstrukce má délku 128 + 160 bitů, tedy dostatečných 288 bitů. Některé certifikační autority tuto konstrukci ještě relativně nedávno používaly, některé možná dokonce doteď používají. Předpokladem je, že složitost S(FG) nalezení kolize hashového kódu bude rovna součinu nalezení kolize dílčích hashových kódů S(FG)=S(F)*S(G).
Joux ve své práci [19] ale dokázal, že tato konstrukce složitost navyšuje jen velmi málo.
Postup vychází z postupu nalézání r-násobných multikolizí. Pokud je první hashovací funkce F iterativní s délkou hashového kódu nf < ng, můžeme vytvořit ng/2 návazných kolizí funkce F se složitostí ng/2*S(F). Tím dostaneme 2ng/2-násobnou kolizi vzhledem k funkci F.
Poté nám stačí mezi těmito zprávami najít jednu kolizi vzhledem k funkci G, a dostaneme dvě zprávy, které mají stejný hashový kód vzhledem k F i G. Složitost tohoto výpočtu
IV h1 h2 ...
2n/2
hk
2n/2 2n/2 = k . 2n/2
Budoucnost hashovacích funkcí
Stránka 33 z 68
je rovna ng/2*S(F)+2ng/2, což je přibližně S(F) + S(G), tj. řádově mnohem méně než očekávaná složitost S(FG). Tato konstrukce tedy nemá smysl.
5.1.4 Nalezení druhého vzoru u dlouhých zpráv snadněji než se složitostí 2n Autoři Kelsey a Schneier publikovali zprávu [20], ve které dokazují, že lze pro dlouhé zprávy o délce přibližně 2k blízké 2n/2, zkonstruovat druhý vzor u iterativních hashovacích funkcí s mnohem menší složitostí. A to díky Davies-Meyerově konstrukci, která umožňuje vytvoření tzv. pevného bodu hj = f(hj,Nj) a vytvoření několika seznamů průběžných kontextů, mezi kterými pak hledáme kolizi. Mezi těmito seznamy tedy nalezneme kolizi, ale takové zprávy mají různou délku. Využijeme tedy pevného bodu, který může být vložen do funkce tolikrát, kolikrát je potřeba. Tím dostaneme potřebný počet bloků, přičemž kontext se nezmění. Za takto nalezené dvě zprávy, které vedou na kontext se stejným hashovým kódem, připojíme zbytek zprávy M, a tím dostaneme druhý vzor zprávy M. To vše se složitostí 2n/2 + 1 + 2n-k + 1, což je mnohem méně, než očekávaných 2n. Například u funkce SHA-1 můžeme tímto postupem vygenerovat druhý vzor se složitostí 2106, což dnes sice stále dostačuje, ale je to řádově mnohem méně než teoretických 2160.
5.2 NIST, soutěž SHA-3
Hashovací funkce mají mnoho využití, například při ukládání hesel, bezpečném připojení do sítě/Internetu, pomáhají při skenování virů, a desítky dalších využití. V podstatě by bez nich Internet, tak jak jej známe, nemohl existovat. Na to, jak jsou v dnešním světě důležité, jsou ale prozkoumány relativně málo a jsou velmi málo studovány. Nejen tento problém chce vyřešit americký Národní Institut pro standardy a technologie, zkráceně NIST (The National Institute of Standards and Technology), soutěží o nový standard SHA-3, který má nahradit hashovací funkce ze stávající rodiny SHA. Algoritmy použité v této rodině jsou považovány za jednoduché a útoky na tyto funkce přibývají. Již dnes je jisté, že prolomení těchto funkcí je v podstatě jen otázka času. NIST tedy chce tyto funkce nahradit právě SHA-3.
NIST zvolil veřejnou soutěž. S tímto postupem už slavil úspěch, kdy v roce 1997 vyhlásil soutěž o blokovou šifru, která nahradila DES. Tehdy se přihlásilo 15 kandidátů. Vznikl úspěšný Advanced Encryption Standard – AES [31].
Příspěvky do soutěže o SHA-3 mohly být posílány do 31. října 2008. Bylo přijato 64 příspěvků. Většinu příspěvků do soutěže AES poslali profesoři. Co se týče zasílatelů do soutěže SHA-3, účast již je různorodější, zasílatelé jsou nejenom z akademické půdy, ale i z průmyslu, nebo od lidí, kteří mají kryptografii jen jako hobby. Zajímavostí je, že jednomu ze zasílatelů je dokonce jen 15 let. Na neoficiálních internetových stránkách The SHA-3 ZOO [21] jsou kandidáti vypsání, společně s výčtem hashovacích funkcí, u kterých již byli objeveny slabiny nebo na ně byl podniknut úspěšný útok. 56 přihlášených funkcí bylo
Budoucnost hashovacích funkcí
Stránka 34 z 68
v době psaní této diplomové práce známo. Do prvního kola postoupilo 51 hashovacích funkcí.
Odborná veřejnost a samozřejmě i zasílatelé mezi sebou, se snaží poukázat na slabosti hashovacích funkcí, nebo je dokonce prolomit. Nutno říci, že úspěšně. Situace se mění téměř každým dnem a neoficiálně [21] zůstává neprolomeno či bez větších slabin již jen 26 příspěvků. Ty obsahují hashovací funkce: ARIRANG, BLAKE, Blue Midnight Wish, CHI, CRUNCH, CubeHash, ECHO, Edon-R, ESSENCE, FSB, Fugue, Grøstl, Hamsi, JH, Keccak, Lane, Lesamnta, Luffa, MD6, SANDstorm, Shabal, SHAvite-3, SIMD, Skein, SWIFFTX, TIB3.
NIST chce co nejrychleji vybrat cca 15 nejslibnějších příspěvků a ty předložit veřejnosti minimálně rok ke kryptoanalýze. Poté bude následovat ještě užší výběr, až nakonec v roce 2011 by měl být vybrán vítěz. Finální standard je očekáván v roce 2012.
Jako zajímavost bych zde chtěl zmínit dva návrhy, u kterých je spoluautorem Vlastimil Klíma. Návrhy obsahují dva nejrychlejší (nejvýkonnější) algoritmy soutěže:
Blue Midnight Wish
Doprovodná dokumentace [30] k této funkci uvádí, že tato funkce má výstup dlouhý 224, 256, 384, nebo 512 bitů, tedy stejně jako SHA-2. Dále uvádí, že tato funkce je odolná proti útoku na délku zprávy a proti multikoliznímu útoku. Také je tato funkce mnohem efektivnější (výkonnější) než SHA-2 při zachování stejné, nebo lepší bezpečnosti. Søren S. Thomsen však publikoval dokument, kde uvádí, že nalezení tzv. blízké kolize (tj. nalezení dvou vstupů, které se liší jen velice málo, tedy o pár bitů, ale které vedou na stejný hashový kód) je u této funkce jednodušší, než by matematicky mělo být, a to u všech verzí této funkce.
EDON-R
Tento návrh je ze všech zaslaných návrhů hashovacích funkcí v soutěži SHA-3 nejrychlejší (nejvýkonnější). Základním prvkem jsou kvazigrupy. Kvazigrupa je vlastně grupoid, na kterém lze neomezeně provádět inverzní operaci. Grupoid je algebraická struktura s jednou operací. Kvazigrupové operace jsou v tomto návrhu definovány pomocí rychlých a dostupných operací implementovaných ve všech procesorech: sčítání, xor a bitové rotace.
V použití kvazigrup je kouzlo rychlosti této navrhované hashovací funkce a zároveň nejvíce kritizovanou částí návrhu, protože přispěvatelé jiných návrhu namítají, že kvazigrupy jsou neprobádanou oblastí a snaží se o diskvalifikaci tohoto návrhu.
5.3 Hashovací funkce HDN typu SNMAC
Problémy dnešních hashovacích funkcí již byly v této práci rozebrány. Jak navrhnout nové hashovací funkce? Vlastimil Klíma a kolegové uvedli na kryptologické konferenci Eurocrypt 2007 velice zajímavý koncept [22],[24] tzv. hashovacích funkcí nové generace.
