Otisk dat je používanější, než myslíte

S pojmem hashovací funkce se lze setkat prakticky na každém kroku internetem. Narazíte na něj při e-mailové komunikaci i při stahování sdílených souborů. Co se ve skutečnosti skrývá za tímto slovním spojením a jaké jsou jeho přínosy?

Související odkazy

Slovník
algoritmus
hash
P2P

Při komunikaci skrze síťové cesty může často dojít ke změně obsahu přenášených dat, ať už vinou zásahu třetí osoby nebo technickou chybou na trase. Aby si přijímající strana mohla zkontrolovat, zda data dorazila v pořádku, využívá se takzvaných hashovacích funkcí, díky nimž lze snadno vypočítat otisk dat (hash kód). Hashovací funkce pro vstup libovolné délky (slovo, věta, text e-mailu atd.) vytvoří otisk pevné délky, takže nesejde na tom, jestli původní soubor má 1 kB nebo 100 MB, otisk bude v obou případech mít délku například 160 b. V praxi pak odesílatel kromě vlastního souboru vypočítá ještě odpovídající hash kód a příjemce porovná otisk obdrženého souboru s původním hash kódem. Jsou-li oba kódy shodné, soubor se přenesl v pořádku.

Jedna z důležitých vlastností hashovacích funkcí již byla nepřímo představena – malá velikost výsledného otisku, pohybující se v řádech desítek a stovek bitů (nejčastěji používanými délkami jsou 128, 160 a 192 b). Další požadovanou vlastností je takzvaná jednosměrnost, což znamená, že pro každý vstup musí jít odpovídající hash kód snadno spočítat, ale naopak z výsledného otisku nesmí být možné odvodit původní data. Zbývá ještě zmínit bezkoliznost, která zajišťuje, že pro různé vstupy budou vypočítány různé otisky (i drobné změně vstupu by měly odpovídat velké změny výsledného otisku).

Rozličné použití hash kódů

Jak již bylo nastíněno, hashovacích funkcí lze s úspěchem použít pro zjištění chyb vzniklých během přenosu souborů. S hash kódy se ale můžete setkat také v řadě na první pohled odlišných aplikacích, jakými jsou například P2P (DirectConnect, Kazaa ad.), kde se jednoznačné otisky souborů dají využít k tomu, aby bylo možné nalézt soubor stejného obsahu. V praxi celá situace vypadá tak, že pokud stahujete soubor od nějakého uživatele a on se odpojí, můžete díky hash kódu snadno nalézt jiného uživatele, který má obsahově shodný soubor. 

Ukázka výstupu hashovacích algoritmů
Algoritmus Vstup Výstup
MD5 cash 93585797569d208d914078d513c8c55a
hash 0800fc577294c34e0b28ad2839435945
SHA-1 cash a34c860a9909dd2ed8b22b29b9377b8c6d48fbec
hash 2346ad27d7568ba9896f1b7da6b5991251debdf2
RIPEMD-160 cash 5ef72c1418aa8996fd0d27450e8fcfb72b0797a7
hash 73045e2e25b9531d5cb676cf73fff291d4a1ee6d

Mezi vlastnosti hashovacích funkcí patří také fakt, že malé změně textu by měla odpovídat velká změna výsledného otisku. Zde změna jediného písmene vede lavinovým efektem k úplné změně otisku.

Podobně lze také hash kódů využít při porovnávání hesel. Pokud se uživatel přihlašuje, vypočítá se z jím zadaného hesla odpovídající otisk a ten se porovná s otiskem uloženým v databázi. V právě uvedeném případě by ale mohla nastat situace, kdy si dva uživatelé zvolí stejné heslo, a tedy také výsledné hashe budou stejné. Tomu se dá snadno zabránit takzvaným solením, při němž se otisky počítají z hesel doplněných o nějakou další hodnotu (sůl), takže i když dva uživatelé budou mít stejné heslo, odpovídající otisky budou odlišné.

 

Přehled některých hashovacích funkcí
MD5 – jeden z nejznámějších algoritmů, navrhl jej Ronald Rivest v roce 1991. MD5 se stále hojně využívá, ačkoliv v něm byly objeveny některé slabiny a délka výsledného otisku, která činí 128 b, již není považována za vhodnou.

SHA – jedná se o skupinu algoritmů pocházejících z dílen NSA (National Security Agency). První verze byla navržena roku 1993 a oficiálně nesla právě označení SHA. Později se však pro ni vžilo spíše označení SHA-0, aby nedošlo k záměně s jejím následníkem SHA-1. Lze se také setkat s variantou SHA-2, která souhrnně označuje několik mírně modifikovaných verzí, jmenovitě SHA-224, SHA-256, SHA-384 a SHA-512.

RIPEMD-160 – výsledek úsilí trojčlenného týmu (Hans Dobbertin, Anton Bossealers a Bart Preneel) vytváří otisky délky 160 b. Jak bezpečností, tak výkonem jsou RIPEMD a SHA považovány za velice podobné.

Konečně, malé velikosti hash kódu lze s úspěchem použít také při asymetrickém šifrování, přesněji digitálním podepisování soukromým klíčem. V praxi může být zapotřebí podepisovat soubory o desítkách nebo stovkách megabajtů, což může nějakou dobu trvat. Proto se nejprve vytvoří mnohem menší otisk takovéhoto souboru a odesílatel podepíše pouze vzniklých několik desítek bitů.

Pokusy o útok: hledání kolizí

