Hashovací funkce

Jedná se o jednosměrné funkce, které musí splňovat přesně definované podmínky. Základní hashovací funkce mapují řetězec libovolné délky (zpráva, datový soubor) na řetězec konstantní délky a vytvářejí tak otisk vstupního řetězce. Výsledný otisk se označuje jako výtah, hash, fingerprint nebo miniatura a je závislý na všech bitech vstupního řetězce. Tyto funkce slouží ke kontrole integrity dat, k porovnání dvojice zpráv, k vyhledávání, indexování a využívají se pro tvorbu digitálních podpisů.

Mezi nejznámější hashovací funkce patří MD4, MD5, SHA-1 a SHA-2. Tyto algoritmy jsou založeny na podobných principech jako blokové šifry, např. AES. Každá hashovací funkce v principu není injektivní (čili prostá), existují tedy různé zprávy poskytující stejný hash. To samo o sobě není problém, pokud hashovací funkce splňuje následující požadavky:

Formálně jde o funkci h, která převádí vstupní posloupnost bitů na posloupnost pevné délky n bitů.

h: D \rightarrow R,

kde |D|>>|R|.

Přímo z této definice vyplývá, že existují kolize, to znamená existenci vstupních dat (x,y) takových, že h(x) = h(y), tj. dvojice různých vstupních dat může mít stejný hash. Lze jen snižovat pravděpodobnost, že nastane kolize pro podobná data, například při náhodné změně v části vstupní posloupnosti. Cílem je tedy dosáhnout co nejvyšší pravděpodobnosti, že dvě zprávy se stejným hashem jsou stejné.

Hashovací funkce se nejčastěji využívají v hashovacích tabulkách, k rychlému nalezení dat pomocí vyhledávacího klíče (search key). Hashovací funkce se použijí k mapování vyhledávacího klíče do indexu pozice v hashovací tabulce, kde jsou pravděpodobně hledaná data uložena. Obecně, může hashovací funkce mapovat několik rozdílných klíčů na stejnou hashovací hodnotu. Hashovací funkce pouze ukazuje na místo, kde by se mělo začít hledat. Proto každá pozice hashovací tabulky obsahuje soubor záznamů  a ne pouze jeden záznam. Z tohoto důvodu je pozice v hashovací tabulce často nazývána oblast (bucket) a hashovací hodnoty nazývány ukazatele na oblast (bucket indicies).

Algoritmus MD5

MD (Message Digest) tvoří skupinu hashovacích algoritmů navržených profesorem Ronaldem R. Rivestem z Massachusettského institutu technologií. Když byl analytiky vyhlášen hashovací algoritmus MD4 za nedostatečně zabezpečený, byl v roce 1991 navržen algoritmus MD5 jako jeho bezpečná náhrada. MD5 (Message-Digest algorithm 5) byl často využíván v softwaru poskytujícím záruku, že přenášený soubor dorazil nedotčený. Některé souborové servery poskytují už vypočtený hash pro soubory, které si chce uživatel stáhnout a ten je může posléze porovnat s hashem už stažených souborů. Některé operační systémy založené na Unixu, také obsahují algoritmus MD5 pro kontrolu integrity dat. MD5 je popsán v internetovém standardu RFC 1321 a jeho výsledný hash má velikost 128 bitů a je většinou vyjádřen jako 32-znakové šestnáctkové číslo.

Výpočet hashe u MD5 probíhá následujícím způsobem: Na vstupu algoritmu MD5 může být zpráva jakékoliv délky. Vstupní zpráva je rozdělena na 512 bitů velké bloky, tedy 16 slov o velikosti 32 bitů. Zpráva je rozdělena, v bloku, do prvních 448 bitů a zbylých 64 bitů je určeno pro délku původní zprávy. Ke zprávě je přidán 1 bit a zbytek je doplněn o 0 bitů, aby byla velikost bloku 448 bitů bez posledních 64 bitů. Výpočet probíhá tak, že každý blok je počítán samostatně. Pro výpočet jsou použity 4 proměnné (A, B, C, D) jejichž inicializační hodnoty jsou předem stanoveny. Velikost těchto konstant je 32 bitů. Dále jsou definovány 4 pomocné funkce. Každá z těchto funkcí má na vstupu tři 32-bitová slova a jako vystup jedno 32-bitové slovo:

F(X,Y,Z) = (X \wedge Y) \vee (\neg X \wedge Z)

G(X,Y,Z) = (X \wedge Z) \vee (Y \wedge \neg Z)

H(X,Y,Z) = X \oplus Y \oplus Z

I(X,Y,Z) = Y \oplus (X \vee \neg Z)

\oplus, \wedge, \vee, \neg vyjadřují operace XOR, AND, OR a NOT. Každá z těchto funkcí je vykonávána postupně 16krát ve čtyřech kolech. Výsledný hash tvoří proměnné A, B, C ,D, ke kterým je přičtena jejich inicializační hodnota. Vše je znázorněno na následujícím obrázku (zdroj Wikipedia):

