Re: Plan C (was Re: Plan B for fixing 5.8.2 binary API)

[Nicholas Clark <nick@ccl4.org>]

On Tue, Oct 21, 2003 at 10:52:54AM -0700, Stas Bekman wrote:
> Nicholas Clark wrote:
> >On Sat, Oct 18, 2003 at 12:41:26PM -0700, Stas Bekman wrote:
> >
> >
> >>Good. So the first time we pass the precomputed hash value it will 
> >>discard it. What happens when the that (now invalid) hash value is passed 
> >>second time? Will it still know to discard it?
> >
> >
> >Yes. A flag is added to the HV saying that an alternative hashing
> >algorithm is in use, and all supplied keys (internally) have a hash
> >value computed using this.
> 
> meaning that the passed hash value will be always ignored, once the 
> alternative hashing alg kicks in, until a new HV is created.

passed hash values will be ignored for that HV.
other HVs are unaffected, including new HVs
And existing HVs don't change behaviour until they are cleared of all keys.

> >Oops. Yes I meant to. "\0" x 1 to "\0" x 16 is good enough to trigger it.
> >Hopefully I will have time tomorrow night
> 
> Sure, take your time. No hurry on our side ;)

This isn't an ok 1/not ok 1 test, but it does demonstrate it kicking
in:

#!/usr/bin/perl -w
use strict;

my %h;
foreach (1..4) {
  $h{"\0"x$_}++;
}

my @k1 = map {length $_} keys %h;

# A rehash should be triggered

foreach (5) {
  $h{"\0"x$_}++;
}

my @k2 = grep {$_ <= @k1} map {length $_} keys %h;

print "@k1\n";
print "@k2\n";
__END__

$ ./perl ~/test/attack.pl
4 3 2 1
2 1 4 3
$ ./perl ~/test/attack.pl
4 3 2 1
4 3 2 1
$ ./perl ~/test/attack.pl
4 3 2 1
3 1 2 4


The 4 in 1..4 is the value of HV_MAX_LENGTH_BEFORE_SPLIT in hv.c
I hope that that code is viable for your testing


> >Given that the default hashing under plan C is the same as 5.8.0
> >(ie not random) "attacks" are any data that is a pathological case for
> >5.8.0, and are going to be "attacks" independent of the hash key.
> >The hash key is now only used for the internal rehashing - effectively
> >the response to an attack is to enable random hashing for that hash only.
> >So only the order of the hash attacked would differ based on key, but
> >with the key fixed for a test it ought to e the same (else there is a bug)
> 
> That also means that we are back to a deterministic order of 'keys/each 
> %hash', right?

Yes, for all hashes that aren't flagged as "under attack"
Hashes which have reacted to pathological data by rehashing internally
will be non-deterministic. (ie behaving like all hashes do in 5.8.1)
And any hash can go this way.
In some ways its more crazy than 5.8.1
I was wondering about randomising the bucket order too for all hashs, to
stop this kick in of rehashing from biting, but I figured it would be
complex.

(I was thinking of rotating the passed 32 bit hash value in all hashes
by the low 5 bits of the "new" hash seed. This won't protect against
complexity attackers who have correctly generated strings with the same
32 bit hash (they'll still trigger the rehashing), but it will make
all normal hashes have a different order every run, which will stop
people being gotcha'ed)


> I think the best approach would be to get RC1 out of the door asap, but 
> wait quite a bit with 5.8.2. That way distros will most likely pick 
> 5.8.2-RC1, but we need more time for this change to be tested. A massive 
> request for testing may help. Unfortunately most people ignore those 
> requests and start reporting bugs as soon as a new version is released.

Why would distros pick up a release candidate?

If most people want to report bugs only after the release of a stable
perl, they suffer, not me. It's their own silly fault and I have little
sympathy. (I can think of less polite phrases to express this sentiment)

And 5.8.3 is due to be along in a couple of months, so it's not the end
of the world.

Nicholas Clark