funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Kolize hashů pro mírně pokročilé

1. 2. 2016 — k47

Hash ta­bulka je jedna ze zá­klad­ních da­to­vých struk­tur, byla vy­na­le­zena roku 1953 a všichni, kdo pro­gra­mo­vání viděli aspoň z rych­líku, ji velice dobře znají. Hash ta­bulky (někdy také ha­shmapy nebo slov­níky/dicti­o­nary) umí vy­hle­dat, přidat nebo smazat hod­notu aso­ci­o­va­nou s ur­či­tým klíčem v kon­stant­ním čase. Všechno je možné jen díky jed­nomu velice chyt­rému triku – po­u­žití ha­sho­vací funkce, která klíč, ať už je ja­ké­ho­koli typu a ve­li­kosti, zob­razí na číslo. To je potom vy­u­žito k ad­re­so­vání do oby­čej­ného plo­chého pole, které všichni známe a mi­lu­jeme.

Tohle všechno fun­guje skoro až zá­zračně. Tedy aspoň do oka­mžiku, kdy to pře­stane. Pak se do­stá­váme do vel­kých pro­blémů.

Všechno záleží na po­u­žité ha­sho­vací funkci. Ta by měla v ide­ál­ním pří­padě být pseudo-ná­hodná – měla by pro­du­ko­vat hashe, které jsou rov­no­měrně roz­lo­žené v oboru hodnot a které ne­za­cho­vá­vají ko­re­lace mezi vstup­ními hod­no­tami, kdy např. hashe po­sloup­nosti čísel také při­po­mí­nají po­sloup­nost. Jinými slovy: mělo by jít ale­spoň o jednu z rodiny uni­ver­zál­ních ha­sho­va­cích funkcí.

Pokud ha­sho­vací funkce pro­du­kuje nad­prů­měrné množ­ství stej­ných hashů pro různé hod­noty, nebo je před­ví­da­telná a hod­noty s ko­li­du­jí­cími hashi může někdo, jehož záměry jsou méně než upřímné, snadno spo­čí­tat, hash-ta­bulky na­jed­nou začnou vy­ka­zo­vat pa­to­lo­gické cho­vání, kdy dříve kon­stantní ope­race po­tře­bují li­ne­ární čas úměrný ve­li­kosti ta­bulky. Může tak jít o velice efek­tivní DOS útok.

Abych to osvět­lil, musím se po­no­řit do kr­va­vých de­tailů.


Hash ta­bulky mají tři zá­kladní va­ri­anty: cha­i­ning, pro­bingcuckoo ha­shing. Cha­i­ning a pro­bing se také ozna­čují jako open ha­shingopen ad­d­res­sing, ale tohle ozna­čení nemám rád, pro­tože si nikdy nemůžu vzpo­me­nout, které je které.

Ře­tě­zící (cha­i­ning) va­ri­anta se za­kládá na poli poin­terů (buckets). Každý z nich uka­zuje na spo­jový seznam, jehož každý článek ob­sa­huje klíč, od­po­ví­da­jící hod­notu a poin­ter na ná­sle­du­jí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 od­po­ví­da­jící pozici v poli poin­terů index = hash % arraySize. Pokud je daná pozice prázdná, vy­tvo­řím článek a na­sta­vím poin­ter na pozici index, aby na něj uka­zo­val. Pokud už je index ob­sa­zený, vy­tvo­řený článek při­po­jím na konec se­znamu.

Aby tohle fun­go­valo v kon­stant­ním čase, kolize musejí být ne­prav­dě­po­dobné. Pokud to platí, vět­šina spo­jo­vých se­znamů ob­sa­huje jen málo článků (v prů­měru n/m, kde m je ve­li­kost ta­bulky a n počet vlo­že­ných ele­mentů) a pole poin­terů má délku úměr­nou počtu po­lo­žek v ta­bulce. V praxi jde o určitý malý ná­so­bek a je do­vo­lené jen určité ma­xi­mální za­pl­nění ta­bulky. Když je tato mez pře­kro­čena, ta­bulka se zvětší na dvoj­ná­so­bek, všechny klíče se re­ha­shují na nové pozice a řetězy kolizí se zkrátí. Zvět­šo­vání o ná­so­bek ga­ran­tuje amor­ti­zo­vaný kon­stantní čas ope­race vklá­dání.