MD5

Legenda: MD5 provádí 64 takovýchto operací. Tyto operace jsou seskupeny do čtyř kol o šestnácti operacích. F je nelineární funkce a v každém kole je použita jedna funkce, která je rozdílná pro všechny kola. Mi označuje 32 bitů velký blok vstupní zprávy a Ki označuje 32 bitů velkou konstantu, která je rozdílná pro každou operaci.

Kryptoanalýza MD5

Již v roce 1993 Den Boer a Bosselaers přišli s tím, že našli takzvanou pseudo-kolizi. Dva různé inicializační vektory mají stejný výsledný hash. V roce 1996 oznámil Dobbertin kolizi, ovšem nebyl to útok na celý algoritmus. V březnu roku 2004 vznikl projekt, který chtěl dokázat, že velikost výsledného hashe 128 bitů není dostatečně velká na provedení narozeninového útoku. Tento projekt skončil záhy po 17. srpnu 2004, kdy Wangová a kol. oznámili nalezení kolize pro celý algoritmus MD5. Sdělili, že útok trval pouze hodinu na počítači IBM p690. 1. března 2005 Wangová, Lenstra a de Weger ukázali vytvoření dvou certifikátů X.509 (certifikát pro veřejné klíče) s různými veřejnými klíči a stejným MD5 hashem. O pár dní později Vlastimil Klíma popsal vylepšený algoritmus, který je schopen nalézt kolize během několika hodin na obyčejném notebooku (Acer TravelMate 450LMi, Intel Pentium 1.6 GHz). Během 8 hodin nalezl 331 kolizí prvního bloku a jednu úplnou kolizi MD5. V porovnaní s Wangovou a kol., které trvalo nalezení kolize na prvním bloku jednu hodinu na 25 50krát rychlejším počítači, je jeho metoda ve výsledku asi 1000 2000krát rychlejší než metoda Wangové.

Algoritmus MD5 sice stále lze používat pro kontrolu integrity souborů a pro detekci změny chybou přenosového nebo záznamového média, pro kryptografické účely se však již nehodí. Jeho náhradou jsou algoritmy z rodiny SHA.

Algoritmy SHA

SHA (Secure Hash Algorithm) je skupina pěti kryptografických hashovacích funkcí navržených NSA (Národní bezpečnostní agentura v USA) a vydaných NIST (Národní institut pro standardy v USA) jako celostátní standard v USA (FIPS). Jak již bylo řečeno existuje pět druhů SHA a to: SHA-1, SHA-224, SHA-256, SHA-384 a SHA-512. Poslední čtyři varianty jsou někdy souhrnně označovány jako SHA-2. SHA-1 má výsledný hash délky 160 bitů u dalších verzí odpovídá jejich číslo délce výsledného hashe.

SHA-1

Původní specifikace algoritmu byla vydána v roce 1993 jako Secure hash standard (FIPS PUB 180). Tato verze je označována jako SHA-0 a záhy po vydání byla stažena agenturou NSA, která na ni provedla změnu. Změna se týkala rotace bitů doleva o n pozic a měla přispět k většímu zabezpečení. 17. dubna 1995 byl udělen standard i této verzi označované jako SHA-1 (FIPS PUB 180-1). Algoritmus SHA-1 je založen na principech podobných těm, které použil profesor Ronald R. Rivest z Massachusettského institutu technologií při návrhu algoritmu MD4.

Standard SHA-1 počítá zmenšenou reprezentaci zprávy nebo datového souboru (hash) délky 160 bitů. Výsledný hash může být vstupem pro algoritmus digitálního podpisu (Digital Signature Algorithm DSA), který vytváří nebo ověřuje podpisy zpráv. Podepisováním hashe dosáhneme větší efektivity, protože výsledný hash je většinou mnohem menší než zpráva, ze které byl vypočten. Stejný hashovací algoritmus musí být použit i při ověřování digitálního podpisu. SHA-1 se nazývá bezpečný (secure), protože by mělo být početně nemožné najít zprávu, která odpovídá výslednému hashi, nebo najít dvě různé zprávy, které by produkovaly stejný hash. Jakákoliv změna zprávy při přenosu s velkou pravděpodobností způsobí změnu výsledného hashe, ověřování tedy selže.

SHA-1 může být použito s algoritmem DSA v elektronické poště, u bankovních transakcí, k uchovaní dat a všude tam, kde je vyžadována záruka integrity dat a jejich autentičnost. SHA-1 se také využívá v protokolech TLS, SSL, SSH, IPsec atd. Tvoří také základ pro blokovací šifry SHACKAL.

Výpočet hashe pomocí SHA-1 znázorňuje následující obrázek (zdroj: Wikipedia):

