Hashing

Hashing - hašování: v oblasti databází technika řešící přístup k datovým záznamům na základě znalosti klíče. V kryptografii se hašovací algoritmy používají zejména pro potřeby zajištění integrity přenášených zpráv či uchovávaných dat. V rámci operačních systémů se hašovací techniky používají i pro potřeby evidence hesel.

S anglickým termínem hashing, v českém překladu nepříliš libě znějícím jako "hašování", jsme se doposud setkávali především v oblasti databází a hromadného zpracování dat. Zde se týká způsobu, jak se dostat k místu, kde je uložen určitý konkrétní datový záznam, od kterého je znám jeho klíč. V každé databázi, obecně všude tam kde je nashromážděn určitý objem dat, musí být jednotlivé datové záznamy určitým způsobem uspořádány, tak aby bylo vždy možné najít konkrétní záznam, který je právě požadován. Jednou z možností je uspořádat jednotlivé záznamy sekvenčně podle hodnoty hodného klíče, a pak mezi nimi vyhledávat také sekvenčně, tedy postupným procházením. Alternativou je předem znát pro každý jednotlivý záznam jeho přesné umístění, a pak "jít na jistotu", bez nutnosti jakéhokoli vyhledávání. Kompromisním řešením je právě myšlenka hašování: z klíče, podle kterého má být záznam vyhledán, se nepříliš náročným způsobem (pomocí tzv. hašovací funkce) vypočítá konkrétní adresa, na které by hledaný záznam měl být umístěn. "Měl" proto, že právě kvůli jednoduchosti a celkové efektivnosti uložení dat je hašovací funkce koncipována tak, že pro různé klíče může dávat stejné výsledky, neboli dvěma různým datovým záznamům může přisoudit stejné fyzické umístění. To je konflikt, který se řeší sekvenčním uložením, resp. sekvenčním vyhledáváním: jednotlivé datové záznamy, pro jejichž klíče dává hašovací funkce stejné výsledky, jsou uloženy za sebou, a jejich vyhledávání znamená "jít na určité místo přímo" (na základě adresy poskytnuté hašovací funkcí), a odsud pak hledat sekvenčně.

S principem "hašování", či spíše s "hašovacími algoritmy", se však lze setkat i v kryptografii, kde se používají pro potřeby zabezpečení. Také zde je hašovací funkce, resp. hašovací algoritmus chápán jako určitá transformace vstupního textu, která je relativně jednoduchá a rychlá, a lze ji snadno aplikovat například na celou zprávu. Výsledkem pak je funkční hodnota, které se říká také "message digest" (což lze velmi volně přeložit jako "výcuc zprávy") - jde typicky o datovou položku konstatní (a předem pevně dané délky), bez ohledu na velikost původní zprávy, resp. zdrojového textu. Už z tohoto samotného faktu by měla být zřejmá jedna základní vlastnost "hašování" v kryptografii: různé zprávy mohou stejný "message digest", neboli stejný "výcuc". Konkrétním důsledkem pak je fakt, že celé hašování je na rozdíl od většiny šifrovacích algoritmů pouze jednosměrným a nevratným procesem - nesnaží se činit taková opatření, aby byla možná i zpětná transformace, neboli odvození původní zprávy na základě znalosti jejího "výcucu" (message digest). Vzhledem k faktu, že různé zprávy mohou mít stejné "výcuc-y", by to ani nebylo principiálně možné.

K čemu je pak ale hašování v kryptografii vůbec dobré? Pokud se hašovací algoritmus zvolí dostatečně šikovně, lze "výcuc" konkrétní zprávy použít například k tomu, aby se zajistila její integrita - tedy aby příjemce měl jistotu, že samotná zpráva nebyla při svém přenosu přes nezabezpečené přenosové cesty jakkoli pozměněna. Jelikož samotné hašovací algoritmy jsou obvykle veřejně známé, nemělo by smysl posílat "výcuc-y" spolu s vlastními zprávami v nezabezpečeném tvaru - protože ten, kdo by chtěl zprávu pozměnit, by jednoduše vypočítal nový "výcuc" a ten připojil ke zfalšované zprávě. V praxi se proto samotné hašování ještě kombinuje se šifrováním - například při symetrických technikách na bázi tajného klíče sdíleného oběma komunikujícími stranami je možné vzít zdrojovou zprávu, pro potřeby výpočtu k ní připojit zmíněný tajný klíč, z výsledného celku vypočítat příslušný "výcuc", a ten přenést spolu se zdrojovým tvarem zprávy. Případný nepřítel pak bez znalosti tajného klíče nemůže pozměnit zprávu a vypočítat k ní nový (a hlavně správný) "výcuc" - příjemce totiž vezme zdrojový tvar zprávy, připojí k ní svou kopii tajného klíče, sám si vypočítá "výcuc", a ten porovná s "výcuc-em", který příšel od druhé strany. Pokud se shodují, má příjemce velkou míru jistoty, že zpráva (přenášená třeba i v nezašifrovaném tvaru) nebyla jakkoli pozměněna.

Samotný hašovací algoritmus, jehož možné využití jsme si právě naznačili, by měl být volen tak, aby výpočet "výcuc-u" byl dostatečně rychlý a jednoduchý, ale na druhé straně bylo nesmírně těžké najít různé zdrojové texty, které budou mít stejný "výcuc", či najít alespoň jeden zdrojový text, jehož "výcuc" by se shodoval s předem známým "výcuc-em" - zde se v podstatě chce, aby to nešlo dělat nijak rozumněji a efektivněji, než postupným vyzkoušením všech možností, které připadají v úvahu.

Různé hašovací techniky se s oblibou používají i pro četné další účely související se zabezpečením, nejen se zajištěním integrity (neporušenosti) přenášených zpráv, případně dat uchovávaných na určitém konkrétním místě. S oblibou se používají například pro potřeby evidence hesel všude tam, kde je třeba nějaká hesla skladovat. Není totiž moc rozumné uchovávat je v jejich zdrojovém tvaru, například v jediném textovém souboru - jeho získáním by si případný narušitel doslova otevřel všechny dveře dokořán! Místo samotných hesel však lze uchovávat například jen jejich "výcuc-y" - vzhledem k charakteru hašovacího algoritmu pak bude nesmírně složité odvodit původní heslo, ale pro "strážce systému" (tj. pro operační systém) bude naopak velmi jednoduché ověřit si podle seznamu "výcuc-ů", zda konkrétní uživatelem zadané heslo je správné či nikoli.