Re: [Caml-list] Hardening [Perl's] hash function further

[Goswin von Brederlow <goswin-v-b@web.de>]

On Tue, Nov 19, 2013 at 01:08:40AM +0100, Gerd Stolpmann wrote:
> Am Montag, den 18.11.2013, 20:44 +0000 schrieb Richard W.M. Jones:
> > The Perl community have found further attacks against their
> > (already considered hardened) hash function.  This article
> > explains the problems quite well:
> > 
> > http://blog.booking.com/hardening-perls-hash-function.html
> 
> Interesting read. I'm wondering which conclusions one should draw from
> it. This article is more or less discussing cryptoattacks on an insecure
> hash function, and the new versions of the functions are only "better"
> but in no way safe (which you only get with crypto hashes or
> dictionaries that don't allow collisions). This sounds for me like a
> race between attackers and hash implementors.
> 
> Gerd

I notice that the problem isn't exploting hash collisions but
collisions in the bucket being used in the hashtable. So no matter how
good the hash is the table still breaks down.

1) the hashtable isn't randomized by default
   - the bucket being used is predictable so you can make long chains

Why not just always use the randomized hash? Why only use it when you
think you have detected an abuse? That is just silly.

2) on long chains the hashtable size is doubled
   - each bucket is split in two and assuming a good hash each will
     get half the entries

You don't double your size. The old and new size should not have a
common divisor, esspecially not 2. Best is to use primes but not
fastest. Using 2^n-1 is tempting since (x mod 2^n-1) is fast to
compute without needing a long division.

If the old and new size have no common divisor then the entries of the
overly long chain are distributed over *all* the buckets. So instead
of getting 2 buckets with n/2 entries you get buckets with n/size
entries.

3) hashtables aren't re-randomized on resize

When you resize a hashtable you have to sort every key into a new
bucket. So why not change the randomize of the hash function at that
time. If the randomizer is applied after the hash is computed this can
be done quickly without having to rehash every key. Takes extra memory
to store the non randomized hash value of each key though. If you
don't want to spend that memory you can rehash every key, which also
allows using a randomized hash function instead of randomizing the
result of the hash.

4) hashtable sizes are predictable

You can also randomize the size. Nobody says you have to (nearly)
double the size in a predictable way. You can have a long list of good
sizes (e.g. prime numbers) and randomly pick one that is between 1.8
and 2.2 times (or whatever grows factor you want) the size as the old
size. The randomness will make the size of the table unpredictable
making it that much harder to construct a key collision.

Note: if a table is resized due to an overlong chain without being
reasonable full I would just resize it a tiny bit instead of about
double. That gets rid of the collisions without doubling the memory
used.

MfG
	Goswin

PS: is anyone working on fixing the stdlib hashtable?