SHA-1

    Zpráva nebo datový soubor je považován za řetězec bitů. Délka zprávy je počet bitů, ze kterých se zpráva skládá. Prázdná zpráva má tedy délku 0 bitů. Zpráva je rozdělena na 512 bitů velké bloky, tedy 16 slov po 32 bitech. Dále jsou data doplněna, aby byla násobkem 64 bitů. Posledních 64 bitů posledního 512 bitů velkého bloku je rezervováno pro délku originální zprávy. Rozdělená zpráva obsahuje 16*n slov, pro n > 0. Takto rozdělená zpráva je považována za posloupnost   o n blocích M1, M2, , Mn , kde každé Mi obsahuje 16 slov.

Posléze je pro každý zpracovávaný blok vytvořena tabulka W a tabulka K, která je pro všechny bloky společná a obsahuje předem dané konstanty. Velikost každé tabulky je 80 řádků. V tabulce W je prvních 16 řádků ekvivalentních datům z bloku (80 slov) a zbytek řádků je dopočítán podle vzorce.

Samotný výpočet probíhá tak, že každý datový blok je počítán samostatně. Pro výpočet je použito 5 proměnných (A, B, C, D, E). Inicializační hodnoty těchto proměnných tvoří konstanty H0 až H4. Tyto proměnné jsou 80krát přepočteny, výsledky jednotlivých bloků jsou sečteny a jsou k nim připočteny původní konstanty H0 až H4. Výsledek tvoří 160-ti bitový řetězec reprezentován pěti slovy. Nákres ukazuje jedno opakování kompresní funkce SHA-1. A až E jsou 32 bitové proměnné. F je nelineární funkce, která se mění. <<<n označuje rotaci bitů doleva o n pozic, n je rozdílné pro každou operaci. Wt označuje rozšířené slovo t-ho opakování, Kt je konstanta   t-ho opakování.

Kryptoanalýza SHA-1

Pro ideální hashovací funkci platí, že nelze najít zprávu, která by byla vzorem k danému hashi. Porušení tohoto pravidla, může být docíleno hrubou silou, vyhledáním 2L výpočtů, kde L je počet bitů hashe. Tento útok se nazývá vzorový (preimage attack). Druhým kritériem je, že nelze najít stejný hash pro dvě rozdílné zprávy. Na toto pravidlo lze zaútočit pomocí narozeninového útoku (birthday attack), který vyžaduje pouze 2L/2 výpočtů. Tento útok je založen na narozeninovém paradoxu, který říká, že pravděpodobnost nalezení páru dvou lidí, kteří mají stejné datum narození, je u skupiny 23 lidí, kteří jsou náhodně vybráni, 50%. U skupiny 57 lidí je to již 99% a dále pravděpodobnost roste až ke 100%. Nalezení takového páru se nazývá kolize. Síla hashovacích funkcí je obvykle porovnávána se symetrickými šiframi jako polovina délky hashe. Tedy síla SHA-1 byla původně odhadována na 80 bitů. Poté, co bylo oznámeno úplné prolomení algoritmu SHA-0 12. června 2004, se objevily pochybnosti odborníků o zavádění SHA-1 do nových kryptografických systémů. Po CRYPTO 2004 (mezinárodní kryptografická konference), kde bylo prolomení SHA-0 zveřejněno, NIST oznámilo, že plánují nahradit SHA-1 algoritmem SHA-2 a jeho variantami do roku 2010. V únoru roku 2005 byl zveřejněn útok vedený Xiaoyun Wang, Yiqun Lisa Yin a Honbo Yu. Jejich útok nalezl kolizi v plné verzi SHA-1 a vyžadoval méně než 269 operací. Na setkání  CRYPTO 2006, Christian Rechberger a Christophe De Canniere prohlásili, že objevili kolizní útok, který dovolí útočníkovi vybrat alespoň část zprávy.

Největším znepokojením u těchto útoků je to, že připravují cestu pro mnohem účinnější útoky. Proto se považuje přechod k silnějším hashovací algoritmům jako rozumný. Některé použití hashovacích algoritmů, jako je uložení hesel, je minimálně ovlivněno kolizními útoky. Konstrukce hesel účtů vyžaduje vzorový útok a přístup k originálnímu hashi, což nemusí být jednoduché. V případě podpisu dokumentů musí útočník vytvořit dvojici dokumentů, jeden neškodný a jeden škodný, a dát neškodný dokument k podepsání držiteli soukromého klíče.

Algoritmy SHA-2 a SHA-3

Tento algoritmus je vylepšením SHA-1, pracuje však na podobném principu. Poskytuje výstup délky 224, 256, 384, nebo 512 bitů. Bezpečnost SHA-1 již byla kompromitována kryptografickými útoky na rozdíl od variant SHA-2, u kterých nebyl doposud zveřejněn úspěšný útok. Jelikož jsou varianty SHA-2 založeny na podobném algoritmu jako SHA-1, je vyvíjen nátlak na vytvoření nových alternativ hashovacích algoritmů. 2. listopadu 2007 byla vyhlášena otevřená soutěž na vývoj nového algoritmu SHA-3. Vyhlášení vítězů a publikace nového standardu je plánována na rok 2012. Jedná se o podobnou veřejnou soutěž, kterou vyhlásil NIST pro standard AES (Advanced Encryption Standard).