Kryptografická hash funkce

Kryptografické hashovací funkce (anglicky hash function, česky někdy též hašovací funkce), jsou speciálním typem funkcí. Jejich účelem je vytvořit otisk pro daný vstup tak, že určit ze znalosti výstupu zpětně vstup je téměř nemožné (představují jednocestné funkce). Navíc splňují i vlastnost, že i minimální změna ve vstupu funkce zásadním způsobem mění hodnotu výstupu. V praxi například počítáme hash nějakého dokumentu, kterou můžeme zaslat nezabezpečeným kanálem. Pokud útočník zná tuto hodnotu, není schopen rychle vytvořit dokument, který by dával stejnou hash hodnotu (této skutečnosti se využívá například při digitálních podpisech dokumentů).

Pro hashovací funkci h tedy obecně platí:

1. Je extrémně obtížné získat předlohu. To znamená, že máme-li pouze hodnotu c, kde c = h(x), je extrémně obtížné zjistit hodnotu x (tj. zabere to značné množství času, například miliardy let i na relativně výkonných strojích).

2. Je odolná vůči získání jiné předlohy. Pokud známe hodnotu x, je extrémně obtížné získat jinou hodnotu y, pro kterou by platilo h(x) = h(y).

3. Je odolná vůči nalezení kolize. Je obtížné najít alespoň nějaké hodnoty x a y, pro které se h(x) = h(y).

Hodnoty hash funkcí se využívají například ke kontrole integrity souborů – pokud přenášíme po síti soubory, může se stát, že vlivem šumu dojde k jejich zdánlivě nepatrnému poškození. To však vyvolá zásadní změnu hash hodnoty u souboru, tudíž při kontrole integrity bezpečně detekujeme chybu. Další místo, kde se hash funkce frekventovaně využívají je ukládání hesel. Pokud například v operačním systému Linux uživatel zadává heslo, ve skutečnost se neuchovává jeho podoba v podobě otevřeného textu (symbolů hesla), ale právě hash hodnota tohoto hesla. Tím je zajištěna bezpečnost, pokud se ztratí databáze hesel, ve skutečnosti útočník nezná jejich přesné znění (tedy musí hledat z obrazu hash funkce zpátky její vzor, což je obtížné). Pokud máte operační systém Linux, můžete si takto zabezpečená hesla prohlédnout příkazem sudo cat /etc/shadow .

Obecně pro hashovací funkce uvažujeme vstup libovolné délky n bitů. Výstup má však fixní délku k bitů (pro MD5 například k = 128 bitů).

Téma také úzce souvisí s existencí tzv. jednocestné funkce (též nazývané jednosměrné). To je taková funkce, jenž lze snadno vyčíslit (tj. najít obraz = funkční hodnotu), ale opačný krok, tedy najít z obrazu (funkční hodnoty) zpátky vzor lze jen velmi obtížně a to především kvůli velkému množství možných variant. V současné době není matematicky dokázáno, že by taková funkce existovala, pokud by se ji podařilo najít, byl by mimo jiné vyřešen tzv. P vs NP problém (což je důležitý problém matematiky).

Základní hash funkce