Re: Hash Table Collisions (n.runs-SA-2011.004)

[William Ahern <william@...>]

On Fri, Dec 30, 2011 at 06:54:47PM -0700, HyperHacker wrote:
<snip>
> On that note, I'm curious if creating hash collisions is feasible in a
> real server. Most servers will reject requests that contain too many
> headers, or that are too long. How many collisions can an attacker
> really create if the number and length of headers is very limited?

Approaching a security issue with, "I'm too unimaginative to come up with a
real-world attack, therefore it's probably impractical", is not really the
best analytical methodology.

That said, SA-2011.004 is part of a class called Computational Complexity
Attacks. They've been described since at least the Perl collision attack
paper many, many years ago. I've been using RB trees exclusively ever since.
(They're easier to work in C anyhow because they don't require any
additional dynamic memory management and the concomitant failure mode.) But
SA-2011.004 is the first real-world attack I've heard of in the intervening
years. Of course, the past is only a reliable indicator of the future until
it isn't. This report might interest the current generation of asshats more
than the last.

Using an RB tree as an adjunct to Lua's hashing would require at least one
more pointer. Two more if you use a non-recursive implementation like this
(shameless plug):

	http://25thandclement.com/~william/projects/llrb.h.html

I've considered hacking Lua to use an LLRB tree instead of hashing in the
past, but have yet to find the time. If you replaced the hash with an RB
tree entirely, you can get away with *less* space. If the hash is half full,
you're maintaining three pointers per node--two per node in the vector, and
one for the chaining. With a recursive LLRB tree you only need two pointers
per node.

I dunno how CPU cache hits would be be effected. Probably detrimentally; but
the real question is by how much. Maybe you could even have both
implementations, and choose at run-time which kind of table you want--best
worst-case or best best-case.

What would also be interesting is trying crit-bit trees.

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