Hlavní navigace

Hašovací funkce: Jak se odolává hackerům

3. 5. 2005
Doba čtení: 8 minut

Sdílet

Vývoj našich znalostí o hašovacích funkcích se za posledních osm měsíců posunul vpřed přímo radikálním způsobem. Loni byl prolomen algoritmus MD5, oznámeno bylo i snížení náročnosti při nalézání kolizí v SHA-1. Co to vlastně hašovací funkce jsou, jaké vlastnosti se od nich vyžadují a jaký je jejich význam v počítačové bezpečnosti?

Při oznamování pokroku z kryptoanalýzy hrozí vypuknutí paniky nebo naopak, a snad i častěji, podcenění. Oznamování bezpečnostních děr počítačových produktů probíhá jak na běžícím páse, těmito novinkami by se mohly živit samostatné agentury. Změny teoretických základů však často zasahují různé způsoby nasazení a celou škálu produktů od mnoha výrobců a je třeba jim věnovat zvýšenou pozornost.

Oproti počítačovým dírám, které vznikají nedbalostí a stresem z rychlosti vývoje, jsou změny v teorii nezbytným průvodním jevem vývoje kryptologie jako vědy i stále stoupajícího výpočetního výkonu. Produkty a systémy by s tímto jevem měly počítat a být již koncipovány tak, aby bylo možné postupně přecházet na novější šifrovací algoritmy.

V tomto a v navazujícím článku se pokusím shrnout poměrně nečekaný vývoj v oblasti hašovacích funkcí za posledních cca osm měsíců. Jejich oslabení se významně týká především použití v mé domácí oblasti – elektronickém podpisu.

Chcete-li přesně pochopit podstatu novinek, je zapotřebí znát trochu teorie, snažím se ji však podat co nejpřístupněji. Matematicky orientovaní čtenáři zde naopak naleznou všechny relevantní odkazy.

Úvod do hašovacích funkcí

Hašovací funkce je funkce h, která má přinejmenším tyto vlastnosti: je kompresní – provádí mapování argumentu /vstupu/ x libovolné bitové délky na hodnotu h(x) /výstup/, která má pevně určenou bitovou délku, je snadno vypočtitatelná – pro dané h a argument x je snadné vypočítat h(x).

Tuto vlastnost ilustruje obrázek č.1, na němž je argument označen jako „zpráva“ a hodnota funkce slovem „otisk“. Smyslem použití hašovacích funkcí obecně bývá možnost reprezentovat potenciálně i velmi dlouhou zprávu jen jejím krátkým otiskem a vytvořit pomyslnou relaci 1:1 mezi zprávou a otiskem.

1612
Obr. 1 – Kompresní vlastnost všech hašovacích funkcí

Hašovací funkce mají v počítačové praxi velmi mnoho použití. V diagnostice hardware např. indikují konečné stavy testů, v komunikaci se používají pro detekci chyb (kódy CRC apod.), v softwarových technikách např. pro implementaci tabulek atd. Ve všech těchto případech se zpravidla vyžaduje, aby hašovací funkce prováděla i dobrou náhodnou distribuci výsledků, rovnoměrné pokrytí oboru hodnot, aby malá změna vstupního řetězce vedla jistě k odlišnému výsledku (ideálně lavinově jinému).

Hašovací funkce vyhovující výše uvedeným aplikacím sice dobře detekují „náhodné“ změny argumentů (zprávy), nejsou však dostatečné pro obor kryptologie, ve kterém lze předpokládat, že útočník bude postupovat při změnách argumentů funkce s veškerou možnou inteligencí.

Kryptologové se proto, mimo jiné, zabývají hašovacími funkcemi (funkci značíme h, argumenty x a x’ /vstupy/, hodnoty y a y’ /výstupy/), které mají následné tři vlastnosti:

1. Odolnost argumentu (preimage resistance) – pro v podstatě všechny výstupy je výpočtově neschůdné nalézt jakýkoliv vstup, který hašuje na daný výstup; tj. nalézt jakýkoliv argument x takový, že h(x) = y pro danou hodnotu y, pro niž odpovídající vstup není předem znám.

Pro ne-matematiky ilustruje tuto vlastnost obrázek 2.

1613
Obr. 2 – Odolnost argumentu (též „jednocestnost“)

Tato vlastnost polopaticky řečeno znamená, že z otisku nesmíme být schopni zjistit jakoukoliv zprávu, které by odpovídal.