Pro­bing va­ri­anta ty­picky po­u­žívá tři in­terní pole – jedno ob­sa­huje klíče, druhé od­po­ví­da­jící hod­noty a třetí ozna­čuje sma­zané po­ložky.

Pokud chci vložit klíč, stejně jako v mi­nu­lém pří­padě spo­čí­tám jeho hash a z něho od­po­ví­da­jící index v tro­jici stejně dlou­hých polí. Když je od­po­ví­da­jící místo prázdné, klíč a hod­notu tam jed­no­duše vložím. Pokud je však místo už za­brané, vložím klíč a hod­notu o jedno místo do­prava (linear pro­bing), o 2i míst do­prava (qua­d­ra­tic pro­bing) nebo o počet míst vy­po­čí­taný jinou ha­sho­vací funkcí (double ha­shing). Pokud je plno i tam, zkou­ším další místa na­pravo dokud ne­na­jdu volný flek.

Když chci najít určitý klíč, spo­čí­tám hash a z něho pozici, na které by se měl na­chá­zet. Pokud se na tomto místě na­chází, skon­čím s úspě­chem. Pokud se tam na­chází jiný klíč, zkusím to o jedno místo vpravo. Takto po­kra­čuji, dokud ne­na­jdu po­ža­do­vaný klíč, sma­zaná místa ig­no­ruji. Když na­ra­zím na prázd­nou hod­notu, pro­hlá­sím, že klíč nebyl na­le­zen. Šipky v di­a­gramu uka­zují, kde se na­chází další klíč se stej­ným hashem. Jak je vidět tento blok nemusí být spo­jitý 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, po­ku­sím se nalézt místo, kde se na­chází (postup stejný jako v mi­nu­lém od­stavci) a potom, co ho ob­je­vím, ve třetím poli ozna­čím danou pozici jako sma­za­nou (jde o pole boolů nebo o bitmapu). Kdy­bych klíče mazal tak, že bych od­po­ví­da­jící pozici v prv­ních dvou polích jen na­sta­vil na null, rozbil bych hle­dání, pro­tože bych tak do spo­ji­tých bloků vnesl díry a hle­dání by při na­le­zení této díry skon­čilo a ne­mu­selo by se dostat ke správ­ným hod­no­tám, které se můžou na­chá­zet těsně za touto dírou.3

Kon­stantní čas pro všechny ope­race je za­ru­čen opět tím, že hash funkce ne­ge­ne­ruje kolize a rov­no­měrně roz­kládá hashe. V dů­sledku toho budou sek­vence, které je po­třeba projít při hle­dání klíčů, ro­zumně krátké. Tři zmí­něná pole mají délku která je opět úměrná počtu po­lo­žek v ta­bulce, i když bývají větší než u cha­i­ningu, pro­tože efek­ti­vita pro­bingu dra­ma­ticky de­gra­duje, když se za­pl­nění ta­bulky blíží 100 pro­cen­tům. Dlouhé běhy ob­sa­ze­ných pozic, kam spadne mnoho hashů, která ná­ho­dou byly blízko sebe, se ještě více pro­dlu­žují a s nimi i počet míst, které je třeba projít. Ne­stačí jen jako v pří­padě cha­i­ningu projít jeden spo­jový seznam od­po­ví­da­jící jed­nomu hashi, ale blok od­po­ví­da­jící ně­ko­lika hashům.

(Tech­nicky vzato: Ha­sho­vací funkce po­u­žitá pro linear pro­bing musí být aspoň 5-in­de­pen­dent nebo musí jít o ta­bu­lation ha­shing, jinak není ga­ran­to­ván kon­stantní čas. Více v tomto videu.)


