Re: Hash seed breaks 5.8.1 binary API; fix suggested

[Nicholas Clark <nick@ccl4.org>]

On Thu, Oct 09, 2003 at 10:41:34PM -0400, Chip Salzenberg wrote:

>   3. Add (or xor or whatever) PL_new_hash_seed with the user-provided
>      hash value *inside* the functions that use hashes, *not* outside
>      them.

I think that it has to be "whatever"

It can't be xor. The attack relies on pre-computing a set of values
which are a pathological case for the hashing algorithm, values which
all end up in one bucket. IIRC the mapping to buckets is done using the low
N bits of the 32 bit hash value (where N starts at 3 and increases as the
hash grows).

Given a set of N bit hash values which map to the same bucket, xoring them
all with a constant will still put them in the same bucket. All this would
do is change the order for keys on non-pathological hashes, without actually
splitting the set. Likewise add would just rotate the buckets round, as
effectively it would be modulo arithmetic in base N

I think that we have to do "whatever" where whatever is hashing the input
32 bit PERL_HASH value inside the hv.c functions, seeded by the per
run random value. I'm just not sure what the "whatever" is. We could use
5 bits of it and rotate the 32 bit hash value round. This makes the attack
harder, because then the attacker has to find a set of strings that hash
to the same 32 bit value, rather than just the same bucket. Then again,
if the attacker can do that, anything we do inside hv.c is fruitless, as
we're trying to reliably distinguish between identical values :-(

At which point we may as well calculate a new hash value inside hv.c each
time and kill performance in the general case.

If we don't do that, I believe that information we have to play with is

1: 32 bit PERL_HASH value
2: key length
3: per run 32 bit random seed

How can we generate a new value out of that at little cost?

Nicholas Clark