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

[md2perpe]

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]

@md2perpe 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.

[j00mi]

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

[Youloeka]

33:38 He said 'sex' D:

[adamziaja]

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

[DJ1TWITCH1]

47:50.. fucking hilarious

[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.

[Koniiiik]

@nzer19 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²).

[echtwahr]

@Koniiiik lets not engage in semantic hairspliting shall we?

[uenyioha]

@nzer19 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.

[someman7]

I'm not going to whine about how smug these guys are, nor how seemingly delusional they are about their English accents. Because there's an even more important point to get accross:

Speakers (of this video, but et al), the talk is intended for the audience. They are whom you're explaining the matter to. You're not simply refreshing your own memory. Thus, your presentation needs to be more accessible than reading, not less.

[nilskp]

Their Big-O notation is wrong.