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

[Peter Bex]

On Sun, Jan 01, 2012 at 01:08:39PM +0100, Jörg F. Wittenberger wrote:
> On Dec 31 2011, John Cowan wrote:
> >>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.

Agreed.  Changing datastructures is not an option.

> If the default hash function is vulnerable I'd like at least to know
> about it.

That's confirmed.  Attached is a preliminary patch to fix this issue.
If you'd like, you could help out testing this.  The patch ensures
no two hash tables use the same offset, so even if the hash value of
a given table were to leak out (which the user still should take every
precaution to avoid!), it won't compromise the randomization of other
hash tables.

It has been pointed out that symbol interning also uses a hash table
which is not based on SRFI-69.  This needs to be fixed as well.
This patch does not address that.

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

Indeed.  If other languages have fixed it transparently, so can we.

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth

hash.patch
Description: Text document