28c3: Effective Denial of Service attacks against web application platforms

Download hiqh quality version: http://bit.ly/rKwW58
Description: http://events.ccc.de/congress/2011/Fa...

Alexander 'alech' Klink, Julian | zeri: Effective Denial of Service attacks against web application platforms
We are the 99% (CPU usage)

This talk will show how a common flaw in the implementation of most of the popular web
programming languages and platforms (including PHP, ASP.NET, Java, etc.) can
be (ab)used to force web application servers to use 99% of CPU for several
minutes to hours for a single HTTP request.

This attack is mostly independent of the underlying web application and just
relies on a common fact of how web application servers typically work.

• Category

  Science & Technology

[j00mi]

You are right. Thats a well known alternative. But i think you must use a balanced tree to gain optimal performance. It's more complicated to do insertion and deletion. But the lookup, like you said, is O(n*log(n)). I would prefer a b-tree if I have a very large immutable set of data and the only thing i do are lookups.

[Per Persson]

A hash table is normally implemented as an array of lists. Then in worst case, insertion takes O(n^2). What if you instead used a balanced binary search tree? Wouldn't that be better and in worst case take O(n log n)? And as long as the elements in the hash table are well spread out, it shouldn't be slower than a list.

[j00mi]

if bucket lookup and str cmp is part of the algorithm then O(n^2) is correct

[uenyioha]

i think they're trying to point out the the string comparisons in addition to the linked list traversals. but agree that O(n^2) is the wrong measure if that's the case.

[echtwahr]

lets not engage in semantic hairspliting shall we?

[adamziaja]

omg, nothing new, i done article about php security in 17 dec on my blog, and there is setting what block this attack...

[Koniiiik]

Actually, I'm pretty sure they mentioned the n² run time is for n insertions. And yes, this is not only O(n²) but Θ(n²).

[Spo0Bo]

If you are using a language that does not randomize the hashing you could also place a random prefix in front of each hash key through using a subclass of hash. No? Didn't see the entire talk because honestly ... get to the point guys :|

[nzer19]

Erm worse case for collisions in a hashtable..the hashtable acts as a linked list or array (depending on implementation). Certainly would not result in O(n^2) operations.