Zraniteľnosť hash tabuliek umožňuje mimoriadne efektívny DoS útok na webové servery

DSL.sk, 30.12.2011

Vo väčšine programovacích jazykov pre webové stránky sa nachádza vážna zraniteľnosť, ktorá umožňuje uskutočniť mimoriadne efektívny Denial-of-Service útok proti webovým serverom.

Na zraniteľnosť upozornila na bezpečnostnej konferencii Chaos Communication Congress dvojica Alexander Klink a Julian Walde.

Zraniteľnosť sa nachádza v implementácii tzv. hashovacích tabuliek v programovacích jazykoch, teda dátových štruktúr používaných na efektívne ukladanie a prácu s dátami vo formáte dvojíc kľúč a hodnota, a najmä v nich využívaných hashovacích funkciách.

Výhodou hashovacích tabuliek sú rýchle operácie, keď v priemernom prípade vloženie, hľadanie aj mazanie jedného prvku trvá konštantný čas. Rýchlosť je dosahovaná vďaka vypočítaniu hash hodnoty kľúča, ktorá sa používa na indexovanie umiestnenia dvojice kľúč a hodnota v interných dátových štruktúrach.

Ako ale zistili Klink a Walde, hashovacie funkcie využívané na tento účel sú vo väčšine programovacích jazykov pre webové stránky zraniteľné, ľahko je možné vytvoriť kolízie s rovnakou hodnotou hashovacej funkcie pre veľké množstvo kľúčov a vkladanie takýchto kľúčov do hashovacích tabuliek následne pre ich implementáciu pomocou zoznamov vyžaduje pre n kľúčov rádovo až n ^ 2 operácií namiesto rádovo n operácií.

To je pri stovkách tisícov kľúčov už výrazná záťaž pre moderné procesory. Zneužiť túto zraniteľnosť je pritom mimoriadne jednoduché, keď už len poslanie dvojíc takýchto dát ako parametrov webového POST dotazu vyvolá vo väčšine jazykov ich vloženie do hashovacej tabuľky.

Napríklad u PHP webový POST dotaz o veľkosti 500 KB zamestná jedno jadro procesora na celú minútu, na permanenté vyťaženie jedného Core i7 jadra stačí bandwidth 70 až 100 Kbit/s a bandwidth útoku 1 Gbps stačí na vyťaženie až 10 tisíc jadier. U ASP.NET stačí 1 Gbps na vyťaženie 30 tisíc jadier serverov, u Javy dokonca na 100 tisíc jadier, u Pythonu na 50 tisíc jadier, u Ruby na vyťaženie milióna jadier.

Aktualizáciu riešiacu problém znáhodnením hashovacej funkcie alebo zabraňujúcu zneužitiu chyby už vydali Microsoft pre ASP.NET, PHP aj Ruby.

Tento typ zraniteľnosti bol pôvodne objavený už v roku 2003 v Perle, Klink a Walde aktuálne zraniteľnosť identifikovali v ďalších jazykoch. Popis zraniteľnosť publikovali Klink a Walde na nruns.com (PDF).


Najnovšie články:



Diskusia:

Mozna uprava Od: branchman | Pridané: 30.12.2011 10:24 Ja by som v clanku upravil "Vo väčšine programovacích jazykov pre webové stránky" na "Vo vacsine serverov webovych stranok" - teda aspon pre pripad, ako bola zranitelnost prezentovana. Plati to aj pre vas pripad, ale tam by to programator musel vedome pouzivat. Webservery maju ten problem, ze POST si pocas spracovavania niekam ukladaju aj v pripade, ze ide o staticku stranku. Preto staci oprava napriklad Tomcatu (server pre Javu) namiesto opravy celej Javy - Tomcat pouziva Hashtable alebo Hashmap a teda staci overridnut implementaciu String.hashCode() alebo staci pouzit vlastnu hashovaciu tabulku a bude to vyriesene. Pochybujem, ze by niekto prepisoval Javu, aj ked aj to sa moze stat. Odpovedať Známka: 2.5 Hodnotiť:

Re: Mozna uprava Od: ebenci | Pridané: 30.12.2011 11:34 imho je ovela jednoduchsie to zmenit jeden krat priamo v jave, ako hladat a opravovat na vsetkych moznych softoch, kde to potencialne moze robit neplechu... Odpovedať Známka: 7.8 Hodnotiť:

z dokumentu Od: xvzf | Pridané: 30.12.2011 11:54 Z dokumentu: Oracle has decided there is nothing that needs to be fixed within Java itself, but will release an updated version of Glassfish in a future CPU (Oracle Security ticket S0104869). Odpovedať Hodnotiť:

z dokumentu Od: xvzf | Pridané: 30.12.2011 11:55 Z dokumentu: Oracle has decided there is nothing that needs to be fixed within Java itself, but will release an updated version of Glassfish in a future CPU (Oracle Security ticket S0104869). Tomcat has released updates (7.0.23, 6.0.35) for this issue which limit the number of request parameters using a configuration parameter. The default value of 10.000 should provide sufficient protection. Odpovedať Hodnotiť:

