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

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.