Co je hashování?
Domů
Články
Co je hashování?

Co je hashování?

Středně pokročilí
Zveřejněno Jul 29, 2019Aktualizováno Jan 31, 2023
7m

Pojmem „hashování“ se označuje vytváření výstupů s pevnou velikostí ze vstupů s velikostí proměnlivou. Používají se přitom matematické vzorce známé jako hashovací funkce (které jsou realizovány jako hashovací algoritmy). 

Ačkoliv ne všechny hashovací funkce využívají kryptografické postupy, tzv. kryptografické hashovací funkce jsou ústřední vlastností všech kryptoměn. Blockchainy a další distribuované systémy jsou díky nim schopny dosahovat vysoké míry integrity a zabezpečení dat.

Tradiční i kryptografické hashovací funkce jsou deterministické, což znamená, že jestliže se vstup hashovacího algoritmu nezmění, zůstane beze změny i jeho výstup (jinak též „digest“ nebo „hash“).

Hashovací algoritmy kryptoměn bývají obvykle navrženy jako jednosměrné funkce, což znamená, že jejich inverzní funkci lze vypočíst pouze s využitím obrovského množství výpočetního času a zdrojů. Jinými slovy výstup je možné z daného vstupu nalézt poměrně snadno, avšak opačný postup (tedy vygenerování vstupu pouze na základě výstupu) představuje relativně složitý úkol. Obecně platí, že čím náročnější je nalézt vstup hashovacího algoritmu, tím vyšší bývá jeho bezpečnost.


Jak hashovací funkce funguje?

Různé hashovací funkce vyprodukují výstupy s různou velikostí, ale velikost možných výstupů daného hashovacího algoritmu zůstává neměnná. Např. algoritmus SHA-256 může vyprodukovat pouze výstupy o velikosti 256 bitů a algoritmus SHA-1 vygeneruje vždy pouze 160bitové digesty.

Pro ilustraci můžeme do hashovacího algoritmu SHA-256 (využívaného u Bitcoinu) vložit slova „Binance“ a „binance“.

SHA-256

Vstup

Výstup (256 bitů)

Binance

f1624fcc63b615ac0e95daf9ab78434ec2e8ffe402144dc631b055f711225191

binance

59bba357145ca539dcd1ac957abc1ec5833319ddcae7f5e8b5da0c36624784b2


Všimněte si, že drobná změna (velikost prvního písmena) vedla k naprosto odlišné hodnotě hashe. Jelikož však používáme algoritmus SHA-256, výstup bude mít vždy bez ohledu na velikost vstupu pevnou velikost, tj. 256 bitů (neboli 64 znaků). Nezáleží ani na tom, kolikrát daná dvě slova do algoritmu vložíme, oba výstupy budou vždy stejné.

Obdobně vložíme-li tytéž vstupy do hashovacího algoritmu SHA-1, získáme následující výsledky:

SHA-1

Vstup

Výstup (160 bitů)

Binance

7f0dc9146570c608ac9d6e0d11f8d409a1ee6ed1

binance

e58605c14a76ff98679322cca0eae7b3c4e08936


SHA je zkratka pro Secure Hash Algorithms neboli bezpečné hashovací algoritmy. Používá se k označení kryptografických hashovacích funkcí zahrnujících algoritmy SHA-0 a SHA-1, ale i skupiny SHA-2 a SHA-3. Algoritmus SHA-256 patří společně s algoritmem SHA-512 a dalšími do skupiny SHA-2. V současnosti jsou za bezpečné považovány pouze skupiny SHA-2 a SHA-3.


Proč jsou důležité?

Běžné hashovací funkce nabízejí širokou řadu použití, mimo jiné vyhledávání v databázích, analýzu objemných souborů či správu dat. Kryptografické hashovací funkce se kromě toho často používají v aplikacích zaměřených na zabezpečení informací, např. ověřování zpráv či vytváření digitálních otisků prstů. Kryptografické hashovací funkce jsou zásadní při těžbě Bitcoinu a hrají roli i při vytváření nových adres a klíčů.

