Re: Plan B for fixing 5.8.2 binary API

[Nicholas Clark <nick@ccl4.org>]

On Mon, Oct 13, 2003 at 12:12:32PM -0400, Chip Salzenberg wrote:
> According to Nicholas Clark:
> > 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" [...]
> > 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?
> 
> OK, that was eye-opening.  Let's be pessimistic and assume that we can't
> use my initial approach -- at least, not without significant theoretical
> doubts about its security.  How about an alternative approach:

Unfortunately I think that we can't.
They generated exploit files. 5.8.0's exploit file is at

http://www.cs.rice.edu/~scrosby/hash/attack/perl-5.8.0-attack.gz

it's 10,000 24 byte strings that in perl 5.8.0 all PERL_HASH to 0
(So on 5.8.1 with the HASH_SEED set to 0 they also all collide)

Having now read the paper properly (rather than just skimming the summaries)
their collisions aren't bucket collisions (ie different 32 bit values that
happen to land in the same bucket), but identical 32 bit hash values
(in this case all zero)


Hence the information we have to play with for all these 10000 strings is

1: PERL_HASH value 0
2: length 24
3: a constant

which doesn't give us a deterministic way of splitting the input into
different buckets.


Nicholas Clark