12:01
29/12/2011

Odpowiednio spreparowane żądanie POST wysłane do webaplikacji powoduje 100% użycie procesora, które może trwać wiele godzin i czasowo zawiesić pracę serwisu internetowego.

Atak na tablice hashujące

Podatność na atak znajduje się w algorytmach tablic hashujących wykorzystywanych przez wiele języków skryptowych i ponieważ jest to tzw. design flaw, błąd nie zależy od architektury webaplikacji. Odkrywcami są Alexander Klink i Julian Waelde. Przedstawili swoje badania na kongresie 28C3:

Na czym polega atak?

W skrócie: atak wykorzystuje to, że dane otrzymywane przez GET/POST są składowane w tablicach hashujących. Atakujący musi spowodować zmapowanie przesyłanych parametrów do tej samej wartości hasha. Tego typu mapowanie jest mało wydajne, więc zajmuje dużo czasu i powoduje obniżenie wydajności.

Atak na tablice hashujące

Atak na tablice hashujące

Dla przykładu, zaprezentowano wyliczenia dla Core i7 i PHP:

    8 MB POST data – 288 min. czasu pracy CPU
    500k POST data – 1 min. czasu pracy CPU
    300k POST data – 30 sek. CPU

Należy jednak wziąć pod uwagę, że konfiguracja PHP może limitować czas przetwarzania pojedynczego żądania (zazwyczaj 1 min). Dodatkowo, sam serwer może mieć ustawione limity na czas pracy procesora.

Oto wersje podatne na atak:

    Java, wszystkie wersje
    JRuby <= 1.6.5 PHP <= 5.3.8, <= 5.4.0RC3 Python, wszystkie wersje Rubinius, wszystkie wersje Ruby <= 1.8.7-p356 Apache Geronimo, wszystkie wersje Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 Oracle Glassfish <= 3.1.1 Jetty, wszystkie wersje Plone, wszystkie wersje Rack, wszystkie wersje V8 JavaScript Engine, wszystkie wersje

Jak się ochronić przed atakiem?

Rozwiązaniem problemu jest użycie “randomized hash functions” — ale ich wdrożenie wymaga zmian w kodzie. Istnieją też obejścia.

Dla PHP, ustawienie wartości max_input_vars ograniczającej liczbę parametrów w jednym żądaniu (PHP 5.4 0RC4) oraz max_input_time. Dla Tomcata podobnie. Dla Microsoft ASP.NET — obniżenie długości żądania HTTP:

<configuration>
<system.web>
<httpRuntime maxRequestLength="200”/>
</system.web>
</configuration>

Na marginesie, powyższa podatność nie jest niczym nowym. Już w 2003 opisano podobny atak, z tym, że na Perla. Przypomnijmy także, że całkiem niedawno opublikowano inny atak DoS na webaplikacje w PHP oraz Javie. Dodatkowo, warto zdawać sobie sprawę, że powyższe problemy mogą wystąpić nie tylko w webaplikacjach, ale w każdym miejscu, gdzie znajdują się struktury danych oparte o tablice hashujące.

P.S. Jeśli chcesz się dowiedzieć czegoś więcej na temat atakowania i ochrony webaplikacji, to zapraszamy na nasze szkolenia — najbliższy termin 23-24 stycznia 2012 ma jeszcze kilka wolnych miejsc.

Przeczytaj także:

34 komentarzy

