Denial of Service through hash table multi-collisions

[Aleksejs]

http://www.nruns.com...ory28122011.pdf

Hash tables are a commonly used data structure in most programming languages. Web

application servers or platforms commonly parse attacker-controlled POST form data into

hash tables automatically, so that they can be accessed by application developers.

If the language does not provide a randomized hash function or the application server does

not recognize attacks using multi-collisions, an attacker can degenerate the hash table by

sending lots of colliding keys. The algorithmic complexity of inserting n elements into the

table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single

HTTP request.

 

 

== PHP 5 ==

PHP 5 uses the DJBX33A (Dan Bernstein's times 33, addition) hash function and parses POST

form data into the $_POST hash table. Because of the structure of the hash function, it is

vulnerable to an equivalent substring attack.

The maximal POST request size is typically limited to 8 MB, which when filled with a set of

multi-collisions would consume about four hours of CPU time on an i7 core. Luckily, this time

can not be exhausted because it is limited by the max_input_time (default configuration: -1,

unlimited), Ubuntu and several BSDs: 60 seconds) configuration parameter. If the

max_input_time parameter is set to -1 (theoretically:

unlimited), it is bound by the max_execution_time configuration parameter (default value:

30).

On an i7 core, the 60 seconds take a string of multi-collisions of about 500k. 30 seconds of

CPU time can be generated using a string of about 300k. This means that an attacker needs

about 70-100kbit/s to keep one

i7 core constantly busy. An attacker with a Gigabit connection can keep about 10.000 i7

cores busy.

 

Video:

http://www.youtube.com/watch?v=_EEhviEO1Vo

 

Iespējamais risinājums:

http://cr.yp.to/critbit.html

[ieleja]

vēl noderīgs ir (būtu) PHP 5.4 rc4, kur pieviests 'max_input_vars', kas arī ļauj cīnīties pret 'hash collision attacks', tikai cik daudzi vēlas RC savā produkcijas kastē?

[Aleksejs]

Jā, PHPisti (kā video stāsta) izvēlējās nevis izvēlēties kolīzijnoturīgāku hash funkciju, bet gan nolimitēt parametru skaitu (kas arī protams nav slikti).

[Aleksejs]

Video kaut kur pazudis, bet rekur slaidi, kas tajā video bija:

http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf

[Aleksejs]

https://github.com/koto/blog-kotowicz-net-examples/tree/master/hashcollision

http://blogs.technet.com/b/srd/archive/2011/12/27/more-information-about-the-december-2011-asp-net-vulnerability.aspx

[yancho]

Video šeit

iepriekšējām bija minēts, ka sync problēmas un tiks ievietota jauna versija.

[marrtins]

Tas O(n^2) ir konkrētai hash f-ijai jebšu vairumam? Ja es pareizi atminos, laikā kad bija jānodod labdarb par šo tēmu, mana uz CRC32 bāzētā hash f-ija, kolīzijas taisīja O(log(n)) - t.i. binārais koks. Vismaz man tā šķiet, ka sanāk logN. Es kaut ko putroju, palaidu garām?

[Aleksejs]

Konkrētajām funkcijām. Crit-bit trees, piemēram arī ir daudz labāks worstcase.

[Mr.Key]

http://www.h-online.com/security/news/item/PHP-5-3-9-released-with-hash-DoS-fix-1407472.html

The PHP developers have announced the release of PHP 5.3.9 which includes the ability to limit the number of input parameters in HTTP requests. The fix addresses the denial of service attack issue which was presented at the 28th Chaos Communication Congress and has led to fixes being applied to many web servers, frameworks and languages.

Edited January 11, 2012 by Mr.Key

[Faks]

iskatas suhosin viegli nobeidz visus bugus,exploit ...

Edited July 29, 2012 by Faks