From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pBUGmUGS025620 for ; Fri, 30 Dec 2011 17:48:30 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmoKAHHq/U4macht/2dsb2JhbABDnCSIHAGICAiBBYFyAQEBAgEBEgIEKAEBIwkLAQQLCwsCARchIhIBBQEKEgYTCQkQh1gImRQKijOEHQGOEgeDfYgSgl6FXYxLhW+IDj2EGA X-IronPort-AV: E=Sophos;i="4.71,433,1320620400"; d="scan'208";a="137300340" Received: from unknown (HELO mxgoog1.janestreet.com) ([38.105.200.109]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 30 Dec 2011 17:48:11 +0100 Received: from mail-tul01m020-f170.google.com ([209.85.214.170]) by mxgoog1.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1Rgfco-0000v5-6J for caml-list@inria.fr; Fri, 30 Dec 2011 11:48:10 -0500 Received: by obcwo10 with SMTP id wo10so11058222obc.29 for ; Fri, 30 Dec 2011 08:48:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:x-originating-ip:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=xAnGRB+iluHs7tVxBv0+erCfzzHtmDqdyxOCg8B1CIE=; b=dZr2ADWMygPlfBHCGJylAd+K9Bo583RN2ftQY3x/k7jlJYgXnyQPcdeigt/R6URRWQ ux354sIZF69SRGTBoSN3wKPH55qkKmtndOWxeMnDYtkULX2a3FygHpROr4HjgNSQJMp1 aOJHvg5w687jnXRo3RbF690hBKkl3yi+NPSj8= MIME-Version: 1.0 Received: by 10.182.13.105 with SMTP id g9mr34611000obc.63.1325263687620; Fri, 30 Dec 2011 08:48:07 -0800 (PST) Received: by 10.182.11.167 with HTTP; Fri, 30 Dec 2011 08:48:07 -0800 (PST) X-Originating-IP: [38.105.200.252] In-Reply-To: <1325263446.5036.104.camel@samsung> References: <1325263446.5036.104.camel@samsung> Date: Fri, 30 Dec 2011 11:48:07 -0500 Message-ID: From: Yaron Minsky To: Gerd Stolpmann Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=f46d044285f255992f04b551ffba Subject: Re: [Caml-list] Hashtbl and security --f46d044285f255992f04b551ffba Content-Type: text/plain; charset=ISO-8859-1 For just this reason, the hashtables in Core have been reimplemented to use an AVL tree in the buckets. That way, even when you have pathological collisions, you degrade gracefully to O(log n) per operation, instead of O(n), where n is the number of keys in the hashtable. y On Fri, Dec 30, 2011 at 11:44 AM, Gerd Stolpmann wrote: > Hi, > > there was recently a security alert for web services that use hash > tables to store web form parameters sent via POST (so that millions of > such parameters can be sent in a single request). It is possible to keep > the web service busy for hours with such a DoS (denial of service) > attack. The type of attack boils down to a problem in most hash table > implementations, namely that the hash functions are invertible, and it > is possible for a malicious user to construct lots of keys that all map > to the same bucket of the hash table, creating a mass collision. > > The text of the alert: > http://www.nruns.com/_downloads/advisory28122011.pdf > > I'd like to discuss this issue, because it is not restricted to the > processing of web requests, but may also occur for all other data coming > from untrusted sources. The web is only the most exposed area where this > issue exists. > > So how is Ocaml affected? The hash functions used in recent Ocaml > releases are also insecure in the above mentioned sense (currently > MurmurHash3, and even a simpler hash function in previous releases). A > quick survey of the Internet revealed at least one site that tries to > break it. Probably a good cryptographer could do it in minutes. > > A pure Hashtbl.add of the constructed keys does not yet lead to the > performance degradation, but a Hashtbl.replace, and of course > Hashtbl.find after the table is built up will. So it depends very much > of the details of the programs whether they are affected or not. > > I've just checked that Ocamlnet uses only Hashtbl.add to collect POST > parameters, so it is not directly vulnerable. But if the crafted request > is actually served by a handler, the handler would get a degraded table, > and could show in turn bad performance (again leading to DoS). > > What are possible fixes? > > 1) Avoid hash tables in contexts where security is relevant. The > alternative is Set (actually a balanced binary tree), which does not > show this problem. > > 2) Use cryptographically secure hash functions. > > 3) Use "randomized" hash tables. The trick here is that there is not a > single hash function h anymore, but a family h(1)...h(n). When the hash > table is created, one of the functions is picked randomly. This makes it > impossible to craft an attack request, because you cannot predict the > function. > > I don't think 1) is viable - hash tables are too wide spread, and are > loved by programmers because of their good performance. 2) would be good > in extremely critical contexts - although it is then again questionable, > because it is likely to have worse performance than 1). > > So, the question is how to do 3). I see two problems here: > > a) how to define the family of hash functions. Is it e.g. sufficient to > introduce an initialization vector for the Murmurhash algorithm, and > fill it randomly? How to get a random number that is good enough? > > b) the Hashtbl in the standard library does not allow it to set the hash > function dynamically. Maybe one can get this effect by using first-class > modules (haven't checked). > > Anyway, I think these problems are difficult enough to deserve some > discussion here. At least I cannot solve them immediately, and this > problem may exist for lots of Ocaml applications. > > Gerd > -- > ------------------------------------------------------------ > Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de > Creator of GODI and camlcity.org. > Contact details: http://www.camlcity.org/contact.html > Company homepage: http://www.gerd-stolpmann.de > ------------------------------------------------------------ > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > > --f46d044285f255992f04b551ffba Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable For just this reason, the hashtables in Core have been reimplemented to use= an AVL tree in the buckets. =A0That way, even when you have pathological c= ollisions, you degrade gracefully to O(log n) per operation, instead of O(n= ), where n is the number of keys in the hashtable.

y

On Fri, Dec 30, 2011 at = 11:44 AM, Gerd Stolpmann <info@gerd-stolpmann.de> wrote:
Hi,

there was recently a security alert for web services that use hash
tables to store web form parameters sent via POST (so that millions of
such parameters can be sent in a single request). It is possible to keep
the web service busy for hours with such a DoS (denial of service)
attack. The type of attack boils down to a problem in most hash table
implementations, namely that the hash functions are invertible, and it
is possible for a malicious user to construct lots of keys that all map
to the same bucket of the hash table, creating a mass collision.

The text of the alert:
http://www.nruns.com/_downloads/advisory28122011.pdf

I'd like to discuss this issue, because it is not restricted to the
processing of web requests, but may also occur for all other data coming
from untrusted sources. The web is only the most exposed area where this
issue exists.

So how is Ocaml affected? The hash functions used in recent Ocaml
releases are also insecure in the above mentioned sense (currently
MurmurHash3, and even a simpler hash function in previous releases). A
quick survey of the Internet revealed at least one site that tries to
break it. Probably a good cryptographer could do it in minutes.

A pure Hashtbl.add of the constructed keys does not yet lead to the
performance degradation, but a Hashtbl.replace, and of course
Hashtbl.find after the table is built up will. So it depends very much
of the details of the programs whether they are affected or not.

I've just checked that Ocamlnet uses only Hashtbl.add to collect POST parameters, so it is not directly vulnerable. But if the crafted request
is actually served by a handler, the handler would get a degraded table,
and could show in turn bad performance (again leading to DoS).

What are possible fixes?

1) Avoid hash tables in contexts where security is relevant. The
alternative is Set (actually a balanced binary tree), which does not
show this problem.

