Kolize hashů pro mírně pokročilé
Hash tabulka je jedna ze základních datových struktur, byla vynalezena roku 1953 a všichni, kdo programování viděli aspoň z rychlíku, ji velice dobře znají. Hash tabulky (někdy také hashmapy nebo slovníky/dictionary) umí vyhledat, přidat nebo smazat hodnotu asociovanou s určitým klíčem v konstantním čase. Všechno je možné jen díky jednomu velice chytrému triku - použití hashovací funkce, která klíč, ať už je jakéhokoli typu a velikosti, zobrazí na číslo. To je potom využito k adresování do obyčejného plochého pole, které všichni známe a milujeme.
Tohle všechno funguje skoro až zázračně. Tedy aspoň do okamžiku, kdy to přestane. Pak se dostáváme do velkých problémů.
Všechno záleží na použité hashovací funkci. Ta by měla v ideálním případě být pseudo-náhodná - měla by produkovat hashe, které jsou rovnoměrně rozložené v oboru hodnot a které nezachovávají korelace mezi vstupními hodnotami, kdy např. hashe posloupnosti čísel také připomínají posloupnost. Jinými slovy: mělo by jít alespoň o jednu z rodiny univerzálních hashovacích funkcí.
Pokud hashovací funkce produkuje nadprůměrné množství stejných hashů pro různé hodnoty, nebo je předvídatelná a hodnoty s kolidujícími hashi může někdo, jehož záměry jsou méně než upřímné, snadno spočítat, hash-tabulky najednou začnou vykazovat patologické chování, kdy dříve konstantní operace potřebují lineární čas úměrný velikosti tabulky. Může tak jít o velice efektivní DOS útok.
Abych to osvětlil, musím se ponořit do krvavých detailů.
Hash tabulky mají tři základní varianty: chaining, probing a cuckoo hashing. Chaining a probing se také označují jako open hashing a open addressing, ale tohle označení nemám rád, protože si nikdy nemůžu vzpomenout, které je které.
Řetězící (chaining) varianta se zakládá na poli pointerů (buckets). Každý z
nich ukazuje na spojový seznam, jehož každý článek obsahuje klíč, odpovídající
hodnotu a pointer na následující článek (nebo null). Když chci vložit pár (key
, value
),
spočítám hash klíče hash = ϝ(key)
a z něj odpovídající pozici v poli pointerů
index = hash % arraySize
. Pokud je daná pozice prázdná, vytvořím článek a
nastavím pointer na pozici index
, aby na něj ukazoval. Pokud už je index
obsazený, vytvořený článek připojím na konec seznamu.
Aby tohle fungovalo v konstantním čase, kolize musejí být nepravděpodobné.
Pokud to platí, většina spojových seznamů obsahuje jen málo článků (v průměru
n/m
, kde m
je velikost tabulky a n
počet vložených elementů) a pole
pointerů má délku úměrnou počtu položek v tabulce. V praxi jde o
určitý malý násobek a je dovolené jen určité maximální zaplnění tabulky. Když
je tato mez překročena, tabulka se zvětší na dvojnásobek, všechny klíče se
rehashují na nové pozice a řetězy kolizí se zkrátí. Zvětšování o násobek
garantuje amortizovaný konstantní čas operace vkládání.
Probing varianta typicky používá tři interní pole - jedno obsahuje klíče, druhé odpovídající hodnoty a třetí označuje smazané položky.
Pokud chci vložit klíč, stejně jako v minulém případě spočítám jeho hash a z něho odpovídající index v trojici stejně dlouhých polí. Když je odpovídající místo prázdné, klíč a hodnotu tam jednoduše vložím. Pokud je však místo už zabrané, vložím klíč a hodnotu o jedno místo doprava (linear probing), o 2i míst doprava (quadratic probing) nebo o počet míst vypočítaný jinou hashovací funkcí (double hashing). Pokud je plno i tam, zkouším další místa napravo dokud nenajdu volný flek.
Když chci najít určitý klíč, spočítám hash a z něho pozici, na které by se měl nacházet. Pokud se na tomto místě nachází, skončím s úspěchem. Pokud se tam nachází jiný klíč, zkusím to o jedno místo vpravo. Takto pokračuji, dokud nenajdu požadovaný klíč, smazaná místa ignoruji. Když narazím na prázdnou hodnotu, prohlásím, že klíč nebyl nalezen. Šipky v diagramu ukazují, kde se nachází další klíč se stejným hashem. Jak je vidět tento blok nemusí být spojitý a mezi klíči, které mají shodný hash, můžou být vklíněny klíče s jinými hashi. Záleží jen na pořadí vložení.
Pokud chci klíč smazat, pokusím se nalézt místo, kde se nachází (postup stejný
jako v minulém odstavci) a potom, co ho objevím, ve třetím poli označím danou
pozici jako smazanou (jde o pole boolů nebo o bitmapu). Kdybych
klíče mazal tak, že bych odpovídající pozici v prvních dvou polích jen nastavil na null
,
rozbil bych hledání, protože bych tak do spojitých bloků vnesl díry a hledání
by při nalezení této díry skončilo a nemuselo by se dostat ke správným
hodnotám, které se můžou nacházet těsně za touto dírou.3
Konstantní čas pro všechny operace je zaručen opět tím, že hash funkce negeneruje kolize a rovnoměrně rozkládá hashe. V důsledku toho budou sekvence, které je potřeba projít při hledání klíčů, rozumně krátké. Tři zmíněná pole mají délku která je opět úměrná počtu položek v tabulce, i když bývají větší než u chainingu, protože efektivita probingu dramaticky degraduje, když se zaplnění tabulky blíží 100 procentům. Dlouhé běhy obsazených pozic, kam spadne mnoho hashů, která náhodou byly blízko sebe, se ještě více prodlužují a s nimi i počet míst, které je třeba projít. Nestačí jen jako v případě chainingu projít jeden spojový seznam odpovídající jednomu hashi, ale blok odpovídající několika hashům.
(Technicky vzato: Hashovací funkce použitá pro linear probing musí být aspoň 5-independent nebo musí jít o tabulation hashing, jinak není garantován konstantní čas. Více v tomto videu.)
Třetí variantou je takzvaný cuckoo hashing, který je založen na myšlence, že nepoužívám jednu hash funkci, ale dvě (a někdy i více). Výsledek každé funkce odpovídá jedné pozici v tabulce. Při vkládání se pokusím vložit na první pozici a když je obsazená, použiji druhou. Když je na této pozici jiný klíč, ten vezmu a přesunu ho na jeho druhou pozici a tak dále dokud nevystrčím klíč do neobsazeného místa. Pokud jsou hash funkce dobré, kolize řídké a nedojde k vytvoření smyček, počet přestěhovaných elementů při každém vložení je malý a to teoreticky garantuje konstantní časy jednotlivých operací (amortizované, když přihlédnu ke zvětšování tabulky, které probíhá, ne když je tabulka plná, ale když nemůžu vložit nový klíč). Cuckoo hashing se navíc chová rozumně i když je hash tabulka téměř plná a jeho výkon nedegraduje tak drasticky.
Podle toho co jsem četl, Cuckoo hashing se v praxi příliš nepoužívá, protože jeho výkon není z hlediska CPU cache nijak zázračný. Při vkládání musím načíst několik položek, které se nacházejí na prakticky náhodných místech v paměti (to je důsledek dobré hash funkce, která se chová jako PRNG), které s největší pravděpodobností nebudou v cache a z toho důvodu utrpím několik cache-miss. To samé platí při hledání klíče, jen počet načtených míst je v nejhorším případě stejný jako počet hash funkcí.
Chaining hash tabulka na tom také není nijak slavně: Nejprve musím načíst jeden pointer na prakticky náhodné pozici v paměti a pak postupně všechny objekty ze spojového seznamu. Protože články jsou dynamicky alokovány a lezí někde na haldě, každý pointer vede na nepředvídatelné místo v paměti. Pokud je tabulka větší než cache, s největší pravděpodobností toto místo nebude v cache. Navíc je načítání objektů spojového seznamu datově závislé: Musím načíst jeden objekt, abych zjistil pointer na ten další a teprve potom ho můžu načíst. Hardware nemá možnost paralelního přístupu k paměti. Některým z těchto nedostatků se dá předejít, když je spojový seznam částečně odrolovaný (jak je například použito v implementaci hashmap v Go).
Probing verze se vzhledem k hardwaru chová nejlépe ze všech. Sice také potřebuje načíst data ze tří prakticky náhodných míst paměti, ale tyto dotazy jsou nezávislé a hardware je může provést paralelně (paralelní fetch je demonstrován např zde). Změnami algoritmu a vnitřních datových struktur, je možné snížit počet interních polí na dvě nebo dokonce jen na jedno, což má za následek ještě lepší chování z hlediska CPU cache, jak ukazuje například tento článek. Navíc: Kolidující klíče nejsou ve spojovém seznamu, který skáče z místa na místo, ale jsou naskládány v paměti jeden vedle druhého (aspoň v případě lineárního probingu). S velkou pravděpodobností se budou nacházet na jedné cache-line, kterou procesor načte z paměti najednou. A když budu muset projít dlouhý seznam klidujících klíčů, prefetching se postará o to, abych měl data k dispozici včas a bez čekání na pomalou RAM. Počet kolizí může být velký, ale když hardware začne kouzlit, cena jedné kolize bude menší než v případě prolézání kratšího spojového seznamu.
Existují pochopitelně i další způsoby jak implementovat strukturu, která se chová jako asociativní pole. Ty jsou většinou založené na stromech a mají svoje specifické použití, jako například Hash Array Mapped Trie (také tady a tady).
Z předešlých odstavců je jasné, proč je útok na kolizi hashů (v literatuře se používá termín hash flooding) vůbec možný a jak efektivní může být. Všechny varianty hash tabulek se spoléhají na hashovací funkci, která musí být dobrá, rovnoměrná a produkovat málo kolizí. Když tyto předpoklady z nějakých důvodů přestane platit na horizontu se objeví čtyři jezdci apokalypsy a zátěž procesoru vyskočí na 100%. Jak se říká: Tvoje hash tabulka je jenom tak dobrá, jak dobrá je tvoje hash funkce.
Pokud do tabulky vkládám klíče, které mají stejný hash nastane právě takový apokalyptický scénář. A navíc stačí když je hash stejný modulo délka tabulky. V případě řetězení se nové klíče postupně vkládají na konec neustále rostoucího spojového seznamu a v případě probingu se musí projít čím dál tím větší blok obsazených pozic než je nalezeno volné místo, kam se může nováček vložit.
Například PHP pro hashování stringových klíčů používá velice jednoduchou a rychlou funkci DJBX33A, která vypadá takhle:
long DJBX33A(const unsigned char *key) { long hash = 5381; while(*key) hash = 33*hash + *key++; return hash; }
Stačí chvíli střídavě zírat do kódu a do ASCII tabulky, než člověk přijde na několik krátkých
stringů, které mají stejný hash. Jsou to například tyto tři: "~!", "}B", "|c"
Obecně platí, že stačí vybrat takové znaky, pro jejichž pozice v ASCII tabulce platí následující:
a * 33 + b (a+1) * 33 + (b-33) (a+2) * 33 + (b-66) ... (a+i) * 33 + (b-i*33)
Z toho, jak je DJBX33A napsána však vyplývá ještě jedna skutečnost: všechny stringy stejné délky poskládané z těchto střípků mají také stejný hash. Takže následující tři stringy mají také stejný hash:
"~!~!~!", "~!}B|c", "|c|cB|"
Najednou si můžu vygenerovat tolik stringů kolik si moje srdce žádá a ve velkém je začít posílat jako GET nebo POST argumenty a provést tak DOS útok nějaké PHP aplikace, jak bylo demonstrováno na Chaos Communication Congress v roce 2011 a 2012.
PHP tuto zranitelnost napravilo po svém a omezilo počet argumentů předaných
jako POST nebo GET na něco kolem tisíce. Na(ne)štěstí v současnosti každá druhá
webová služba poskytuje JSON API, které může útočník podstrčit speciálně
připravený JSON dokument, který obsahuje jen a pouze zákeřné klíče. Když pak
webová aplikace zavolá json_decode
1 , naparsuje JSON do PHP pole a
sama se tak DOSne.
Pro představu jak velkou škodu může útok napáchat. Vytvoření pole se 100000 neškodnými klíči zabere (v PHP 5.6) 40 milisekund, se stejným počtem zákeřných klíčů 84000 milisekund.
V Javě/Scale jsem po rychlém experimentu v REPLu naměřil hodnoty: 27 ms a 20000 ms. Na konkrétních číslech však moc nezáleží, jde o to, že jedno roste lineárně, druhé kvadraticky.
V PHP verze 7 mají hash tabulky drasticky pozměněnou implementaci.
Přešli z řetězu dynamicky alokovaných spojových seznamů na dvě před-alokovaná
fixní pole, která má výkon velice podobný
probingu. Stále však používají hashovací funkci DJBX33A
. Útok je tedy stále
možný, jen díky zvýšenému výkonu bude o něco málo méně účinný. Podle prvních
nástřelů to vypadá, že je zhruba 10x méně nebezpečný.
A to nemluvím o tom, že celočíselné klíče se berou jako hash, což vede k možnosti útoků, které jsou triviální a zcela devastující.1
Jedinou skutečnou obranou proti tomuto útoku je použít randomizovanou hashovací funkci. Protože i když používám funkci, která rovnoměrně rozkládá hashe a není možné jednoduše před-počítat kolidující klíče a pak z nich poskládat mnohem víc delších klíčů, dostatečně odhodlaný útočník může brute-force metodou před-počítat dostatečné množství kolizí a pak je opakovaně posílat na cílový server. Přesně v duchu rčení pain is temporary, glory is ethernal.
Jak jsou na tom jiné jazyky/runtime?
HHVM standardně používá Murmur3 hash, ale když běží ne stroji, který podporuje SSE4.2, tak začne hashovat pomocí CRC32, která je implementována v hardware a tudíž velice rychlá (bohužel je rychlá i pro útočníky).
Java k hashování stringů používá funkci, která je velice podobná té z PHP:
public int hashCode() { int h = 0; for (char v : value) { h = 31 * h + v; } return h; }
A stejně jako v případě PHP je zcela triviální vygenerovat kolidující stringy:
"1}" // 49 * 31 + 125 = 1644 "2^" // 50 * 31 + 94 = 1644 "3?" // 51 * 31 + 63 = 1644 "4 " // 52 * 31 + 20 = 1644
Integer se (zase podobně jako v PHP) hashuje na sebe sama. Na rozdíl
od PHP se však tato slabina nedá tak jednoduše zneužít, protože int má malý rozsah.
V javě má 4 bajty a něco přes 4 miliardy možných hodnot, takže v nejhorším
případě do hash tabulky můžu vložit 65536 klíčů, jejichž hash je dělitelný
65536 a hash modulo velikost tabulky
bude stejný.
Long se hashuje takto:
public static int hashCode(long value) { return (int)(value ^ (value >>> 32)); }
To vypadá rozumně, ale
(long) x << 32 | (long) x
je nula pro libovolné x. Když jsou horní a dolní čtyři bajty stejné, jejich xor je 0.
Zkuste si to sami a uvidíte jak se roztočí větrák na procesoru:
val map = new collection.mutable.HashMap[Long, Int]() for (i <- 0 until 100000) { val h = (i.toLong << 32 | i.toLong) map.put(h, 1) }
Problém může také nastat, když obě poloviny longu používají jen pár dolních bitů. Když používají jen 10 bitů (tedy čísla v rozmezí 0 - 1024), můžou reprezentovat milion kombinací, ale jejich hash je jen v onom desetibitovém rozmezí 0 - 1024. V takovém případě se bude hashovat jen do malé částí hash-tabulky a všechno bude (opět) velice pomalé. Tenhle případ jsem poznal na vlastní kůži, když jsem se snažil udělat něco chytrého.
Java v některé nedávné verzi přinesla jednu vychytávku: Pokud jeden slot obsahuje víc jak 8 kolizí, je spojový seznam přestavěn na binární red-black strom. Ten v patologických případech zredukuje lineární časovou složitost na logaritmickou za cenu nepříjemně komplikovaného kódu.
C# podle všeho používá celkem jednoduchou multiplikativní funkci.
val hash1, hash2 = 5381 while (i < str.length) { hash1 = (hash1 * 33) + str(i) hash2 = (hash2 * 33) + str(i+1) i += 2 } hash1 + (hash2 * 1566083941)
Když se nechci uchylovat k bruteforce řešení, je spočítání kolidujících stringů poměrně jednoduché.
Například tyto dva kolidují: "*_O_", "+_n_"
.
Pokud se však zahledíte do odkazovaného kódu, uvidíte tam za několika IFDEFy nějaké ty XORy a možná i nějakou tu randomizaci. Těžko říct o co přesně tam jde.
Ať už je ale hash funkce libovolná, útočník může vždycky bruteforce vypočítat kolidující řetězce. Když jich zkusí moře, dostane pár kapek, a to může být víc než dost.
Jediným systematickým řešením je použít randomizovanou hash funkci. Taková funkce má několik skrytých argumentů (jsou např. vygenerovány na začátku běhu programu), které změní výstup hashovací funkce tak, že když s jedním argumentem mají dvě hodnoty stejný hash, s jiným mají vzájemně odlišné hashe.
Jako špatný příklad příklad uvedu PHP funkci DJBX33A
. V té se na začátku
vyskytuje magická konstanta 5381. Když bych randomizoval tuto konstantu, hashe
budou jiné, ale jejich korelace zůstanou.
Pokud platí:
ϝ(a, 5381) = ϝ(b, 5381)
Tak bude také platit
ϝ(a, s) = ϝ(b, s)
Hashe se změní, kolize zůstanou.
Je nutné použít randomizovanou funkci, která tak byla navržena, jako je třeba
SipHash (podrobně popsaná v tomto paperu). Ta je jednak
rychlá (pomalejší než jednoduchá DJBX33A
, ale mnohem rychlejší než třeba MD5) a
zároveň poskytuje všechno dobré kolem randomizace. Útočník je schopný provést
hash flood útok jen pokud zná náhodných 128 bitů, které SipHash používá jako seed, ale
ty se můžou měnit každou minutu nebo při každém HTTP požadavku. Útočník jednak
nemá jak zjistit tento seed a i kdyby ho zjistil2 , má jen limitované
možnosti, jak ho uplatnit.
V případě PHP je změna hashovací funkce triviální, protože na rozdíl od světa Javy není součástí veřejného API a její změna nemůže rozbít kód, který na ní závisí.
Jako další ukázka proč jsou hashovací funkce důležité může posloužit příklad Bloom filtrů. Bloom filtr je pravděpodobnostní datová struktura pro test členství v množině, která interně používá několik hashovacích funkcí. Nedávno jsem psal vlastní maličkou implementaci bloom filtru do knihovny sketches a použil jsem stejné hashovací schéma jako v knihovně Breeze založené na MurMur3 hashi. Při testování se ukázalo, že výsledný filtr generuje 1000000000x více falešných pozitiv, než by statisticky měl. To byla velice špatná zpráva, protože to dělalo tuto strukturu mnohem méně přesnou a mnohem méně užitečnou. Později se ukázalo, že za tuto vadu může právě použití MurMur3 hashe, který očividně neprodukuje uniformní rozložení a nepatří tedy do rodiny univerzálních hashovacích funkcí. Při použití dobré univerzální hashovací funkci problém zmizel.
Na závěr přidám dvě perličky:
Cache procesoru je také (překvapivě) organizována jako hash-tabulka - obsahuje několik slotů (řekněme 64) a každý slot může obsahovat 8 cache line (každá má 64 bajtů). Hashovací funkce vypadá takto: vezme fyzickou adresu, zahodí 6 nejnižších bitů a vezme 6 dalších. Výsledkem je index slotu v němž bude hledat nebo do něhož bude ukládat data.
Když program přistupuje na adresy s velice specifickým rozestupem, cache alising v podstatě udělá hash flood CPU cache, jak je ukázáno ve What Every Programmer Should Know About Memory nebo v Binary Search Is a Pathological Case for Caches. Následující graf pochází právě z WEPSKAM.
Za pozornost stojí také Robin Hood Hashing. Jde o variantu probing hashování, kde v nejhorším případě mají operace logaritmickou složitost. RH hashování toho docílí tím, že průměruje počet slotů, které je potřeba prohledat ve stylu Robina Hooda - bohatým bere (krátká probing cesta) a chudým dává (dlouhá cesta). Elementy v jenom běhu jsou tedy seřazeny podle délky probe cesty (nebo dokonce v některých variantách podle hashe samotnho), při vkládáná se tedy provádí inserion sort a hledání je možné předčasně ukončit i v případě, když element není v tabulce přítomen a dále to vede k velice jednoduchému a rychlému zvětšování tabulky a hromadnému vkládání, kterému předchází radix sort.
Tohle všechno znamená, že jsou všechny operace rychlé a tabulka se chová rozumně, i když je z velké části (klidně i 90%) zaplněná. Jak o tom teď píšu, napadá mě, že bych měl napsat vlastní implementaci ve Scale a přidat ji do sketches.
A to je všechno. Pokud jste se dočetli až sem, nejspíš toho víte o hash funkcích a jejich kolizích víc, než jste kdy chtěli vědět.
Dále k tématu:
- Advanced Data Structures - Dictionaries
- Hash functions: An empirical comparison
- Five Myths about Hash Tables
- Hash Collision Probabilities
- Cuckoo Filters So now that we've proven theoretically that this won't work, how could it work in practice?
- PHP compaction hell: Kdo neamortizuje, spláče nad O(n²)
- Load Balancing and the Power of Hashing
- Throw away the keys: Easy, Minimal Perfect Hashing
- Hopscotch hashing
- Leapfrog Probing
- O kolizích hashů v Javě se letmo zmiňuje Aleksey Shipilёv v přednášce java.lang.String Catechism.
- Tady patří díky Janu-Sebastianovi Fabíkovi, který krátce potom, co jsem dopřednášel, přišel na to, že
json_decode
je částečně odolný nejtriviálnějšímu útoku, kdy se serveru pošle pole s speciálně připravenými numerickými klíči. Kdyžjson_decode
bez extra parametrů narazí na JSON objekt, naparsuje ho jako PHP objekt. PHP objekty konvertují všechny atributy na string a tedy útok numerickými klíči nemá žádný dopad. Když se všakjson_decode
předá druhý argument$assoc
, tak JSON objekty naparsuje na pole a jsme zpátky odkud jsme vyšli. V obou případech je však zranitelný, když mu podstrčíme json s kolidujícími stringovými klíči. - např. Python používal podobnou funkci, ale později se ukázalo, že je možné zjistit tajný seed.
- Přímo je možné smazat elementy na konci řady, tedy ty, které mají napravo neobsazenou pozici. Stejně tak je možné vložit element do smazané pozice. Tyto dvě zkratky nerozbijí hledání, protože nezpřetrhají řady obsazených pozic.