[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: John Cowan
Subject: Re: [Chicken-hackers] On Hash Collisions (28C3)
Date: Fri, 30 Dec 2011 22:50:20 -0500
User-agent: Mutt/1.5.18 (2008-05-17)

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!

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.

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

And it was said that ever after, if any                 John Cowan
man looked in that Stone, unless he had a               address@hidden
great strength of will to turn it to other    
purpose, he saw only two aged hands withering
in flame.   --"The Pyre of Denethor"

reply via email to

[Prev in Thread] Current Thread [Next in Thread]