2) Use cryptographically secure hash functions.

3) Use "randomized" hash tables. The trick here is that there is = not a
single hash function h anymore, but a family h(1)...h(n). When the hash
table is created, one of the functions is picked randomly. This makes it
impossible to craft an attack request, because you cannot predict the
function.

I don't think 1) is viable - hash tables are too wide spread, and are loved by programmers because of their good performance. 2) would be good
in extremely critical contexts - although it is then again questionable,
because it is likely to have worse performance than 1).

So, the question is how to do 3). I see two problems here:

a) how to define the family of hash functions. Is it e.g. sufficient to
introduce an initialization vector for the Murmurhash algorithm, and
fill it randomly? How to get a random number that is good enough?

b) the Hashtbl in the standard library does not allow it to set the hash
function dynamically. Maybe one can get this effect by using first-class
modules (haven't checked).

Anyway, I think these problems are difficult enough to deserve some
discussion here. At least I cannot solve them immediately, and this
problem may exist for lots of Ocaml applications.

Gerd
--
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany =A0 =A0gerd@gerd-stolpmann.de
Creator of GODI and camlc= ity.org.
Contact details: =A0 =A0 =A0 =A0http://www.camlcity.org/contact.html
Company homepage: =A0 =A0 =A0 http://www.gerd-stolpmann.de
------------------------------------------------------------


--
Caml-list mailing list. =A0Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs


--f46d044285f255992f04b551ffba--