Předem známa je pouze funkce h, tj. způsob jejího výpočtu, definiční obor (kruh vlevo) i obor hodnot (kruh vpravo) této funkce. Z oboru hodnot je volen libovolný výstup y. Nalezení jakéhokoliv vstupu x funkce h, který bu mu odpovídal, nesmí být možné. Definice uvedená výše připouští, že útočník může předpočítat obraz (hodnoty y) pro nějakou zanedbatelně malou podmnožinu vzorů z definičního oboru – takové způsoby nalezení argumentu se neuvažují, protože se předpokládá, že se útočník na y netrefí.

V praxi je v takové situaci například útočník na heslo x, které je uloženo formou zhašované hodnoty y v souboru na disku, k němuž se mu podařilo získat přístup (pro ztížení slovníkových útoků bývají hodnoty hesla ještě tzv. osoleny, ale to zde rozebírat nebudeme).

2. Odolnost druhého argumentu (2nd-preimage resistance) – je výpočtově neschůdné nalézt jakýkoliv druhý vstup, který má shodný výstup jako jakýkoliv určený první vstup; tj. pro dané x nelze nalézt druhý argument x’ ≠ x, přičemž platí h(x) = h(x’) = y.

1614
Obr. 3 – Odolnost druhého argumentu (též „slabá odolnost proti kolizím“)

Tato vlastnost se projeví v „normální“ situaci, kterou si většina uživatelů představí při útoku na hašovací funkci. Máme předem dánu hašovací funkci h, nějakou zprávu x a její otisk y (nebo ho snadno spočteme). Nesmí být možné nalézt jakoukoliv jinou zprávu x’, jejíž otisk by byl stejný. Protože se předem neví, jakou zprávu budeme hašovat, výše uvedená definice požaduje tuto vlastnost pro všechny argumenty x.

V praxi přichází do úvahy útok tehdy, pokud by chtěl někdo zaměnit zprávu x za x’, což může přicházet do úvahy např. při (elektronickém) digitálním podpisu, při kontrole integrity souborů (ať již stahovaných z webu nebo P2P sítí). Běžný člověk by si pravil, že to by mohlo stačit, kryptologové však vznášejí ještě třetí požadavek.

3. Odolnost proti kolizím (collision resistance) – je výpočtově neschůdné nalézt jakékoliv dva rozdílné vstupy x a x’, které hašují na shodný výstup; tj. x’ ≠ x takové, že h(x) = h(x’) = y (volný výběr obou vstupů).

1615
Obr. 4 – Odolnost proti kolizím (též „silná odolnost proti kolizím“)

Tato situace se liší od předchozí tím, že si je možné hodnotu x volit libovolně. Na první pohled se zdá, že se jedná o shodné definiční podmínky jako v předchozím případě, ale rozhodně tomu tak není. Danost zprávy x (prvního argumentu) je totiž při zkoušení odolnosti druhého argumentu určena nějakou, na útočníkovi nezávislou, podmínkou. Z pohledu útočníka je x již dáno a musí pro něj hledat x’.

Při obecné (silné) odolnosti proti kolizím si však útočník může volit x i x’ s jediným cílem, totiž aby hašovaly na shodnou hodnotu (lhostejno jakou). Tato vlastnost předpokládá, že útočník je v takové pozici, že může ovlivnit vstupní hodnotu hašovací funkce. Další viz níže u útoků Wangové, které se všechny zaměřují na toto obecné hledání kolizí (dle obr.4).

Ideální kryptografická hašovací funkce bude oplývat všemi třemi vlastnostmi! Je vhodné chápat, že pokud je velikost množiny definičního oboru hašovací funkce větší než oboru hodnot (což bývá v praxi vždy), hašovací funkce nemůže být bezkolizní. Pozorný čtenář si však jistě všiml, že definice obsahují obraty „výpočtově neschůdné“ – kolize prostě nesmí být možné nalézt. Kontext definice se mění jak rozvojem technologie, tak požadovanou mírou ekonomických nákladů (nemá smysl utrácet více, než získáte).

Pro další úvodní seznámení se s hašovacími funkcemi doporučuji buď známou knihu od Menezes/Oorschot/Van­stone nebo přístupnější český článek od kryptologů Klíma/Rosa, pojednávající zejména o variantě HMAC [PDF, 150kB].

Pozn.: existují případy patologických funkcí (např. identita), které jsou odolné proti druhému argumentu, popř. jsou i odolné proti kolizím, ale nemají odolný argument; odolnost argumentu nelze proto obecně implikovat a je zapotřebí uvádět všechny tři vlastnosti samostatně.

Narozeninový paradox