Dodaj komentarz
  1. > czas przetważania
    Czy chodziło Ci o: przetwarzania :)

  2. Atak działa – przykładowe demo dla PHP – http://koto.github.com/blog-kotowicz-net-examples/hashcollision/kill.html – nie udało mi się powtórzyć requestu 500 KB, z moich doświadczeń minutę zajmują dopiero payloady od ok. 1.5 MB

    Problem w tym, że najprawdopodobniej patch na PHP nie pomoże (jeśli ktoś ma już to wkompilowane, proszę o kontakt, potestujemy zmodyfikowany payload).

    • I ile wykonanie tego na PHP zajmuje? Bo w pythonie killer.txt parsuje w jakies 1.5sec na moim macbooku pro (i5 dual core).

    • Patch dla PHP ogranicza maksymalna liczbe zmiennych POST do 1000. Wedle panow Klinke i Waelde, choc jest to jedynie obejscie problemu to powinno byc w tym przypadku wystarczajace. I nawet, gdyby zamiast 1k ograniczenie bylo do 10k tak jak zostalo to zrobione w Apache Tomcat to tez byloby ok – takie pytanie padlo na koniec sesji ok. ~55:10. Oczywiscie ma sie to tylko do przypadku, gdzie jedyna wykorzystywana tablica hashujaca sa dane POST.

    • @Sayane

      u mnie (MBP i5, PHP 5.3) killer.txt to jakaś minuta. Chodzi o to, że w killer.txt są kolizje hashy dla algorytmu używanego w PHP. Dla Pythona pewnie trzeba zmodyfikować payload, ale to drobna zmiana.

  3. A jak ochronic przed atakiem Pythona?

    • Trzymaj go w bezpiecznym miejscu, i ociągaj drapieżniki od akwarium, a na pewno nic mu się nie stanie.

  4. Jest jakaś informacja do tego np a securityfocus? :)

  5. W przypadku javy wyglada to groznie, a wychodzac poza aplikacje webowe to taki atak na jave moznaby przeprowadzic wykorzystujac spreparowany plik properties co tez jest pakowane w hashtable o ile sie nie myle.

    • Często do hash tables pakowane są dane z jsona, więc nie tylko post/get może być wektorem ataku.

  6. config poprawiony, thanks niebezpiecznik :P

  7. Piotrze, ale czy oby na pewno ten atak mozna nazwac 0day? Deweloperzy poszczegolnych jezykow/aplikacji zostali powiadomieni odpowiednio wczesniej. Dla niektorych rozwiazan sa juz gotowe mniej lub bardziej dzialajace patche, dla innych powinny sie pojawic niedlugo.

  8. Hashtable którego podstawą jest tablica drzew stringów, zamiast listy? zamiast O(n^2) będziemy mieli około O(log(n)).

    • Hashtable ma złożoność O(n) przy rozwiązywaniu kolizji metodą łańcuchową. Skąd Ci się wzięła kwadratowa?

    • Ohja… copy pasta z prezentacji & za mało myślenia:
      Dla n kolizji n^2, a dla n kolizji na drzewach: nlogn…

  9. wielki hax znany kazdemu pierwszorocznemu studentowi, srsly?

    • niby z jakiej uczelni?

    • Malo prawdopodobne, skoro wiekszosc absolwentow to mrowczy programisci, albo administratorzy.

      Inna rzecz, ze nie sprecyzowales o jaka uczelnie chodzi. Humanistyczna? nieszczegolnie. To moze inzynieria srodowiskowa? naaah.

    • Mnie na pierwszym roku nie uczyli jak wykorzystać podstawową własność tablic hashujących do ataku na systemy…

      A sam atak super – pokazuje on, że nie tylko osoby czytające kod maszynowy do poduszki mogą coś zdziałać w świecie bezpieczeństwa. Kreatywnym podejściem i łączeniem prostych, ogólnie znanych faktów można często osiągnąć zaskakująco ciekawe wyniki.

    • Panowie bez obrazy, ale w podstawowych zrodlach informacji pierwszorocznego studenta – cormen , wazniak, wikipedia mozna po krotszej obserwacji literek zauwazyc informacje o kolizjach i metodach ich rozwiazywania, co sprawia ze news jest lekko rzecz biorac trywialny.

    • Tomasz, bez obrazy, ale przeczytałeś wogóle o co chodzi w tym ataku? Newsem nie jest to, że w tablicach hashujących są kolizje – wszyscy je akceptują, łącznie z autorami tego ataku. Newsem jest to jak można je wykorzystać do ataku na systemy, ze względu na (w skrócie) brak randomizacji zarodka w wykorzystywanych przez nie funkcjach hashujących.

      Idąc Twoim tokiem rozumowania można stwierdzić że wogóle całe bezpieczeństwo jest tematem na trywialne newsy – przecież znakomita większość dziur ma swoją genezę w prostych błędach w jednej z warstw (jak wykroczenie poza tablicę, brak walidacji treści od usera, etc), z ogólnie znanymi metodami ich rozwiązywania.

  10. W przypadku PHP Suhosin załatwia sprawę elegancko, jest kilka parametrów którymi można dopieścić swoją konfigurację (suhosin.post.*), ale nawet na defaultach daje sobie radę.

  11. Microsoft już wydał poprawkę (i przy okazji 3 inne łaty)

    • Na dziurę średnikową też?

  12. Stary dobry perl nie jest na to podatny:)
    http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/

    • Od 7 lat…

    • Z podobnego względu zmienili trochę wcześniej quicksort na mergesort w perlu. Sam zresztą się natknąłem na ten problem sortując długą listę podobnych plików (quicksort robił się O(n^2)).

    • To dziwne, że inne języki nie pozbyły się tego problemu wcześniej.

  13. http://az.linux.pl/2011/12/bezpieczenstwo-php.html w moim arcie, który nie przedstawia żadnych rewolucji jest mowa o zapobieganiu tego typu atakowi, a powstał przed filmikiem na youtube, bo nic nowego nie odkryli, to znany atak imo…

  14. nic nowego. ;] od dawna to bylo znane. PHP 5.4.0 jeszcze nie wydane a juz jest memory_limit bypass.. wiecej na devilteam.

  15. Mod Security do Apache tak samo załatwia sprawę, zwracając evil userowi “413 Request Entity Too Large”. Na pewno jest to pewniejszy sposób niż redefinicja max_input_time, który tak na prawdę niczego nie załatwia.

  16. […] koniec stycznia wydano PHP w wersji 5.3.9, aby poprawić ten błąd bezpieczeństwa. Jak się jednak okazuje, podczas łatania jednej dziury, wprowadzono drugą, i to o wiele gorszą. […]

  17. “Odkrywcami są Alexander Klink i Julian Waelde” Serio? A skądże! Technika ataku na hashtable była znana już w 2003 roku albo pewnie i wcześniej: http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/

Twój komentarz

Zamieszczając komentarz akceptujesz regulamin dodawania komentarzy. Przez moderację nie przejdą: wycieczki osobiste, komentarze nie na temat, wulgaryzmy.