Třetí va­ri­an­tou je tak­zvaný cuckoo ha­shing, který je za­lo­žen na myš­lence, že ne­po­u­ží­vám jednu hash funkci, ale dvě (a někdy i více). Vý­sle­dek každé funkce od­po­vídá jedné pozici v ta­bulce. Při vklá­dání se po­ku­sím vložit na první pozici a když je ob­sa­zená, po­u­žiji druhou. Když je na této pozici jiný klíč, ten vezmu a pře­sunu ho na jeho druhou pozici a tak dále dokud ne­vy­str­čím klíč do ne­ob­sa­ze­ného místa. Pokud jsou hash funkce dobré, kolize řídké a ne­do­jde k vy­tvo­ření smyček, počet pře­stě­ho­va­ných ele­mentů při každém vlo­žení je malý a to te­o­re­ticky ga­ran­tuje kon­stantní časy jed­not­li­vých ope­rací (amor­ti­zo­vané, když při­hlédnu ke zvět­šo­vání ta­bulky, které pro­bíhá, ne když je ta­bulka plná, ale když nemůžu vložit nový klíč). Cuckoo ha­shing se navíc chová ro­zumně i když je hash ta­bulka téměř plná a jeho výkon ne­de­gra­duje tak dras­ticky.

Podle toho co jsem četl, Cuckoo ha­shing se v praxi příliš ne­po­u­žívá, pro­tože jeho výkon není z hle­diska CPU cache nijak zá­zračný. Při vklá­dání musím načíst ně­ko­lik po­lo­žek, které se na­chá­zejí na prak­ticky ná­hod­ných mís­tech v paměti (to je dů­sle­dek dobré hash funkce, která se chová jako PRNG), které s nej­větší prav­dě­po­dob­ností ne­bu­dou v cache a z toho důvodu utrpím ně­ko­lik cache-miss. To samé platí při hle­dání klíče, jen počet na­čte­ných míst je v nej­hor­ším pří­padě stejný jako počet hash funkcí.

Cha­i­ning hash ta­bulka na tom také není nijak slavně: Nej­prve musím načíst jeden poin­ter na prak­ticky ná­hodné pozici v paměti a pak po­stupně všechny ob­jekty ze spo­jo­vého se­znamu. Pro­tože články jsou dy­na­micky alo­ko­vány a lezí někde na haldě, každý poin­ter vede na ne­před­ví­da­telné místo v paměti. Pokud je ta­bulka větší než cache, s nej­větší prav­dě­po­dob­ností toto místo nebude v cache. Navíc je na­čí­tání ob­jektů spo­jo­vého se­znamu datově zá­vislé: Musím načíst jeden objekt, abych zjis­til poin­ter na ten další a teprve potom ho můžu načíst. Hard­ware nemá mož­nost pa­ra­lel­ního pří­stupu k paměti. Ně­kte­rým z těchto ne­do­statků se dá pře­de­jít, když je spo­jový seznam čás­tečně odro­lo­vaný (jak je na­pří­klad po­u­žito v im­ple­men­taci ha­shmap v Go).

Pro­bing verze se vzhle­dem k hard­waru chová nej­lépe ze všech. Sice také po­tře­buje načíst data ze tří prak­ticky ná­hod­ných míst paměti, ale tyto dotazy jsou ne­zá­vislé a hard­ware je může pro­vést pa­ra­lelně (pa­ra­lelní fetch je de­mon­stro­ván např zde). Změ­nami al­go­ritmu a vnitř­ních da­to­vých struk­tur, je možné snížit počet in­ter­ních polí na dvě nebo do­konce jen na jedno, což má za ná­sle­dek ještě lepší cho­vání z hle­diska CPU cache, jak uka­zuje na­pří­klad tento článek. Navíc: Ko­li­du­jící klíče nejsou ve spo­jo­vém se­znamu, který skáče z místa na místo, ale jsou na­sklá­dány v paměti jeden vedle dru­hého (aspoň v pří­padě li­ne­ár­ního pro­bingu). S velkou prav­dě­po­dob­ností se budou na­chá­zet na jedné cache-line, kterou pro­ce­sor načte z paměti na­jed­nou. A když budu muset projít dlouhý seznam kli­du­jí­cích klíčů, pre­fet­ching se po­stará o to, abych měl data k dis­po­zici včas a bez čekání na po­ma­lou RAM. Počet kolizí může být velký, ale když hard­ware začne kouz­lit, cena jedné kolize bude menší než v pří­padě pro­lé­zání krat­šího spo­jo­vého se­znamu.

