Funkce
Hashovací funkce
Při vytváření hashe pro šifrovací účely se používají takové algoritmy, že je prakticky vyloučené změnit dokument takovým způsobem, aby se současně nezměnil jeho hash. Příkladem jednoduchého hashe (pro kryptografii nepoužitelného) je kontrolní součet řady čísel, používaný pro ověření, že při jejich přepisování nedošlo k chybě.
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ů. | |
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). | |
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ří:
jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk) | |
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ší) | |
vysoká pravděpodobnost, že dvě zprávy se stejným hašem jsou stejné | |
vysoká obtížnost nalezení vstupu, který odpovídá požadovanému haši (výstupu), viz jednocestná funkce. | |
Hašovací funkce je funkce h, která má přinejmenším tyto vlastnosti: | |
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). | |
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|. | |
Z definice plyne existence kolizí, to znamená dvojic | |
vstupních dat (x,y), x≠y, 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é. |
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í: | |
Odolnost vůči získání předlohy. Pro daný otisk c je obtížné spočítat x takové, že | |
h(x) = c (hašovací funkce je jednosměrná.) | |
Odolnost vůči získání jiné předlohy. Pro daný vstup x jeobtížné spočítat y takové, že h(x) = h(y). | |
Odolnost vůči nalezení kolize. Je obtížné systematicky najít dvojici vstupů (x,y), pro které h(x) = h(y). |
Hash
Další obvyklé požadavky zahrnují: | |
Nekorelovatelnost vstupních a výstupních bitů, kvůli znemožnění statistické krypto analýzy. | |
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ů. | |
Lokální odolnost vůči získání předlohy. Je obtížné najít i jen část vstupu x ze znalosti h(x). | |
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. | |
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. | |
Odolnost druhého argumentu (též „slabá odolnost proti kolizím“). | |
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ů). | |
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. | |
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ů. |