Zajímavé rovněž je, že obě zmíněné situace (obr.3 a obr.4) mají rozdílný výpočet pravděpodobností náhodného nalezení kolizí. Druhá situace je v kryptologii známa jako tzv. narozeninový paradox. Jste-li na večírku, pak pro 50procentní pravděpodobnost toho, že se na něm nachází někdo, kdo se narodil shodný den v roce (léta se neuvažují) jako právě vy, je zapotřebí, aby tam přišlo alespoň 254 osob (musíte jít na megapárty). Pokud se však spokojíte s 50procentní pravděpodobností toho, že se na večírku nachází libovolné dvě osoby se shodným narozeninami, pak dostačuje, aby večírek navštívilo 23 osob.

Pozn: narozeninový paradox samozřejmě předpokládá náhodnost narozenin dotyčných, tj. že nejste třeba na vítání občánků, ani nejste dvojčata, chodící spolu kazit statistiky. Uvedené pravděpodobnosti též zanedbávají přestupné roky.

Tato nevinná matematická hříčka má v kryptologii vážný dopad. Útoky hrubou silou jsou v případech použitelnosti narozeninového paradoxu totiž mnohem snazší a říká se jim pak narozeninový útok.

SHA-1

Kryptografický hašovací algoritmus SHA-1 byl původně definován ve FIPS 180–1, tato specifikace je však již nahrazena novější verzí FIPS 180–2 [PDF, 242 kB], která obsahuje navíc i definice nových variant (někdy souhrnně označovaných jako SHA-2), které zahrnují SHA-224, SHA-256, SHA-384 a SHA-512.

Zatím pouze uveďme, že SHA-1 rozsekává vstupní zprávu na bloky o délce 512 bitů, poslední blok zprávy doplňuje a zarovnává, včetně přidání údaje o délce zprávy, na nějž je vyhrazeno posledních 64 bitů. SHA-1 tak může zpracovávat vstupní zprávy o délce až do 264−1 bitů, tj. cca 2.305.840 TB. Uvedením délky se výrazně ztěžuje možnost nalezení a výskytu kolizí mezi zprávami různých délek – kolize je primárně potřeba hledat mezi zprávami zcela shodné délky. Výstup SHA-1 má délku 160 bitů, tj. 20 bytů.

SHA-1 je, podobně jako jiné hašovací funkce, tzv. iterativní hašovací funkce. To znamená, že při zpracování každého 512bitového bloku se vždy použije stejný modul tzv. vnitřní kompresní funkce. Kompresní funkce má dva vstupy, 160bitový (v prvním kroku je inicializován předepsaným inicializačním vektorem, v dalších krocích přenosy z výstupů minulých kroků jako tzv. kontext) a 512bitový (blok dat). Po zpracování posledního bloku se výstup kompresní funkce použije jako výstupní hodnota.

Náhodné orákulum

Nyní je vhodné se seznámit s matematickou fikcí tzv. náhodného orákula. To se chová tak, že na zadání vstupní zprávy vydá náhodnou hodnotu výstupu, a toto přiřazení si již pamatuje. Při zadání jiných zpráv opět vždy generuje zcela náhodnou hodnotu výstupu (neohlíží se ani na to, jaké hodnoty již vygenerovalo). Pokud však zadáte zprávu, pro kterou orákulum již někdy hodnotu generovalo, pak sáhne do své paměti a poskytne stejnou hodnotu jako dříve. V tomto ohledu dřívějších jevů se orákulum tedy chová algoritmicky a deterministicky. Ideální hašovací funkce by pak měla mít matematicky shodné vlastnosti, jaké vykazuje náhodné orákulum.

Poskytuje-li orákulum délku výstupu 160 bitů, pak útok hrubou silou na orákulum na odolnost proti druhému argumentu (obr.3) má výpočetní náročnost řádu 2160. Při útoku proti kolizím (obr.4) se využije narozeninový paradox a náročnost útoku nakonec přibližně vyjde jen v řádu 2^(160/2) = 280 pokusů.

BRAND24

Zde je tedy patrné, jak nárok na silnou odolnost proti kolizím dramaticky snižuje náročnost útoku proti hašovacím funkcím, nikoliv třeba 2×, ale 280 krát!

Tolik tedy spíše teoretičtější úvod do problematiky hašovacích funkcí. Doufám, že vás příliš neunavil, protože příště se již podíváme na konkrétní případy útoků na MD5 a SHA-1.

Tipněte si, kolik náhodně narozených osob musí být na vaší párty, aby s cca 90procentní pravděpodobností nastalo, že: aspoň dvě budou mít narozeniny ve shodný den / někdo v místnosti má narozeniny jako Vy?

Byl pro vás článek přínosný?

Autor článku

Autor se několik let specializuje na Elektronický podpis v ČR aj. konzultace v oblasti počítačové bezpečnosti.
Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).