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

[Dario Teixeira <darioteixeira@yahoo.com>]

Hi,

> I've thought about this during the last debate on randomized hashing

> (which I think is now known to be ineffective, as implemented, to be
> secure), and I think a reasonable goal would be to use a balanced tree
> of buckets to a good worst-case, instead of fighting at the hash
> function level. As said at the time, this is what Core use, but I'm
> not sure what the bookkeeping overhead is against current hashtables.
> I hope it's possible to fight the constants to get something in the
> same performance ballpark.

Just to make sure we are all on the same page, allow me to summarise
the main points under discussion.  I think we all agree on the following:

 - Any hashtable implementation that uses a non-cryptographic hash function
   and relies on an association list of buckets is vulnerable to attacks
   that force the worst-case O(n) behaviour.  Though you can buy some time
   by tweaking the hash function, you are still stuck in an arms race with
   attackers.

 - Solution approach #1: switch to a cryptographic hash function.  This
   approach is simple and would solve the problem once and for all.
   Unfortunately, the performance would be terrible (how much though?).

 - Solution approach #2: keep the non-cryptographic hash function but use
   a balanced tree for the buckets instead of an association list.  This
   should mitigate the worst-case scenario -- it would go from O(n) to
   O(log n) -- and performance is most likely better than the first approach.

 - Since this problem presents itself on limited domains, it seems unfair
   to ask *all* applications to sacrifice performance to protect themselves
   from non-existent attackers.  Therefore, if the adopted solution does
   indeed have a serious performance penalty, then it should be opt-in.

Did I miss something important?  Anyway, it seems we are lacking actual
metrics to quantify the performance impact of the various approaches.
To complicate matters further, on some architectures but not on others
you may now or in the future have silicon that speeds up the calculation
of cryptographic hash functions...

Best regards,
Dario Teixeira