Exis­tují po­cho­pi­telně i další způ­soby jak im­ple­men­to­vat struk­turu, která se chová jako aso­ci­a­tivní pole. Ty jsou vět­ši­nou za­lo­žené na stro­mech a mají svoje spe­ci­fické po­u­žití, jako na­pří­klad Hash Array Mapped Trie (také tadytady).


Z pře­de­šlých od­stavců je jasné, proč je útok na kolizi hashů (v li­te­ra­tuře se po­u­žívá termín hash flo­o­ding) vůbec možný a jak efek­tivní může být. Všechny va­ri­anty hash ta­bu­lek se spo­lé­hají na ha­sho­vací funkci, která musí být dobrá, rov­no­měrná a pro­du­ko­vat málo kolizí. Když tyto před­po­klady z ně­ja­kých důvodů pře­stane platit na ho­ri­zontu se objeví čtyři jezdci apo­ka­ly­psy a zátěž pro­ce­soru vy­skočí na 100%. Jak se říká: Tvoje hash ta­bulka je jenom tak dobrá, jak dobrá je tvoje hash funkce.

Pokud do ta­bulky vklá­dám klíče, které mají stejný hash na­stane právě takový apo­ka­lyp­tický scénář. A navíc stačí když je hash stejný modulo délka ta­bulky. V pří­padě ře­tě­zení se nové klíče po­stupně vklá­dají na konec ne­u­stále ros­tou­cího spo­jo­vého se­znamu a v pří­padě pro­bingu se musí projít čím dál tím větší blok ob­sa­ze­ných pozic než je na­le­zeno volné místo, kam se může no­vá­ček vložit.

Na­pří­klad PHP pro ha­sho­vání strin­go­vých klíčů po­u­žívá velice jed­no­du­chou a rych­lou 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 ta­bulky, než člověk přijde na ně­ko­lik krát­kých stringů, které mají stejný hash. Jsou to na­pří­klad tyto tři: "~!", "}B", "|c"

Obecně platí, že stačí vybrat takové znaky, pro je­jichž pozice v ASCII ta­bulce platí ná­sle­du­jí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 na­psána však vy­plývá ještě jedna sku­teč­nost: všechny stringy stejné délky po­sklá­dané z těchto střípků mají také stejný hash. Takže ná­sle­du­jící tři stringy mají také stejný hash:

"~!~!~!", "~!}B|c", "|c|cB|"

Na­jed­nou si můžu vy­ge­ne­ro­vat tolik stringů kolik si moje srdce žádá a ve velkém je začít po­sí­lat jako GET nebo POST ar­gu­menty a pro­vést tak DOS útok nějaké PHP apli­kace, jak bylo de­mon­stro­váno na Chaos Com­mu­ni­cation Con­gress v roce 20112012.

PHP tuto zra­ni­tel­nost na­pra­vilo po svém a ome­zilo počet ar­gu­mentů pře­da­ných jako POST nebo GET na něco kolem tisíce. Na(ne)štěstí v sou­čas­nosti každá druhá webová služba po­sky­tuje JSON API, které může útoč­ník pod­str­čit spe­ci­álně při­pra­vený JSON do­ku­ment, který ob­sa­huje jen a pouze zá­keřné klíče. Když pak webová apli­kace zavolá json_decode1, na­par­suje JSON do PHP pole a sama se tak DOSne.

Pro před­stavu jak velkou škodu může útok na­páchat. Vy­tvo­ření pole se 100000 ne­škod­nými klíči zabere (v PHP 5.6) 40 mi­li­sekund, se stej­ným počtem zá­keř­ných klíčů 84000 mi­li­sekund.

V Javě/Scale jsem po rych­lém ex­pe­ri­mentu v REPLu na­mě­řil hod­noty: 27 ms a 20000 ms. Na kon­krét­ních čís­lech však moc ne­zá­leží, jde o to, že jedno roste li­ne­árně, druhé kva­d­ra­ticky.

