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 q2CI1gxK016658 for ; Mon, 12 Mar 2012 19:01:42 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhgFAD85Xk/UGyoCkWdsb2JhbABDgwmxQgSBCCIBAQEBCQsLBxQDJIIJAQEEAVMlBgsLIRYPCQMCAQIBRRMIAQGIAQkHvAqKNRyDDoMiBJVMhWmNHoFb X-IronPort-AV: E=Sophos;i="4.73,570,1325458800"; d="scan'208";a="148907025" Received: from smtp2-g21.free.fr ([212.27.42.2]) by mail1-smtp-roc.national.inria.fr with ESMTP; 12 Mar 2012 19:01:29 +0100 Received: from [192.168.1.3] (unknown [82.237.71.191]) by smtp2-g21.free.fr (Postfix) with ESMTP id 689354B0206 for ; Mon, 12 Mar 2012 19:01:25 +0100 (CET) Message-ID: <4F5E3A6E.4010406@inria.fr> Date: Mon, 12 Mar 2012 19:03:26 +0100 From: Xavier Leroy User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.27) Gecko/20120216 Thunderbird/3.1.19 MIME-Version: 1.0 To: caml-list@inria.fr References: <4F3078F1.8070105@redhat.com> <4F3079F7.4040606@redhat.com> <20120207083412.GA30350@annexia.org> <20120310073113.GA16716@annexia.org> In-Reply-To: <20120310073113.GA16716@annexia.org> X-Enigmail-Version: 1.1.2 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003) 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