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

On 15/02/2010 20:55, Tom Jackson wrote:
> More interesting to me is why the similar function it tclLiteral.c was> not changed:>> line914 	result += (result<<3) + bytes[i];

Oh dear, that was an oversight. It will be fixed very soon. :-)

> So basically all the pro-change arguments are based upon un-shown> work. My tests show no difference when the collide proc is used as> given, but if you change the collide proc, the current hash seems to> work very well.

What's the point of that? With the collision demonstrator (which is
published on the Wiki) you have a simple way of generating problematic
keys. By "problematic" I mean "large numbers of keys with the same
hashcode". To argue that changing the collide procedure gets rid of the
problem is missing the whole damn point! We're not testing the collision
generator. We're testing the hash function.

What I would be interested in is a demonstration of an equivalent
collision generator for FNV without requiring rapid growth of key sizes
(as those would force the attacker to do more work).

> One interesting change is that the run time goes way down. Maybe there> is something special about the original proc. This special feature> does not reduce the security of the hash, for that you need a generic> method to find a collision with a particular string.

You're mistaken. This is not a strict security issue because we never
assume that two different keys have a different hashcode. What it is is
a potentially-crippling performance attack, since it lets anyone who can
control what the keys are to make as many keys with the same hashcode as
they want (hence they always end up in the same hash bucket even when we
resize, leading to O(n**2) performance instead of O(1)). The collide
procedure demonstrates the core of how to exploit this problem; all
that's then needed is code that puts the keys in an array or dictionary
(which is the natural way to write a handler for an http request in
tclhttpd or Wub) and you've got a real problem. Yes, only a
Denial-of-Service attack, but those matter.

> My recommendation: demonstrate a real vulnerability to the original> hash before introducing a fix. No vulnerability has been demonstrated.

Do you accept the argument above?

> Regardless of any problems with the current hash, why does anyone care> if some idiot chooses an array to store HTTP headers? Should the Tcl> language protect everyone because they don't realize they need to> understand that user data needs to be validated, or at least not> trusted?

WTF are you talking about? I take it you seem to think that validating
is done before the initial parse of the values into a data structure,
rather than afterwards? Interesting concept. I'm not aware of any
non-trivial web server that does that.

> Of course I'm on record as being opposed to using an array to handle> HTTP headers, only the hard headed would continue to use arrays to> represent  HTTP headers, or create any local variables automatically.> Instead, what you do is to create a representation of the user data> and then query it using known keys.

Oh, we're supposed to use leprechaun juice to hold the representation?

> But of course the problem is that the core developers want everything:> unconscious security.

All we're looking for is a way to generate hashcodes for arbitrary
"short" values (short is probably "no more than 80 characters" really)
that are unlikely to be the same. We can't (and never could) guarantee
that there will be no clashes, but we do want it to be difficult to
generate arbitrarily many clashes because that enables DoS attacks.

> Many years ago I learned a simple lesson: everyone that came before me> knew what they were doing. If I intend to change it, I must first> understand the choices they made. I don't see any understanding here.

I certainly see no understanding in your message. You're mixing up
different hashing schemes and different types of hashes and different
reasons for hashing and, well, the result is you're way off base.

Donal.

begin:vcard
fn:Donal K. Fellows
n:Fellows;Donal
org:The University of Manchester;Research Computing Services
adr:;;Oxford Road;Manchester;;M13 9PL;United Kingdom
email;internet:dona...@manchester.ac.uk
version:2.1
end:vcard

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