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 q0VEH1Xa019423 for ; Tue, 31 Jan 2012 15:17:01 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjkEAIb3J0/U4366k2dsb2JhbABDnhaQSiIBAQEBCQkLCRQDIoFyAQEDAQEYTQkLBQsFBiUhRRIGEwkIAYdqAwa5D4sQLAYBKhMCgn4LAgIBBBMLBAZZCggDMoMsBI0uF5ow X-IronPort-AV: E=Sophos;i="4.71,596,1320620400"; d="scan'208";a="142216350" Received: from moutng.kundenserver.de ([212.227.126.186]) by mail1-smtp-roc.national.inria.fr with ESMTP; 31 Jan 2012 15:16:39 +0100 Received: from office1.lan.sumadev.de (dslb-188-097-001-058.pools.arcor-ip.net [188.97.1.58]) by mrelayeu.kundenserver.de (node=mrbap2) with ESMTP (Nemesis) id 0Mh6vJ-1SDry01wQb-00MIqc; Tue, 31 Jan 2012 15:16:38 +0100 Received: from gps.dynxs.de (localhost [127.0.0.1]) by office1.lan.sumadev.de (Postfix) with ESMTP id A2FAEC0714; Tue, 31 Jan 2012 15:16:36 +0100 (CET) Received: from 84.107.248.22 (SquirrelMail authenticated user gerd) by gps.dynxs.de with HTTP; Tue, 31 Jan 2012 15:16:37 +0100 Message-ID: <403c4e4bb2cfce801aad217c80365879.squirrel@gps.dynxs.de> In-Reply-To: <87zkd531kl.fsf@frosties.localnet> References: <1325263446.5036.104.camel@samsung> <87zkd531kl.fsf@frosties.localnet> Date: Tue, 31 Jan 2012 15:16:37 +0100 From: "Gerd Stolpmann" To: "Goswin von Brederlow" Cc: caml-list@inria.fr User-Agent: SquirrelMail/1.4.21 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 X-Priority: 3 (Normal) Importance: Normal X-Provags-ID: V02:K0:BCLXwCgnykZiFMmawLc/Hnwqlrzg25hn++DSP1dC7ZX UnNpY2CtAMxXddPtRQtBY/RfMa8KJc8zrwxDgKQX4wfB/hD2U6 p2l6iTaUqBIacubL3DJaZnRbnGI2HZA0MeDjo8P3/oiafyYcRw Pr0yRWxNELfZ2hWnd/ryUIVOhtNtc8nRn/xgCEOeKuGGUoc0tJ EssLk+SJkthTSoSl5f53yOeZ48kM0x+rbW2doyNZXG0DF7pPY5 32vvm6tuPmwyseJ2mGh7jNcKV0uJvaruqOnY6yvj31SqU2caXZ AsCCKp7r8LJQau+qhbX8Esie1NkEo26T5PZamSAQMa3OzeJuFu jHFRxMysxLrZeZnXn8QOPUgP0KwDb07UQ1zaTSBR0Qo0uA3kWG x1VTVIxyyJI0Ih+UKQTwD+sD7VpTJx6PjQ= Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q0VEH1Xa019423 Subject: Re: [Caml-list] Hashtbl and security > Gerd Stolpmann writes: > >> 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. > > Unfortunately O(log n) > O(1) and that can be a deciding factor in the > overall runtime. Even for small n your code then runs 2,3,4,... times > slower. > >> 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 > > You are forgetting a variable in this. To create a DOS in the hashtable > you need to hit the same bucket again and again. And bucket = hash % size. > > You focused on the hash but lets talk about the size for a moment. > > The size is rather limited and large hashtabels simply won't increate > size anymore and allways have lots of collisions. So even if someone > isn't actively trying to create DOS the performace still tanks as you > add more items. I cannot completely follow here. If you add more elements, the bucket array is resized. The ocaml Hashtbl does this when the number of elements exceeds half of the array size. The argument of Hashtbl.create is only the initial size of the bucket array. The upper bound is Sys.max_array_length, of course. Granted, on 32 bit platforms it is low (4M). But nobody of sound mind would run ocaml programs on 32 bit for production purposes. (If you do, consider to switch. You can use more memory and get a little performance boost, not only for ocaml programs.) Gerd > And this isn't only a problem in ocaml. The glib hashtable also has a > maximum size in the 32bit range for example. > > > So for ocaml the first thing that needs to be fixed is to allow larger > size arrays of buckets. > > MfG > Goswin > > -- > 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 > > > -- 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 *** Searching for new projects! Need consulting for system *** programming in Ocaml? Gerd Stolpmann can help you.