V PHP verze 7 mají hash ta­bulky dras­ticky po­změ­ně­nou im­ple­men­taci. Přešli z řetězu dy­na­micky alo­ko­va­ných spo­jo­vých se­znamů na dvě před-alo­ko­vaná fixní pole, která má výkon velice po­dobný pro­bingu. Stále však po­u­ží­vají ha­sho­vací funkci DJBX33A. Útok je tedy stále možný, jen díky zvý­še­nému výkonu bude o něco málo méně účinný. Podle prv­ních ná­střelů to vypadá, že je zhruba 10x méně ne­bez­pečný.

A to ne­mlu­vím o tom, že ce­lo­čí­selné klíče se berou jako hash, což vede k mož­nosti útoků, které jsou tri­vi­ální a zcela de­vas­tu­jící.1

Je­di­nou sku­teč­nou obra­nou proti tomuto útoku je použít ran­do­mi­zo­va­nou ha­sho­vací funkci. Pro­tože i když po­u­ží­vám funkci, která rov­no­měrně roz­kládá hashe a není možné jed­no­duše před-po­čí­tat ko­li­du­jící klíče a pak z nich po­sklá­dat mnohem víc del­ších klíčů, do­sta­tečně od­hod­laný útoč­ník může brute-force me­to­dou před-po­čí­tat do­sta­tečné množ­ství kolizí a pak je opa­ko­vaně po­sí­lat na cílový server. Přesně v duchu rčení pain is tem­po­rary, glory is ether­nal.


Jak jsou na tom jiné jazyky/run­time?

HHVM stan­dardně po­u­žívá Murmur3 hash, ale když běží ne stroji, který pod­po­ruje SSE4.2, tak začne ha­sho­vat pomocí CRC32, která je im­ple­men­to­vána v hard­ware a tudíž velice rychlá (bo­hu­žel je rychlá i pro útoč­níky).

Java k ha­sho­vání stringů po­u­žívá funkci, která je velice po­dobná 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 tri­vi­ální vy­ge­ne­ro­vat ko­li­du­jící stringy:

"1}" // 49 * 31 + 125 = 1644
"2^" // 50 * 31 + 94  = 1644
"3?" // 51 * 31 + 63  = 1644
"4 " // 52 * 31 + 20  = 1644

In­te­ger se (zase po­dobně jako v PHP) ha­shuje na sebe sama. Na rozdíl od PHP se však tato sla­bina nedá tak jed­no­duše zne­u­žít, pro­tože int má malý rozsah. V javě má 4 bajty a něco přes 4 mi­li­ardy mož­ných hodnot, takže v nej­hor­ším pří­padě do hash ta­bulky můžu vložit 65536 klíčů, je­jichž hash je dě­li­telný 65536 a hash modulo velikost tabulky bude stejný.

Long se ha­shuje takto:

public static int hashCode(long value) {
  return (int)(value ^ (value >>> 32));
}

To vypadá ro­zumně, ale

(long) x << 32 | (long) x

je nula pro li­bo­volné x. Když jsou horní a dolní čtyři bajty stejné, jejich xor je 0.

Zkuste si to sami a uvi­díte jak se roz­točí větrák na pro­ce­soru:

val map = new collection.mutable.HashMap[Long, Int]()

for (i <- 0 until 100000) {
  val h = (i.toLong << 32 | i.toLong)
  map.put(h, 1)
}

Pro­blém může také nastat, když obě po­lo­viny longu po­u­ží­vají jen pár dol­ních bitů. Když po­u­ží­vají jen 10 bitů (tedy čísla v roz­mezí 0 – 1024), můžou re­pre­zen­to­vat milion kom­bi­nací, ale jejich hash je jen v onom de­se­ti­bi­to­vém roz­mezí 0 – 1024. V ta­ko­vém pří­padě se bude ha­sho­vat jen do malé částí hash-ta­bulky 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 chyt­rého.

Java v ně­které ne­dávné verzi při­nesla jednu vy­chy­távku: Pokud jeden slot ob­sa­huje víc jak 8 kolizí, je spo­jový seznam pře­sta­věn na bi­nární red-black strom. Ten v pa­to­lo­gic­kých pří­pa­dech zre­du­kuje li­ne­ární ča­so­vou slo­ži­tost na lo­ga­rit­mic­kou za cenu ne­pří­jemně kom­pli­ko­va­ného kódu.

