Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Xavier Leroy <Xavier.Leroy@inria.fr>]

On 03/10/2012 08:31 AM, Richard W.M. Jones wrote:

>> Rather than changing every app that uses Hashtbl, I'd prefer to fix
>> this upstream by choosing a random seed for hash tables unless the
>> caller explicitly sets one or sets an environment variable to disable
>> this.
>>
>> In Perl, the seed is a random number chosen when the Perl interpreter
>> starts up.  This is low overhead, but still leaves a (much more
>> theoretical) attack where someone can determine the seed from a
>> long-running process using some other method and still attack the hash
>> table.
>>
>> In Python there is an environment variable you can set to disable
>> randomized hash tables.  Further Python discussion here:
>> http://bugs.python.org/issue13703
>> http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465
> 
> No comment at all?  This is an exploitable CVE ...

As you and Gerd said, the new Hashtbl implementation in the upcoming
major release has everything needed to randomize hash tables by
seeding.  The question at this point is whether randomization should
be the default or not: some of our big users who don't do Web stuff
value reproducibility highly...  We (OCaml core developers) will take
a decision soon.

Musing: there is something strange about saying that a data structure
has a DOS vulnerability.  It's a bit like saying that a steak knife
has homicidal intent.  Web-facing applications that use the wrong data
structure have vulnerabilities; the data structure does not.  And,
even randomized, a hashtable still has O(n) worst-case behavior...

Gerd Stolpmann adds:

> Currently, the only way for library developers to fix their product for
> 3.12 is to restrict the size of the hashtables coming from untrusted
> sources.

A much better fix is to replace your hash tables with references to
AVL maps.  Guaranteed O(log n) is the way to go for Web app developers
to sleep soundly at night.

Resignedly awaiting a CVE about association lists,

- Xavier Leroy