Hašovací funkce

Z Wikipedie, otevřené encyklopedie

Hašovací funkce je předpis pro výpočet kontrolního součtu (haše) ze zprávy či většího množství dat. 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. Formálně je to funkce 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). 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 vysoká pravděpodobnost, že dvě zprávy se stejným kontrolním součtem jsou stejné.

Obsah

[editovat] Požadavky na hašovací funkci

Nejdůležitější je následující trojice vlastností. Obtížností se v tomto kontextu myslí výpočetní složitost.

  1. Odolnost vůči získání předlohy. Pro daný haš c je obtížné spočítat x takové, že h(x)=c. (Hašovací 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).

[editovat] Známé hašovací funkce

  • MD5 – oblíbená, ale již kompromitovaná funkce. Od srpna 2004 je veřejně znám postup pro nalezení kolizního páru zpráv. [1]
  • 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 hašovacích funkcí (SHA-256, SHA-384, SHA-512 a SHA-224), které jsou součástí standardu FIPS 180-2 [2], a u kterých dosud nebyly nalezeny žádné bezpečnostní slabiny.

[editovat] Podívejte se také

[editovat] Externí odkazy

[editovat] Reference