Hash kódy v praxi? HashCalc!
Chcete-li si nabyté znalosti o hashovacích funkcích vyzkoušet v praxi, můžete k tomu použít velice jednoduchou a přehlednou aplikaci HashCalc od společnosti SlavaSoft. Tento volně šiřitelný nástroj nabízí řadu hashovacích algoritmů, které lze použít na text i soubory.
Hashovací algoritmy tedy hrají významnou roli nejen ve světě síťové komunikace a není divu, že postupem času byly hledány jejich slabiny. Hitem několika posledních měsíců se staly útoky na často používaný algoritmus MD5, kdy byl nejprve zveřejněn takzvaný čínský útok a poté i výsledky snažení Vlastimila Klímy, jednoho z nejznámějších českých kryptologů.

Výsledkem prvně jmenovaného postupu je schopnost současného vytvoření dvou rozdílných soborů se stejným hash kódem (takzvaná kolize prvního řádu), nelze jím však k libovolnému souboru vytvořit jiný se stejným hash kódem (tzv. kolize druhého řádu). Vlastimil Klíma pak začátkem roku přišel s novou variantou hledání kolizí, jež je údajně až šestkrát rychlejší než metoda čínských vědců.

V souvislosti s kolizemi se také často mluví o narozeninovém paradoxu, který využívá zajímavého výsledku elementární matematiky. Představte si, že je v jedné místnosti, nebo spíš sále n lidí. Pak pravděpodobnost, že některý z nich má narozeniny ve stejný den jako vy, je 1−(364/365)n.

To znamená, že pro dosažení alespoň padesátiprocentní pravděpodobnosti by bylo zapotřebí 254 osob. Tato situace přesně odpovídá té, kdy známe výsledný hash jednoho řetězce a chceme najít druhý řetězec, který má stejný hash. Uvážíte-li naproti tomu situaci, kdy hledáte libovolné dva řetězce takové, že jsou různé avšak mají stejný hash kód, tak ta odpovídá tomu, že z n lidí v sále mají alespoň dva narozeniny ve stejný den. Pravděpodobnost se pak spočítá ze vztahu 1−(365!/(365n×(365−n)!)). Pro alespoň padesátiprocentní pravděpodobnost tedy stačí pouze 23 lidí! Máte-li možnost vyzkoušet tento paradox na větší skupině lidí, určitě to udělejte, budete pravděpodobně překvapeni, jak zdánlivě nelogické tvrzení platí.

Ani takové paradoxy, ani výzkumy čínských vědců nic nemění na faktu, že hashování je a bude v praxi hojně používáno a každý počítačově gramotný člověk by měl tušit, o co jde.

Článek vznikl
ve spolupráci
s časopisem
Computer
a čerpá
z čísla 12/05.

Diskuze (15) Další článek: Mechanismus kontroly pravosti Windows již prolomen

Témata článku: Fingerprint, MD5, National Security Agency, Soukromý klíč, Libovolný soubor, Mys, Paradox, Ron Rivest, Mysl, Libovolný kód, Původní funkce, Otis, Stejný soubor, Bart, Cash, Solení, Druhý řetězec, Rozdílná velikost, Soli, Hashovací funkce, Asymetrické šifrování, Původní data, Odlišné zjištění, Otisk



Sex manželských párů? Jen výjimečně. Ložnice ovládnou roboti s umělou inteligencí

Sex manželských párů? Jen výjimečně. Ložnice ovládnou roboti s umělou inteligencí

** Sex manželských párů jen při zvláštních příležitostech. ** Ložnice ovládnou sexuální roboti s umělou inteligencí. ** I to je jeden ze závěrů Mezinárodní robotické konference.

Filip KůželJiří Liebreich
RobotiSexUmělá inteligence
Jak poznat, že máte možná hacknutý telefon? Toto je devět symptomů, které můžete pozorovat

Jak poznat, že máte možná hacknutý telefon? Toto je devět symptomů, které můžete pozorovat

** Jak poznat, že je váš smartphone hacknutý? ** Hledejte známky po nestandardním chování telefonu ** Stačí když telefon vydrží méně nebo topí i v klidovém režimu...

Martin Chroust
Jak...Malware
Recenze hry Sonic Origins. Povedené předělávky klasik s několika vadami na kráse

Recenze hry Sonic Origins. Povedené předělávky klasik s několika vadami na kráse

Novým přírůstkům do Sonicovy série se nedaří zrovna nejlépe. Sega se tentokrát vrátila až na samotný začátek modrého ježka a jeho původní dobrodružství znovu vydala v přepracované podobě. Jak se kolekce Origins povedla?

Martin Nahodil
Sonic OriginsPS5Recenze
Zákaz potratů nutí ženy mazat aplikace pro sledování svého cyklu. Facebook to řeší mazáním účtů a příspěvků

Zákaz potratů nutí ženy mazat aplikace pro sledování svého cyklu. Facebook to řeší mazáním účtů a příspěvků

** Zrušení práva na potrat v USA má nečekaný vliv i na mobilní technologie ** Uživatelky ze strachu mažou citlivé aplikace ** Meta zase maže příspěvky a účty lidí, kteří nabízí potratové pilulky

Martin Miksa
MetaZdravíPro ženy
Doba pokročila. Češi dostali aplikaci, se kterou mohou partnerovi odsouhlasit sexuální styk

Doba pokročila. Češi dostali aplikaci, se kterou mohou partnerovi odsouhlasit sexuální styk

** Mobilní aplikace XPass chce zatočit se sexuálním násilím ** Uživatelům umožní udělit souhlas k pohlavnímu styku QR kódem ** Kromě toho chce také chránit a edukovat

Martin Miksa
SexMobilní aplikace