Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

Am 17.02.10 19:41, schrieb Tom Jackson:
> The keyspace is only 32 bits, this is trivial by any measure. I guess> Gustav has already found several sets of keys. Of course, the real> problem is that you only need the low order bits of the hash to match,> so the keyspace for the buckets is much smaller than 32 bits.>    
Exactly.  It is sufficient to attack a much smaller keyspace to achieve
the reported slowdowns. To make a lookup in a table with 55000
entries a linear search, it is sufficient to find hash-values with the
identical 14 low bits (in the current mapping from hash-key to bucket).
One can construct such key-sets for every hash function in a c
program in less than 20 seconds (finds e.g.  70000 keys with the
same hash suffix as "hello" based on fnv).

As pointed out earlier, this attack is not possible when using a randomized
seed and hash functions like murmur or lookp3, which mix the seed properly
into the hash value, since on every start of tcl, it will return 
sufficiently
different hash values for the same keys.

Since tcl support custom hash tables, every c-level application can
provide for their own hash tables a different hash function with and 
without
seeds.

In case, there is still someone listening:
Below are some results from loading dict/words into
an array (the script donal posted) with 4 hash algorithms.
It shows, that Tcl's classic hash function does very well,
murmur is the seconds and the perl hash function is the
worst of these.

-gustaf neumann

   CLASSIC
   218022.7906 microseconds per iteration

   MURMUR
   219907.73859999998 microseconds per iteration

   LOOKUP3
   225928.0354 microseconds per iteration

   PERL_HASH
   249029.0566 microseconds per iteration


------------------------------------------------------------------------------
Download Intel® Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs 
proactively, and fine-tune applications for parallel performance. 
See why Intel Parallel Studio got high marks during beta.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
Tcl-Core mailing list
Tcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/tcl-core