Funkce

Hashovací  funkce

bullet

Hash je většinou mnohem kratší než celkový dokument.

Výhodou šifrování hashe místo celého dokumentu je čitelnost dokumentu i bez klíče a vyšší rychlost šifrování a dešifrování, která dovoluje použití složitějších (a tedy bezpečnějších) šifrovacích algoritmů.

bullet

Reprodukovatelná metoda pro převod vstupních dat do (relativně) malého čísla, které vytváří jejich jednoznačnou charakteristiku a je velmi obtížné najít taková data, která vyhovují požadovanému otisku (tzv. jednocestná funkce).

bullet

Výstup hašovací funkce označujeme jako výtah,miniatura, otisk, fingerprint či hash (česky též někdyjako haš). Funkce je důležitou součástí kryptografických systémů pro digitální podpisy a často se též používá prokontrolu integrity dat, k rychlému porovnání dvojicezpráv, indexování, vyhledávání apod.

Mezi hlavní vlastnosti této funkce patří:

bullet

jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk)

bullet

malou změnou vstupních dat dosáhneme velkou změnu na výstupu (tj. výsledný otisk se odpůvodního zásadně na první pohled liší)

bullet

 vysoká pravděpodobnost, že dvě zprávy se stejným hašem jsou stejné

bullet

vysoká obtížnost nalezení vstupu, který odpovídá požadovanému haši (výstupu), viz jednocestná funkce.

bullet

Hašovací funkce je funkce h, která má přinejmenším tyto vlastnosti:

bullet

je kompresní (není zde ale tento pojem míněn vběžném matematickém smyslu) - provádí mapování argumentu (vstupu) x libovolné bitové délky na hodnotu h(x) (výstup), která mápevně určenou bitovou délku, je snadno vypočitatelná - pro dané h a argument x je snadné vypočítat h(x).

bullet

Formálně jde o funkci h, která převádí vstupní posloupnost bitů (či bytů) na posloupnost pevné délky n bitů. kde |D| > |R|.

bullet

Z definice plyne existence kolizí, to znamená dvojic

bullet

vstupních dat (x,y), xy, takových, že h(x) = h(y), tj. dvojice různých vstupních dat může mít stejný otisk. Kolize jsou nežádoucí, ale v principu se jim nelze vyhnout, protože počet možných různých vstupních zpráv je nekonečný a počet různých otisků je omezený (limitovaný, konečný, menší). Vhodnou volbou funkce lze snížit pravděpodobnost, že nastane kolize pro podobná data (např. při náhodné změně v části vstupní posloupnosti) a maximalizovat obtížnost nalezení inverzí funkce. Cílem je dosáhnout co nejvyšší pravděpodobnosti, že dvě zprávy se stejným hashem (hešem) jsou stejné.

bullet

Z hlediska bezpečnosti je nutno přidat řadu dalších vlastností. Nejdůležitější je následující trojice vlastností, která určuje obtížnost napadení hašovací funkce. Obtížností se v tomto kontextu myslí výpočetní složitost, která by měla být za současných technologických možností (které se ovšem v čase mění) mimo možnosti reálného použití:

bullet

Odolnost vůči získání předlohy. Pro daný otisk c je obtížné spočítat x takové, že

bullet

h(x) = c (hašovací funkce je jednosměrná.)

bullet

Odolnost vůči získání jiné předlohy. Pro daný vstup x jeobtížné spočítat y takové, že h(x) = h(y).

bullet

Odolnost vůči nalezení kolize. Je obtížné systematicky najít dvojici vstupů (x,y), pro které h(x) = h(y).

Hash

bullet

Další obvyklé požadavky zahrnují:

bullet

Nekorelovatelnost vstupních a výstupních bitů, kvůli znemožnění statistické krypto analýzy.

bullet

Odolnost vůči skoro-kolizím. Je obtížné nalézt x a y taková, že h(x) a h(y) se liší jen v malém počtu bitů.

bullet

Lokální odolnost vůči získání předlohy. Je obtížné najít i jen část vstupu x ze znalosti h(x).

bullet

Odolnost argumentu (preimage resistance) - pro, v podstatě, všechny výstupy je výpočtově neschůdné nalézt jakýkoliv vstup, který hašuje na daný výstup; tj. nalézt jakýkoliv argument x takový, že h(x) = y pro danou hodnotu y, pro niž odpovídající vstup není předem znám.

bullet

Odolnost druhého argumentu (2nd-preimage resistance) – je výpočtově neschůdné nalézt jakýkoliv shodný výstup jako jakýkoliv určený první vstup; tj. pro dané x nelze nalézt druhý argument x’ x, přičemž platí h(x) = h(x’) = y.

bullet

Odolnost druhého argumentu (též „slabá odolnost proti kolizím“).

bullet

Odolnost proti kolizím (collision resistance) – je výpočtově neschůdné nalézt jakékoliv dva rozdílné vstupy x a x’, které hašují na shodný výstup; tj. x’ x takové, že h(x) = h(x’) = y (volný výběr obou vstupů).

bullet

Ideální kryptografická hašovací funkce má všechny tři uvedené vlastnosti. Pokud je velikost množiny definičního oboru hašovací funkce větší než oboru hodnot (což bývá v praxi vždy), hašovací funkce nemůže být bezkolizní. Definice obsahují obraty „výpočtově neschůdné“ - kolize nesmí být možné nalézt.

bullet

Kontext definice se mění jak rozvojem technologie, tak požadovanou mírou ekonomických nákladů. V poslední době řada útoků na hašovací funkce byla úspěšná, a to vede k rozvoji nových algoritmů.