Kryptografická hašovací funkce

Hashovací funkce je reprodukovatelná metoda pro převod vstupních dat do (relativně) malého čísla, které vytváří jejich otisk (můžeme ho označit jako charakteristika dat). Výsledný otisk se označuje také jako výtah, miniatura, fingerprint či hash (česky též někdy jako haš). Funkce může sloužit ke kontrole integrity dat, k rychlému porovnání dvojice zpráv, indexování, vyhledávání apod. Je důležitou součástí kryptografických systémů pro digitální podpisy.

Výsledný otisk se často nesprávně označuje jako kontrolní součet.

Vlastnosti

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

1. jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk)
2. malou změnou vstupních dat dosáhneme velkou změnu na výstupu (tj. výsledný otisk se od původního zásadně na první pohled liší)
3. vysoká pravděpodobnost, že dvě zprávy se stejným kontrolním součtem jsou stejné

Popis

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

$h:D\rightarrow R\,,$

kde |D|>|R|.

Z definice plyne existence kolizí, to znamená dvojic 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ý otisk. Kolize jsou nežádoucí, ale v principu se jim nelze úplně vyhnout. 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 kontrolním součtem jsou stejné.

Bezpečnost

Nejdůležitější je následující trojice vlastností, která určuje obtížnost napadení hashovací 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í mimo možnosti reálného použití:

1. Odolnost vůči získání předlohy. Pro daný hash c je obtížné spočítat x takové, že h(x)=c (hashovací funkce je jednosměrná.)
2. Odolnost vůči získání jiné předlohy. Pro daný vstup x je obtížné spočítat y takové, že h(x)=h(y).
3. Odolnost vůči nalezení kolize. Je obtížné systematicky najít dvojici vstupů (x,y), pro které h(x)=h(y).

Další obvyklé požadavky zahrnují:

• Nekorelovatelnost vstupních a výstupních bitů, kvůli znemožnění statistické kryptoanalý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).

Známé hashovací funkce

• Message-Digest algorithm – oblíbená MD5, ale již kompromitovaná funkce. Od srpna 2004 je veřejně znám postup pro nalezení kolizního páru zpráv.
• Secure Hash Algorithm (SHA):
  • SHA-1 – oblíbená, ale již kompromitovaná funkce. V únoru 2005 byl zveřejněn objev algoritmu, který umožňuje nalézt kolizi podstatně rychleji než hrubou silou. Výpočetní náročnost je ale stále mimo současnou techniku.
  • SHA-2 – rodina 4 hashovacích funkcí (SHA-256, SHA-384, SHA-512 a SHA-224), které jsou součástí standardu FIPS 180-2, a u kterých dosud nebyly nalezeny žádné bezpečnostní slabiny.
• Tiger (hash) – funkce z roku 1995, používána v peer-to-peer aplikacích

Podívejte se také

• Cyklický redundantní součet (CRC)
• Kontrolní součet

Externí odkazy

• http://www.lupa.cz/clanek.php3?show=4090 – úvod do hashovacích funkcí
• Kryptografická hašovací funkce v encyklopedii MathWorld (anglicky)