Skutečná síla hashování se projevuje při zpracovávání obrovských množství informací. Hashovací funkci lze například použít na velký soubor nebo dataset a její výstup použít k rychlému ověření přesnosti a integrity dat. Takové využití je možné díky deterministické povaze hashovacích funkcí – vstup se vždy přetaví ve zjednodušený, zhuštěný výstup (hash). Díky této technice odpadá potřeba skladovat a „pamatovat si“ velké objemy dat.

Hashování nachází užitek zejména v kontextu blockchainové technologie. Využívá se při několika operacích na bitcoinovém blockchainu, většinou při těžbě této kryptoměny. Ve skutečnosti se o hashování opírají téměř všechny kryptoměnové protokoly, a to při slučování a spojování skupin transakcí do bloků či vytváření kryptografických propojení mezi bloky, čímž vzniká samotný blockchain.


Kryptografické hashovací funkce

Zopakujme, že hashovací funkce využívající kryptografické postupy lze označit za kryptografické hashovací funkce. Obecně platí, že k prolomení kryptografické hashovací funkce je zapotřebí ohromné množství pokusů využívajících hrubou sílu. K „obrácení chodu“ kryptografické hashovací funkce by člověk musel náhodně zkoušet vkládat vstupy, dokud by nezískal kýžený výstup. Zároveň je také možné z několika různých vstupů získat tentýž výstup, v takovém případě hovoříme o „kolizi“.

Aby byla kryptografická hashovací funkce považována za skutečně bezpečnou, musí z technického hlediska splňovat tři vlastnosti. Můžeme je popsat jako odolnost vůči kolizi, odolnost vůči nalezení vzoru a odolnost vůči nalezení druhého vzoru.

Než se na jednotlivé vlastnosti podíváme podrobně, podívejme se na jejich stručné shrnutí.

  • Odolnost vůči kolizi: nelze nalézt dva rozdílné vstupy, které by jako výstup vygenerovaly tentýž hash.

  • Odolnost vůči nalezení vzoru: u hashovací funkce nelze „obrátit chod“ (tj. na základě daného výstupu nalézt vstup).

  • Odolnost vůči nalezení druhého vzoru: nelze nalézt druhý vstup, který by kolidoval s daným vstupem.


Odolnost vůči kolizi

Jak jsme uvedli, ke kolizi dochází, když dva různé vstupy vyprodukují tentýž hash. Hashovací funkce je tedy považována za odolnou vůči kolizi do chvíle, než někdo kolizi odhalí. Upozorňujeme, že ke kolizi může dojít u jakékoliv hashovací funkce, protože počet možných vstupů je nekonečný, ale počet výstupů konečný.

Jinými slovy, hashovací funkce je odolná vůči kolizi, dokud je možnost nalezení kolize tak malá, že by to vyžadovalo miliony let výpočtů. Přestože bezkolizní hashovací funkce neexistují, některé jsou dostatečně silné na to, aby se daly považovat za odolné vůči kolizi (např. SHA-256).

Skupiny algoritmů SHA-0 a SHA-1 již nejsou považovány za bezpečné, protože u nich byly nalezeny kolize. V současnosti jsou za bezpečné považovány skupiny SHA-2 a SHA-3.


Odolnost vůči nalezení vzoru

Odolnost vůči nalezení vzoru souvisí s konceptem jednosměrných funkcí. Hashovací funkce se považuje za odolnou vůči nalezení vzoru tehdy, existuje-li velmi nízká pravděpodobnost, že někdo dokáže nalézt vstup, na jehož základě byl vygenerován konkrétní výstup.

Upozorňujeme, že tato vlastnost se od předchozí liší, protože u ní by se útočník snažil odhadnout vstup tak, že by se podíval daný výstup. Oproti tomu ke kolizi dochází v případě, že někdo nalezne dva různé vstupy, které vygenerují tentýž výstup, ale na použitých vstupech nesejde.