celkom nerozumiem Od: XMen | Pridané: 30.12.2011 12:38 Ak som spravne pochopil clanok, tak v nom chcu povedat, ze velke mnozstvo parametrov v http requeste sposobi velku vytazenost CPU, kedze pre kazdy parameter je nutny zapis do hash tabulky serveru. Ocakaval som, ze takyto problem bol na serveroch rieseny uz davno a som troska prekvapeny, ze tam niesu obmedzenia na pocet parametrov. Nechapem co mrkvosoft opravil na asp.net-e. Nemysleli ste skor IIS? Lebo toto nieje problem jazyka ale weboveho serveru. Odpovedať Známka: -2.0 Hodnotiť:

Re: celkom nerozumiem Od reg.: Redakcia DSL.sk | Pridané: 30.12.2011 12:57 Toto je v prvom rade problém jazyka, ako je detailne vysvetlené aj v článku. Pridanie aj stotisícov záznamov do hash tabuľky by bolo bezproblémové, ak by hash tabuľka fungovala podľa očakávaní a nebolo by možné zneužiť kolízie. Keď ale hash funkcia nie je dostatočne dobrá a je možné dosiahnuť kolíziu všetkých záznamov do jednej hash hodnoty, zvyšuje sa zložitosť vkladania na n^2 a práve to umožňuje efektívny DoS. Odpovedať Známka: 10.0 Hodnotiť:

Re: celkom nerozumiem Od: XMen | Pridané: 30.12.2011 14:39 ok suhlasil by som, ale ak tomu potom rozumiem spravne, tak ta zranitelnost spociva v tom, ze hashove tabulky pri zisteni kolizie kluca, vytvaraju pod rovnakym hashom (oboch klucov) zretazeny zoznam, ktory sa musi doplnit o novy prvok (s novym klucom) vzdy pri zisteni kolizie a prave toto zvysuje narocnost algoritmu hash tabulky. Rozumiem tomu spravne? Odpovedať Známka: 10.0 Hodnotiť:

Re: celkom nerozumiem Od: qqqqqqqqqqqqq | Pridané: 30.12.2011 14:53 Ano aj. Sposobov na vysporiadanie sa s koliziou hashovych hodnot je viacej, napr. vytvaranie zretazeneho zoznamu (co si ale vyzaduje dalsiu pamat dopredu neznamej velkosti). Tiez je mozne kolizie riesit ulozenim polozky na najblizsie volne miesto v hash tabulke, alebo najskor skusit pouzit druhu (prip. aj tretiu atd.) hashovaciu funkciu s nadejou, ze nove miesto bude volne. Konkretny sposob zavisi na implementacii, vsetky maju svoje vyhody aj nevyhody. Odpovedať Hodnotiť:

Re: celkom nerozumiem Od reg.: Redakcia DSL.sk | Pridané: 30.12.2011 17:39 Najpresnejším pomenovaním celého problému je, že útočník vie pri vložení N prvkov do hash table dosiahnuť zložitosť O(N^2) namiesto očakávaných O(N). To je spôsobené viacerými faktormi, tým ako sú hash tabuľky implementované (hash funkcia a zoznamy), že sú použité slabé hash funkcie a nájsť množstvo kolízií je veľmi ľahké a že sú použité vždy rovnaké hash funkcie a útočník tak vie a môže vygenerovať kolízne kľúče vždy použiteľné pre daný jazyk / jeho implementáciu. Vina nie je samostatne na žiadnom z týchto faktorov a zneužitiu sa dá zabrániť rozličnými spôsobmi. Asi najľahším, ktorý navrhujú aj autori, je znáhodnenie hash funkcie, ktorá bude mať v každej inštancii hash tabuľky inú inicializačnú náhodnú hodnotu. Odpovedať Známka: 10.0 Hodnotiť:

Re: celkom nerozumiem Od: XMen | Pridané: 30.12.2011 20:21 Ano s tym suhlasim, ze by sa dalo zabranit zneuzitiu pouzitim lepsej hash funkcie avsak podla mna uplne staci, ked sa zavedu limity pre mnozstvo parametrov v POST requeste (podla mna toto rovnako plati aj pre GET requesty). Ved naco by komu bolo viac nez 1000 parametrov? Podla mna by takyto limit stacil pre 99.99% webovych aplikacii a pre tie ostatne by si ho developery nastavovali podla vlastnych poziadaviek. Obmedzovanie velkosti POST requestu podla mna nieje vobec potrebne lebo limit by mohol stacit. Rovnako to spravili pre servery Tomcat, GlassFish a myslim, ze to ma aj apache. Dokonca sa tam da pre kazdy request obmedzit aj cas CPU. Odpovedať Známka: 10.0 Hodnotiť:

Re: celkom nerozumiem Od: xvzf | Pridané: 31.12.2011 14:22 jasne, ale pokial nevyriesia problem s hash tabulkami, tak sa moze prejavit aj inde ako pri parametroch requestov na web serveroch.... Odpovedať Hodnotiť:

Re: celkom nerozumiem Od: lolo21 | Pridané: 1.1.2012 21:15 to nerieši príčinu, iba následok Odpovedať Hodnotiť:

Pridať komentár