C# podle všeho po­u­žívá celkem jed­no­du­chou mul­tipli­ka­tivní 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 uchy­lo­vat k bru­te­force řešení, je spo­čí­tání ko­li­du­jí­cích stringů po­měrně jed­no­du­ché. Na­pří­klad tyto dva ko­li­dují: "*_O_", "+_n_".

Pokud se však za­hle­díte do od­ka­zo­va­ného kódu, uvi­díte tam za ně­ko­lika IFDEFy nějaké ty XORy a možná i ně­ja­kou tu ran­do­mi­zaci. Těžko říct o co přesně tam jde.


Ať už je ale hash funkce li­bo­volná, útoč­ník může vždycky bru­te­force vy­po­čí­tat ko­li­du­jící ře­tězce. Když jich zkusí moře, do­stane pár kapek, a to může být víc než dost.

Je­di­ným sys­te­ma­tic­kým ře­še­ním je použít ran­do­mi­zo­va­nou hash funkci. Taková funkce má ně­ko­lik skry­tých ar­gu­mentů (jsou např. vy­ge­ne­ro­vány na za­čátku běhu pro­gramu), které změní výstup ha­sho­vací funkce tak, že když s jedním ar­gu­men­tem mají dvě hod­noty stejný hash, s jiným mají vzá­jemně od­lišné hashe.

Jako špatný pří­klad pří­klad uvedu PHP funkci DJBX33A. V té se na za­čátku vy­sky­tuje ma­gická kon­stanta 5381. Když bych ran­do­mi­zo­val tuto kon­stantu, hashe budou jiné, ale jejich ko­re­lace zů­sta­nou.

Pokud platí:

ϝ(a, 5381) = ϝ(b, 5381)

Tak bude také platit

ϝ(a, s) = ϝ(b, s)

Hashe se změní, kolize zů­sta­nou.

Je nutné použít ran­do­mi­zo­va­nou funkci, která tak byla na­vr­žena, jako je třeba Si­pHash (po­drobně po­psaná v tomto paperu). Ta je jednak rychlá (po­ma­lejší než jed­no­du­chá DJBX33A, ale mnohem rych­lejší než třeba MD5) a zá­ro­veň po­sky­tuje všechno dobré kolem ran­do­mi­zace. Útoč­ník je schopný pro­vést hash flood útok jen pokud zná ná­hod­ných 128 bitů, které Si­pHash po­u­žívá jako seed, ale ty se můžou měnit každou minutu nebo při každém HTTP po­ža­davku. Útoč­ník jednak nemá jak zjis­tit tento seed a i kdyby ho zjis­til 2, má jen li­mi­to­vané mož­nosti, jak ho uplat­nit.

V pří­padě PHP je změna ha­sho­vací funkce tri­vi­ální, pro­tože na rozdíl od světa Javy není sou­částí ve­řej­ného API a její změna nemůže rozbít kód, který na ní závisí.


Jako další ukázka proč jsou ha­sho­vací funkce dů­le­žité může po­slou­žit pří­klad Bloom filtrů. Bloom filtr je prav­dě­po­dob­nostní datová struk­tura pro test člen­ství v mno­žině, která in­terně po­u­žívá ně­ko­lik ha­sho­va­cích funkcí. Ne­dávno jsem psal vlastní ma­lič­kou im­ple­men­taci bloom filtru do knihovny sket­ches a použil jsem stejné ha­sho­vací schéma jako v knihovně Breeze za­lo­žené na MurMur3 hashi. Při tes­to­vání se uká­zalo, že vý­sledný filtr ge­ne­ruje 1000000000x více fa­leš­ných po­zi­tiv, než by sta­tis­ticky měl. To byla velice špatná zpráva, pro­tože to dělalo tuto struk­turu mnohem méně přes­nou a mnohem méně uži­teč­nou. Poz­ději se uká­zalo, že za tuto vadu může právě po­u­žití MurMur3 hashe, který oči­vidně ne­pro­du­kuje uni­formní roz­lo­žení a ne­patří tedy do rodiny uni­ver­zál­ních ha­sho­va­cích funkcí. Když jsem použil dobrou uni­ver­zální ha­sho­vací funkci, pro­blém zmizel.