Odolnost vůči nalezení vzoru je cenná při ochraně dat, protože autenticitu zprávy je možné dokázat pomocí jejího jednoduchého hashe, není tedy nutné informace zveřejňovat. Mnoho poskytovatelů služeb a webových aplikací v praxi místo prostého textu hesel uchovává a využívá hashe vygenerované na jejich základě.


Odolnost vůči nalezení druhého vzoru

Zjednodušeně lze říci, že odolnost vůči nalezení druhého vzoru leží někde mezi výše uvedenými vlastnostmi. K útoku nalezením druhého vzoru dochází tehdy, když je útočník schopen nalézt konkrétní vstup, který vygeneruje stejný výstup, jako u již známého vstupu.

Jinými slovy při útoku druhým vzorem se hledá kolize, ale namísto hledání dvou náhodných vstupů, které vygenerují tentýž hash, útočníci hledají vstup, který vygeneruje tentýž hash, který lze získat pomocí jiného konkrétního vstupu.

Proto je každá hashovací funkce, která je odolná vůči kolizím, zároveň odolná vůči útokům nalezením druhého vzoru, protože tento druhý útok vždy vyžaduje existenci kolize. Nicméně útok nalezením vzoru lze provést i u funkce odolné vůči kolizi, protože je k němu potřeba nalezení jednoho vstupu na základě jednoho výstupu.


Těžba

Hashovací funkce se využívají v mnoha krocích těžby Bitcoinu, např. při kontrole zůstatků, párování vstupů a výstupů transakcí a u hashovacích transakcí v rámci jednoho bloku tvořícího Merkleův strom. Avšak jeden z hlavních důvodů, proč je bitcoinový blockchain bezpečný, spočívá v tom, že těžaři musí před nalezením platného řešení dalšího bloku provést obrovské množství hashovacích operací.

Konkrétně musí těžař při tvorbě hashovací hodnoty kandidátského bloku vyzkoušet mnoho různých vstupů. V zásadě budou schopni blok zvalidovat pouze v případě, že vygenerují výstupní hash začínající určitým počtem nul. Počet nul je ukazatelem náročnosti těžby a mění se podle hashratu dostupného na síti.

V našem případě představuje hashrate výpočetní sílu využívanou k těžbě Bitcoinu. Pokud se hashrate na síti zvýší, bitcoinový protokol automaticky upraví náročnost těžby tak, aby se průměrná doba nutná k vytěžení bloku i nadále pohybovala kolem 10 minut. Naopak rozhodne-li se několik těžařů s těžbou přestat, hashrate výrazně klesne a náročnost těžby se sníží (na úroveň, kdy se průměrná doba těžby bloku vrátí na 10 minut).

Těžaři nemusí hledat kolize, protože za platný výstup lze považovat vícero vygenerovaných hashů (podmínkou je daný počet nul na začátku). U jednoho bloku tedy existuje několik řešení a těžaři musí nalézt pouze jedno z nich, které musí být v souladu s prahem stanoveným náročností těžby. 

Vzhledem k tomu, že těžba Bitcoinu je činnost nákladově náročná, těžaři nemají motivaci podvádět, protože by tak zaznamenali výrazné finanční ztráty. Čím více těžařů se k blockchainu připojí, tím větší a silnější bude.


Závěrem

Není pochyb o tom, že hashovací funkce představují zásadní nástroj počítačové vědy, zejména při nakládání s obrovskými objemy dat. Hashovací algoritmy mohou mít v kombinaci s kryptografií univerzální využití a zároveň nabízejí rozmanité formy zabezpečení a ověřování. Kryptografické hashovací funkce tedy hrají zásadní úlohu pro všechny kryptoměnové sítě a pochopení jejich vlastností a mechanismů fungování přinese užitek všem zájemcům o blockchainovou technologii.