Osobní stránky

Denial of service útok na webové aplikace s využitím hash kolize

V posledních měsících se objevilo několik článků a prezentací týkající se zranitelnosti webových aplikací pomocí kolize hashů. Idea tohoto útoku se objevila již v roce 2003, ale většina programovacích jazyků zavedla protipoatření až v nedávné době. V tomto článku popíšu základní myšlenku útoku a jak se proti němu bránit.

Pokud předává jakákoliv webová stránka data serveru, využívá se pro ukládání těchto proměnných speciální datová struktura, v Javě Map, v PHP array, v ASP.NET NameValueCollection a podobně. Všechny tyto datové struktury slouží k uložení dat ve fromátu: klíč1 = hodnota1, klíč2 = hodnota2. Jelikož může mít klíčjakoukoliv hodnotu, tak se k uložení se použije hashovací funkce.

Hashovací funkce funguje tak, že pro každý vstup vrátí vždy stejně dlouhý otisk parametru = hash, může to být číslo nebo řetězec. Pokud této funkci dáváme různé vstupy, otisky by tedy měly být rovnoměrně rozdělené. Ukažme si vše na příkladu. Pokud budeme chtít vložit klíč login s hodnotou root, výsledek hashovací funkce bude například hash("login") = 2. Hodnoty se ukládají do spojových seznamů, které jsou na začátku rozděleny do několika částí podle rozsahu hashovací funkce (ty reprezentují čtverečky na prvním obrázku). Budeme uvažovat, že hashovací funkce vrací číslo v rozsahu 0 – 4, abychom podle toho věděli do které části proměnnou vložit (v praxi se používají mnohem větší rozsahy).

Dále budeme chtít do proměnné volžit klíč pass s hodnotou abc123, hash bude hash("pass") = 4. Proměnná bude po tomto vložení vypadat jako na následujícím obrázku, pass se vloží na čtvrtou pozici.

Jako třetí budeme potřebovat vložit klíč param s hodnotou foo, jejíž hash je hash("param") = 2. Tím vznikne kolize, pozice 2 je již zabraná, takže musíme vložit novou proměnnou za hodnotu login.

Pokud dojde při přidávání položek k další kolizi, hodnoty se vloží za poslední prvek v odpovídající kategorii podle hashe. Celý tento způsob zajišťuje rychlý způsob vkládání, vybírání a mazání z takovéto proměnné. V průměrném čase tato implementace dosahuje lineární složitosti Θ(n) = n, to znamená, že rychlost záleží lineárně na počtu prvků. V nejhorším případě je ale složitost exponenciální O(n) = n2, to znamená, že délka trvání je úměrná druhé mocnině počtu prvků. Teto případ nastává, pokud vkládáme jen kolizní prvky, musí se totiž projít celý spojový seznam již vložených prvků až na konec.

Celý útok je založen na tomto principu, serveru budeme posílat jen kolizní prvky ve velkém množství. Když tedy vložíme dostatečně velké množství prvků zahltíme tím paměť serveru a vytížíme procesor, takže nebude moci obsluhovat ostatní požadavky. Pokud navíc odešlemě několik takovýchto požadavků zároveň, nebudou k internetové stránce moci přistupovat ostatní uživatelé. Tento útok se nazívá denial of service (DoS), tedy odepření služby.

Každý programovací jazyk má různou implementaci tohoto hashovacího algoritmu, takže se způsoby vytváření kolizí liší. Pro vytvoření kolize v PHP nám stačí jednoduchý skript:

$size = pow(2, 16);
$startTime = microtime(true);

$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
    $array[$key] = 0;
}

$endTime = microtime(true);

echo ($endTime - $startTime) .' seconds';

Tento skript na mém počítači trvá přibližně 30 sekund. Pokud vkládáme stejný počet čísel postupě od 0 do $size, celý skript trvá přibližně 0,01 sekund. Do pole se vkládají ve skriptu jen kolizní prvky a proto dojde k takovémuto nárůstu času. Za druhý parametr funkce pow() můžeme dát kromě 16 jakékoliv jiné číslo, například 15 nebo 17, a ke kolizím bude docházet stále.

Vytváření kolizí záleží na implementované hashovací funkci. Každý programovací jazyk používá rozdílnou hashovací funkci a proto budou i způsoby vytváření kolizí v různých jazycích rozdílné.  Všechny hlavní programovací jazyky již naštěstí vydaly opravnou verzi, která takovémuto typu útoku zabrání. Většinou omezují maximální počet předaných parametrů serveru na nějákou rozumně vysokou hodnotu, například 1000. Tato hodnota je dostatečně vysoká pro předání všech parametů od webové stránky a dost nízká na to, aby nemohlo dojít k enormnímu zatížení serveru. Většina serverů a jazyků také umožňuje tuto hodnotu změnit podle potřeby.

Jakub Škvára


Jakub je cestovatel, blogger a webový vývojář. Zajímá se především o technické novinky a rád navštěvuje konference. Používá: Symfony2 Framework, AngularJS, NodeJS, MongoDB a další moderní technologie. Aktuálně žije v Londýně.