Hašovacia funkcia

Hašovacia funkcia je funkcia (predpis) pre prevod vstupného reťazca dát na krátky výstupný reťazec. Tento reťazec sa označuje ako haš (angl. hash), charakteristika, odtlačok vstupných dát. Dĺžka hašu je závislá od zvolenej hašovacej funkcie, má fixnú dĺžku pár desiatok bitov.

Hašovacie funkcie sa využívajú napríklad na zrýchlenie vyhľadávania.

Vlastnosti

Hašovacia funkcia vytvára pre rovnaký vstup zakaždým rovnaký výstup. Vstupom hašovacej funkcie môže byť ľubovoľný tok dát, ktorý je však konečný alebo zarovnaný (angl. padded) na určitú dĺžku, ktorú funkcia spracuje. Výstup má fixnú dĺžku.

Toto zobrazenie väčšej množiny vstupov $x$ , do menšej množiny výstupov $H(x)$ nie je prosté. Preto určite existujú dva rôzne vstupy, ktoré dávajú rovnaký výstup. Týmto konkrétnym rôznym dátam sa hovorí kolízie hašovacích funkcií.

Bežné hašovacie funkcie, ktoré nemožno považovať za bezpečné by mali spĺňať:

Rýchlosť transformácie – funkcia rýchlo spočíta zo vstupu $x$ výstup $H(x)$ .
Rozloženie výstupov – funkcia musí distribuovať výstupy rovnomerne v celom obore hodnôt, teda produkuje málo kolízii.
Lavínovitosť – vytvorený hash musí natoľko závisieť na každom bite vstupu, že aj jeho malá zmena rapídne ovplyvní výstup.

Kryptografická hašovacia funkcia musí vyhovovať ďalším kritériam.

Soľ (Salt)

Niektoré funkcie pridávajú pri hashovaní do pôvodného reťazca aj náhodne vygenerovaný reťazec znakov. Tým sa docieľuje vyššia bezpečnosť.

Použitie

Hašovacie funkcie majú rozmanité použitie nielen v informatike. Niektoré z použití:

Indexovanie – transformácia kľúča, teda zhrnutie vlastností určitých dát na ich charakteristiku.
Rýchle vyhľadávanie – vytváranie tabuliek charakteristík k veľkému množstvu dát.
Rýchle overenie dát – overenie integrity dát, ide o implementáciu kontrolného súčtu.

Bezpečné ukladanie hesiel – uloženie hesla len v podobe jeho charakteristiky.^{[pozn 1]}

Pozri aj

Poznámky

↑ Bezpečné ukladanie hesiel pomocou hašov sa používa v OS Linux. Pri overovaní hesla sa zakaždým vypočíta jeho haš a len ten sa overí s autorizačnou databázou hesiel, heslá nie sú nikde uložené. Možnému útoku na databázu hesiel dopredu pripravenými tabuľkami hašov zabraňuje tzv. solenie hesiel. Soľ predstavuje náhodnú, OS známu hodnotu, ktorá sa pred výpočtom hašu pridá k heslu, a tak znemožní uvedený útok dopredu pripravenou tabuľkou hašov, tzv. útok pomocou rainbow tables

Referencie

KMENT, V. Hašovací funkce: Jak se odolává hackerům [online]. Lupa.cz, 2005 [cit. 2008-12-31]. ISSN 1213-0702.
MENEZES, A. - van OORSCHOT, P. - VANSTONE, S. Handbook of Applied Cryptography. CRC Press, 1996. 816 str. ISBN 0-8493-8523-7.

Externé odkazy

HashCalc Archivované 2008-01-11 na Wayback Machine - freeware nástroj na výpočet viacerých hašovacích funkcií
Crypto-world - detailný článok o rôznych hašovacích funkciách v elektronickom magazíne o kryptológii

[1] Bezpečné ukladanie hesiel pomocou hašov sa používa v OS Linux. Pri overovaní hesla sa zakaždým vypočíta jeho haš a len ten sa overí s autorizačnou databázou hesiel, heslá nie sú nikde uložené. Možnému útoku na databázu hesiel dopredu pripravenými tabuľkami hašov zabraňuje tzv. solenie hesiel. Soľ predstavuje náhodnú, OS známu hodnotu, ktorá sa pred výpočtom hašu pridá k heslu, a tak znemožní uvedený útok dopredu pripravenou tabuľkou hašov, tzv. útok pomocou rainbow tables

[pozn 1]