Re: [Chicken-hackers] On Hash Collisions (28C3)

[Jörg F . Wittenberger]

On Dec 31 2011, John Cowan wrote:

> Thomas Bushnell, BSG scripsit:
>
> > Huh? The point is that well-chosen hash collisions can force the 
> > algorithm into its worst case behavior, and if that's linear, it's a 
> > problem. Choosing a linear algorithm to begin with is hardly a win!

Let me second that one.

The point is _not_ about replacing hash tables with something else
(especially not something of higher complexity cost; let alone
the need to change whatever program that would be) elsewhere
when compiled by chicken.

The point is hash table implementation in chicken.

If the default hash function is vulnerable I'd like at least to know
about it.  Once I know, I'll estimate the cost to fix it to save my
brain from remebering that I'm not supposed to use hash tables where
appropriate because they could degenerate into an issue.


> But it's worst-case as well as best-case linear.  From the abstract:
>
> # 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.
>
> Inserting n keys into an a-list can never take more than O(n) time.

At the cost of lookup time - not exactly a big win.

> Limiting the number of parameters seems like a good idea too.

That might be a point - but that should be application specific.
I'd really dislike, if there where an arbitrary limit to the amount
of keys a hash table can hold.