Na závěr přidám dvě per­ličky:

Cache pro­ce­soru je také (pře­kva­pivě) or­ga­ni­zo­vána jako hash-ta­bulka – ob­sa­huje ně­ko­lik slotů (řek­něme 64) a každý slot může ob­sa­ho­vat 8 cache line (každá má 64 bajtů). Ha­sho­vací funkce vypadá takto: vezme fy­zic­kou adresu, zahodí 6 nej­niž­ších bitů a vezme 6 dal­ších. Vý­sled­kem je index slotu v němž bude hledat nebo do něhož bude uklá­dat data.

Když pro­gram při­stu­puje na adresy s velice spe­ci­fic­kým ro­ze­stu­pem, cache ali­sing v pod­statě udělá hash flood CPU cache, jak je uká­záno ve What Every Pro­gra­m­mer Should Know About Memory nebo v Binary Search Is a Patho­lo­gi­cal Case for Caches. Ná­sle­du­jící graf po­chází právě z WEPSKAM.

Za po­zor­nost stojí také Robin Hood Ha­shing. Jde o va­ri­antu pro­bing ha­sho­vání, kde v nej­hor­ším pří­padě mají ope­race lo­ga­rit­mic­kou slo­ži­tost. RH ha­sho­vání toho docílí tím, že prů­mě­ruje počet slotů, které je po­třeba pro­hle­dat ve stylu Robina Hooda – bo­ha­tým bere (krátká pro­bing cesta) a chudým dává (dlouhá cesta). Ele­menty v jenom běhu jsou tedy se­řa­zeny podle délky probe cesty (nebo do­konce v ně­kte­rých va­ri­an­tách podle hashe sa­mot­nho), při vklá­dáná se tedy pro­vádí in­se­rion sort a hle­dání je možné před­časně ukon­čit i v pří­padě, když ele­ment není v ta­bulce pří­to­men a dále to vede k velice jed­no­du­chému a rych­lému zvět­šo­vání ta­bulky a hro­mad­nému vklá­dání, kte­rému před­chází radix sort.

Tohle všechno zna­mená, že jsou všechny ope­race rychlé a ta­bulka se chová ro­zumně, i když je z velké části (klidně i 90%) za­pl­něná. Jak o tom teď píšu, napadá mě, že bych měl napsat vlastní im­ple­men­taci ve Scale a přidat ji do sket­ches.


A to je všechno. Pokud jste se do­četli až sem, nej­spíš toho víte o hash funk­cích a jejich ko­li­zích víc, než jste kdy chtěli vědět.


Dále k tématu:


  1. Tady patří díky Janu-Se­bas­ti­a­novi Fa­bí­kovi, který krátce potom, co jsem do­před­ná­šel, přišel na to, že json_decode je čás­tečně odolný nej­tri­vi­ál­něj­šímu útoku, kdy se ser­veru pošle pole s spe­ci­álně při­pra­ve­nými nu­me­ric­kými klíči. Když json_decode bez extra pa­ra­me­trů narazí na JSON objekt, na­par­suje ho jako PHP objekt. PHP ob­jekty kon­ver­tují všechny atri­buty na string a tedy útok nu­me­ric­kými klíči nemá žádný dopad. Když se však json_decode předá druhý ar­gu­ment $assoc, tak JSON ob­jekty na­par­suje na pole a jsme zpátky odkud jsme vyšli. V obou pří­pa­dech je však zra­ni­telný, když mu pod­str­číme json s ko­li­du­jí­cími strin­go­vými klíči.
  2. např. Python po­u­ží­val po­dob­nou funkci, ale poz­ději se uká­zalo, že je možné zjis­tit tajný seed.
  3. Přímo je možné smazat ele­menty na konci řady, tedy ty, které mají na­pravo ne­ob­sa­ze­nou pozici. Stejně tak je možné vložit ele­ment do sma­zané pozice. Tyto dvě zkratky ne­roz­bijí hle­dání, pro­tože ne­zpře­tr­hají řady ob­sa­ze­ných pozic.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články