1. Hash a hashovací funkce

Hash a hashovací funkce

Hash (otisk) je matematická funkce, která je založená na faktu, že jedním směrem je spočítaná velice snadno, ovšem její inverze, čili zpětné zjištění výpočtů, je velice obtížné, někdy dokonce nemožné. Hash se hojně využívá při řešení problému autentizace, pro elektronické (digitální) podepisování, pro verifikaci integrity dat, pro ukládání hesel, či pro generování náhodných dat. Je zřejmé, že hashovací funkce mají několikeré využití, my se budeme blíže zabývat využitím při autentizaci.

Problém autentizace

Říkali jsme si, že problémem užití RSA je v autentizaci odesilatele a adresáta.

Pokud bude s námi neustále asymetricky komunikovat Pepa a vyměňovat si s námi informace s tím, že každý už máme daný veřejný i privátní klíč, může zasáhnout opět zvídavá Jarmilka. Získá od Pepy privátní klíč, spočítá pomocí veřejného klíče správnou kombinaci a může vesele odposlouchávat. Či může pomocí veřejného klíče šifrovat zprávy a posílat falešné zprávy oběma stranám.

Jako další příklad si představme, že chceme vydat důležité prohlášení, ale nepřejeme si, aby s ním kdokoli manipuloval a zároveň chceme, aby si každý mohl ověřit, že jsme jej skutečně napsali my (tzn. že se za nás někdo nevydává a chceme potvrdit autorství dokumentu).

Jak tomuto zabránit? Autentizovat komunikující osoby. V autentizaci nám pomůže právě hash.

Hash

Výsledkem hashovací funkce je obvykle 128 nebo 160 bitů dlouhá sekvence, která naprosto jednoznačně označuje blok dat. Blokem dat lze zde rozumět dokument, email, nebo dokonce celý soubor dat. Podstatné ovšem zůstává, že stejná data mají vždy stejný otisk. Stejně tak, pokud změníme vstupní blok dat, výrazně se změní i hash těchto dat. Podvrh je tedy prakticky nemožný. Jediným problémem zůstává tzv. kolize. Kolizí rozumíme případ, kdy dva různé vstupní bloky dat mají stejný otisk. Žádanou vlastností kvalitní hashovací funkce je minimalizace těchto možných kolizí. Celý systém je přehledně zobrazen zde  obr. 1.

Obr. 1 Princip hashovací funkce

Když například zkombinujeme principy hashe a asymetrické kryptografie za účelem vytvoření digitálního podpisu, budeme postupovat následovně:

šifrujeme:

  • na otevřený text aplikujeme hashovací funkci a vytvoříme ze zprávy hash
  • ten zašifrujeme svým soukromým klíčem
  • zašifrovaný hash přiložíme ke zprávě a odešleme (samotná zpráva tedy šifrována není) obr. 2

Obr. 2 Šifrování pomocí hash a soukromého klíče


 

dešifrujeme:

  • ten, kdo si bude chtít ověřit, že zpráva je v pořádku a autenticita neporušená, použije veřejný klíč, kterým dešifruje hash obr. 3

Obr. 3  Dešifrování pomocí hash a veřejného klíče

 


 

  • pokud se hash dešifrovaný veřejným klíčem bude totožně shodovat s hashem vytvořeným s pomocí soukromého klíče, pak je zpráva v pořádku a nebylo s ní manipulováno obr. 4

Obr. 4 Ověřený hash je totožný, zprávy nebyla upravována

 


 

Principy a využitím digitálních a elektronických podpisů se blíže budeme zabávat v následujících článcích.

Hashovací algoritmy

Nyní si obecně představíme několik nejznámějších hashovacích algoritmů. Některým se budeme blíže věnovat v dalších studijních článcích a cvičeních.MD5 (Message Digest Algorithm 5)Algoritmus MD5, publikovaný v roce 1991, je založený na jednocestné matematické funkci, která tvoří z jakéhokoli textu hash o velikosti 128 bitů.Probíhají zde lineární i nelineární funkce, permutace, rozdělení bitů na jednotlivé bloky a samozřejmě patřičné logické operace.Zde se nabízí otázka - co je to lineární a nelineární funkce či logická operace? Napadá vás vysvětlení?

    • lineární funkce je taková funkce, která je závislá na definičním oboru a oboru hodnot, které nabývá; tyto hodnoty potom rovnoměrně klesají či stoupají (zvláštním případem je funkce konstantní)

nelineární funkce

       je potom taková funkce, která neklesá ani nestoupá rovnoměrně

logických operací

       máme několik -

 AND

      ,

 OR

      ,

 XOR

       a jejich inverze

 NAND

      ,

 NOR

       a

 IOR,

     pravdivostní tabulky jsou vžité axiomy, které není potřeba dokazovat, a jsou vidět na schématu obr. 5

Obr. 5  Pravdivostní tabulky vybraných logických funkcí

Hashovací algoritmus MD5 se využívá například pro ukládání hesel v Unixových operačních systémech, například Linux.SHA a jeho modifikaceSHA (Secure Hash Algorithm) je jednocestná hashovací funkce vyvinutá institucí National Institute of Standards and Technology (NIST). Je brána jako nástupce algoritmu MD5.Algoritmus vytváří z jakkoli dlouhé zprávy hash dlouhý 160 bitů. Tento hash je nazývaný také message digest. Hash je používán především jako digitální podpis zprávy a většinou slouží pro verifikaci její pravosti. Adresát vypočte hash a porovná s hashem přijaté zprávy, pokud nesouhlasí doručený message digest s tím, který adresát spočítal, zpráva byla cestou modifikována.Mezi další příklady algoritmů můžeme uvést:DSA - Digital signature algorithmDSA se stal roku 1994 americkým vládním standardem, který patří do sekce asymetrických algoritmů. Byl navržen NSA (National Security Agency) a určen pouze k digitálnímu podpisu. Algoritmus DSA využívá soukromého 160 bitového klíče a 1024 bitového veřejného klíče.Tento algoritmus je volně šiřitelný a tudíž jeho největší výhodou je, že vedle bezpečnosti poskytuje komfort freewarového programu. Problematika dešifrování se opět opírá o problém diskrétního logaritmu.Tiger a Tiger 2Tiger je hashovací funkce, kterou v roce 1995 navrhli Ross Anderson a Eli Biham. Tato funkce vytváří kontrolní hash o délce 192, 128 či 160 bitů. Používá se pro kontrolu integrity souborů nebo ukládání hesel. Upgrade Tiger 2 stále ještě není oficiálně publikovaný a narozdíl od předchozí verze používá jinou funkci pro ukončení algoritmu.Teď se společně podrobněji podíváme na některé ze zmíněných algoritmů.

Shrnutí

Po asymetrickém způsobu šifrování a představení některých zástupců, jsou na pořadu hashe. Hash nám z libovolně dlouhého dokumentu vytvoří podle hashovací funkce otisk. Této vlastnosti se využívá především u elektronických a digitálních podpisů.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.