[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 http://ccil.org/~cowan
purpose, he saw only two aged hands withering
in flame. --"The Pyre of Denethor"