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

Tom Jackson skrev:
> Hey,> > As far as I can tell this entire operation and the logic used to> justify it is totally messed up.> > Unless I'm missing some additional code, one of the basic> justifications for this change is completely wrong.> > That justification is the wiki entry which shows FNV somehow creates a> hash key distribution that outsmarts the test program "collide". From> my reading of the collide program it was designed to find collisions.> Unfortunately the code seems to find X candidates which have the same> hash value and then create an array.> > Guess what! This trick works for any hash function. As far as  I can> tell it works for the new FNV hash and one which I tried the djb hash.

Yes, but it is extremely simple for the classic Tcl hash, because:

1. It has the property that if $x and $y are two equal length strings 
which hash to the same 32-bit value, then $a$x$b and $a$y$b will be a 
pair of strings which hash to the same value too, for any strings $a 
and $b.

2. There are very many pairs of strings as short as 2 characters which 
hash to the same 32-bit value.

FNV escapes 1 by using ^ to add in the characters, and 2 by using a 
multiplier larger than 255. It's probably still possible to find 
strings $x and $y such that FNV($x) = FNV($y), but I suspect they'd 
need to be of length at least 5, and chances are pretty good that 
FNV($a$x) != FNV($a$y) (naively I'd say 255/256, but there could be 
strings $x and $y which are less sensitive to the prefix $a).

With the FNV hash function, an HTTP header parser can to some extent 
randomise the results of an attacker by picking a $salt prefix and 
using $salt$header as hash entry for data that has to do with the the 
$header prefix. With the classic hash function, that has no effect 
whatsoever; an attack works just as well no matter what $salt is chosen.

Lars Hellström



------------------------------------------------------------------------------
SOLARIS 10 is the OS for Data Centers - provides features such as DTrace,
Predictive Self Healing and Award Winning ZFS. Get Solaris 10 NOW
http://p.sf.net/sfu/solaris-dev2dev
_______________________________________________
Tcl-Core mailing list
Tcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/tcl-core