Hašovacia funkcia

z Wikipédie, slobodnej encyklopédie

Hašovacia funkcia je funkcia, predpis pre transformáciu ľubovoľne dlhého vstupu na fixne dlhý, výrazne kratší výstup. Pre rovnaký vstup zakaždým rovnaký výstup. Vstupom je ľubovoľný tok dát, ktorý je však konečný. Výstup má fixnú dĺžku, pár desiatok bitov. Tento reťazec sa označuje ako haš (angl. hash), charakteristika, odtlačok. Dĺžka hašu je závislá od zvolenej hašovacej funkcie.

Táto transformácia, zobrazenie väčšej množiny vstupov x, do menšej množiny výsupov 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í.

Kryptoanalytické skúmanie hašovacích funkcií súvisí s hľadaním konkrétnych kolízii. Odhalenie metódy rýchleho hľadania kolízii, napríklad na bežne dostupnom výpočtovom vybavení, rapídne degraduje bezpečnosť hašovacej funkcie.

Obsah 1 Vlastnosti 1.1 Hašovacie funkcie 1.2 Kryptografické hašovacie funkcie 2 Implementácie a príklady 2.1 Bežné hašovacie funkcie 2.2 Kryptografické hašovacie funkcie 2.3 Kľúčované hašovacie funkcie 2.4 Príklady 3 Použitie 4 Poznámky 5 Referencie 6 Externé odkazy

[upraviť] Vlastnosti

[upraviť] Hašovacie funkcie

Bežné hašovacie funkcie (nedajú sa 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.

[upraviť] Kryptografické hašovacie funkcie

Hašovacie funkcie používané v kryptológii by mali navyše spĺňať ^[1]:

• Jednocestnosť - funkcia musí byť jednocestná, tj. inverznú funkciu ťažko nájsť. Teda iba znalosť výstupu nijak nevedie k znalosti vstupného textu. Pre dané x ľahko spočítať H(x), pre dané H(y) ťažko spočítať y.
• Silná bezkolíznosť - ak nie je možné v rozumnom čase nájsť akýkoľvek pár vstupov tak, aby nastala kolízia. Nájsť ľubovoľné x1, x2, aby platilo H(x1) = H(x2).
• Slabá bezkolíznosť - ak nie je možné v rozumnom čase k danému vstupu nájsť vstup iný tak, aby nastala kolízia. Pre dané x1 nájsť také x2, x1 ≠ x2, aby platilo H(x1) = H(x2).

[upraviť] Implementácie a príklady

[upraviť] Bežné hašovacie funkcie

Predstavujú jednu z implementácii výpočtu kontrolného súčtu.

[upraviť] Kryptografické hašovacie funkcie

• MD - Message-Digest algorithm
• SHA - Secure Hash Algorithm
• RIPEMD - RACE Integrity Primitives Evaluation Message Digest

a ďalšie, ktoré nie sú často používané Whirlpool, HAVAL, PANAMA, Tiger

[upraviť] Kľúčované hašovacie funkcie

Použitie hašovacej funkcie s tajným kľúčom, napríklad HMAC.

[upraviť] Príklady

Príklady hašov niektorých hašovacích funkcií z krátkeho textového reťazca. Malá zmena vstupu skutočne spôsobí lavínovité zmeny vo výstupe:

vstup:     Prehlasujem, že ti dlžím 100
výstup: 
 MD5       fbe8e3408311811c0d182d0193a03a62
 SHA-1     68741d0244e8ce0989af154977ce037c7c75a32e
 SHA-256   da3292bf01f1a5a37ffd1c8650430c3a65766205bad2faac1e1a7ab1d23ccc88
 RIPEMD160 01b5e2da3697a5759d7848e697b1415aeb6e082d
 CRC32     46b88aaa

vstup:     Prehlasujem, že ti dlžím 900
výstup: 
 MD5       42e4bf834247c94795911ef86b8817e3
 SHA-1     6f6baee4bf87762435f0e245a94c478cbf3d97df
 SHA-256   bfbcd7dbd3ff2b8f6b59142ad352136d70e53ec13c1b263dae685ca3fb46ded5
 RIPEMD160 41392a069ce0a3b58062bbf66f9f528502d3c046
 CRC32     48abdb12

[upraviť] Použitie

Hašovacie funkcie majú rozmanité použitie nielen v informatike. Uvedený pojem charakteristika je možné plne nahradiť pojmom haš. 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 ^[2].
• Podpisovanie dát - overenie integrity a autentifikácie dát, súvisí s elektronickým podpisom a asymetrickými šiframi.

[upraviť] Poznámky

1. ↑ Podrobne o kryptografických hašovacích funkciách píše kapitola Hašovacie funkcie a overenie integrity z referenčnej Handbook of Applied Cryptography
2. ↑ 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

[upraviť] 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.

[upraviť] Externé odkazy

• Útok pomocou rainbowtables - princíp, schémy, postupy ako previesť útok na bezpečné ukladanie hesiel pomocou hašov práve predpripravenými tabuľkami s hašmi
• HashCalc - 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