Jde o jedno ze základních primitiv moderní kryptografie. Kryptografické hashovací funkce je druh hashovací funkce, která má navíc určité vlastnosti. Těmi jsou především jednosměrnost a bezkoliznost a v ideálním případě se chová jako náhodné orákulum.
Náhodné orákulum
Hash nejde snadno uhádnout a působí jako náhodný výběr prvku z obrovské množiny hodnot. Při každém zavolání se chová algoritmicky a deterministicky a vždy dostaneme stejný výstup, avšak změna byť jednoho bitu na vstupu bude mít za následek absolutně odlišnou hodnotu hashe.
Z definice hashe plyne existence kolizí. Pokud je velikost množiny X je větší než velikost množiny obor hodnot Y, který jak víme je konečně dlouhý - pak dle podle principu holubníku musí existovat kolize.
Jednosměrná funkce (one-way)
Pro asymetrickou kryptografii a hashovací funkci je důležitým prvkem jednosměrná funkce.
Oproti asymetrickému šifrování, se využívá u hashů typ jednosměrné funkce, která nejde invertovat např. pomocí klíče. V současnosti jsou jednosměrné funkce postaveny jen na víře, že lidé nebudou umět invertovat takovou složitou funkci. Není vůbec vhodné hashe používat na šifrování (existují duhové tabulky).
To, co je výpočetně možné se mění spolu s tím, jak roste výkon počítačů. S dobou se mění doporučení toho, která hashovací funkce je bezpečná. Když víme jak vzory funkce, nebo kolize nalézat jednodušeji, než útokem hrubou silou hovoříme o prolomení hašovací funkce.
Kolize
Vlastnost odolnosti vůči kolizím je důležitá pro digitální podpisy, kde tato vlastnost zaručuje jedinečnost ověření pro autoritu. Dalším z příkladů jsou proof-of-work systémy, které používají vlastnost bezkoliznosti k vyjádření množství provedené výpočetní práce. Bezkoliznost v neposlední řadě poskytuje identitu, že není možné nalézt dva dokumenty (nebo objekty, struktury, textové řetězce) se stejnou hashí.
Bezkoliznost
Uvádí se pod názvem Pre-Image Resistance
K zadané hodnotě hashe y := h(m), je výpočetně nemožné nalézt vzor m, pro který platí y = h(m).
Odolnost proti nalezení druhého vzoru
V literetuře tato vlastnost známá jako pod pojmy Second Pre-Image Resistance, Weak collision resistence.
Pro vzor m1 nalézáme druhý vzor m1, pro který platí m1 ≠ m2 dávající stejný obraz h(m1) = h(m2).
Pro kryptografickou hashovací funkci by neměl být znám žádný algoritmus, který by zvládl najít m2 efektivněji než útokem hrubou silou tzn. složitost nalezení vzoru je ≈ 2n.
Odolnost proti nalezení kolize
Vlastnost se nazívá Collision Resistance, Colision Free
Nalezneme dvojici různých vstupů m1 a m2 mající stejný obraz h(m1) = h(m2).
V případě nalezení kolize dvou obrazů nás může klamat intuice. Narozeninový paradox vyvozuje, že pro n-bitovou hašovací funkci nastává kolize dvou zpráv s cca 50% pravděpodobností, namísto očekávaných 2n−1.