Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Gerd Stolpmann
> AUGER Cédric writes: > >> More seriously, hashtables are here to store values, so you don't want >> want to have a hash value bigger than (2^30)-1. >> >> In fact even such a value is too big for that purpouse IMHO, since on a >> 4Gio RAM computer, it will take half it to store the table, assum

Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Goswin von Brederlow
AUGER Cédric writes: > More seriously, hashtables are here to store values, so you don't want > want to have a hash value bigger than (2^30)-1. > > In fact even such a value is too big for that purpouse IMHO, since on a > 4Gio RAM computer, it will take half it to store the table, assuming > eac

Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Goswin von Brederlow
"Gerd Stolpmann" writes: > Well, looks like that the upper 32 bits aren't considered at all for > computing the hash value. This is for sure surprising - I would have > expected that these bits somehow go in to the final value (e.g. that they > are xor-ed with the lower half). > > My guess is tha

Re: [Caml-list] Hashtbl and security

2012-02-08 Thread Gerd Stolpmann
Well, looks like that the upper 32 bits aren't considered at all for computing the hash value. This is for sure surprising - I would have expected that these bits somehow go in to the final value (e.g. that they are xor-ed with the lower half). My guess is that this was done to ensure that an int-

Re: [Caml-list] Hashtbl and security

2012-02-08 Thread AUGER Cédric
Le Wed, 08 Feb 2012 10:41:03 +0100, Goswin von Brederlow a écrit : > "Gerd Stolpmann" writes: > > >> Gerd Stolpmann writes: > >> 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. > >> > >

Re: [Caml-list] Hashtbl and security

2012-02-08 Thread Philippe Wang
On Wed, Feb 8, 2012 at 10:41 AM, Goswin von Brederlow wrote: > [...] > Maybe the size of the hashtable indeed isn't the problem but the hash > function. Here is something odd: > > # for i = 1 to 63 do Printf.printf "%d %d\n" (1 lsl i) (Hashtbl.hash (1 lsl > i)) done;; > 2 2 > 4 4 > 8 8 > 16 16 >

Re: [Caml-list] Hashtbl and security

2012-02-08 Thread Goswin von Brederlow
"Gerd Stolpmann" writes: >> Gerd Stolpmann writes: >> 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 r

Re: [Caml-list] Hashtbl and security

2012-01-31 Thread Gerd Stolpmann
> 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 s

Re: [Caml-list] Hashtbl and security

2012-01-30 Thread Goswin von Brederlow
Xavier Leroy writes: > On 01/01/2012 01:52 PM, Richard W.M. Jones wrote: >> On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: >>> Indeed. The optional "seed" parameter to Hashtbl.create does exactly >>> this in the new implementation of Hashtbl (the one based on Murmur3). >> >> It m

Re: [Caml-list] Hashtbl and security

2012-01-30 Thread Goswin von Brederlow
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

Re: [Caml-list] Hashtbl and security

2012-01-04 Thread oliver
On Wed, Jan 04, 2012 at 06:56:11PM +0100, Damien Doligez wrote: > On 2012-01-02, at 02:43, oliver wrote: > > > If the type is an abstract type, which comes from something like > > Hashtbl.Randomseed > > and has type t, not type int, this problem would vanish. > > You have to be careful. If we ma

Re: [Caml-list] Hashtbl and security

2012-01-04 Thread Damien Doligez
On 2012-01-02, at 02:43, oliver wrote: > If the type is an abstract type, which comes from something like > Hashtbl.Randomseed > and has type t, not type int, this problem would vanish. You have to be careful. If we make hash table randomization mandatory, the Frama-C people will hate us, as wil

Re: [Caml-list] Hashtbl and security

2012-01-02 Thread Gerd Stolpmann
Am Sonntag, den 01.01.2012, 16:21 -0800 schrieb Shawn Wagner: > On Fri, 30 Dec 2011 17:44:06 +0100 > Gerd Stolpmann wrote: > > > > What are possible fixes? > > > > 1) Avoid hash tables in contexts where security is relevant. The > > alternative is Set (actually a balanced binary tree), which doe

Re: [Caml-list] Hashtbl and security

2012-01-02 Thread David MENTRE
Hello, 2012/1/1 Gerd Stolpmann : > Am Sonntag, den 01.01.2012, 18:29 +0100 schrieb Xavier Leroy: >> On 01/01/2012 01:52 PM, Richard W.M. Jones wrote: [...] >> > It may be worth noting that Perl solved this problem (back in 2003) by >> > unconditionally using a seed which is a global set to a rando

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread oliver
On Mon, Jan 02, 2012 at 12:58:03AM +0100, Gerd Stolpmann wrote: [...] > > > What I could imagine is a module Sys.Security where all security > > > features are accessible and configurable, e.g. > > > > I doubt that this makes sense. > > Nearly anything that can be programmed can become a security

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread Shawn Wagner
On Fri, 30 Dec 2011 17:44:06 +0100 Gerd Stolpmann wrote: > > 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 functio

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread Gerd Stolpmann
Am Montag, den 02.01.2012, 00:24 +0100 schrieb oliver: > > I understand it very well that adding support for cryptographically > > secure random numbers to core Ocaml is a challenge. There is no POSIX > > API, and /dev/random is, although widely available, still non-standard. > [...] > > And also

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread oliver
On Sun, Jan 01, 2012 at 10:04:03PM +0100, Gerd Stolpmann wrote: > Am Sonntag, den 01.01.2012, 18:29 +0100 schrieb Xavier Leroy: > > On 01/01/2012 01:52 PM, Richard W.M. Jones wrote: > > > On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: > > >> Indeed. The optional "seed" parameter to

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread Gerd Stolpmann
Am Sonntag, den 01.01.2012, 18:29 +0100 schrieb Xavier Leroy: > On 01/01/2012 01:52 PM, Richard W.M. Jones wrote: > > On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: > >> Indeed. The optional "seed" parameter to Hashtbl.create does exactly > >> this in the new implementation of Hasht

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread Xavier Leroy
On 01/01/2012 01:52 PM, Richard W.M. Jones wrote: > On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: >> Indeed. The optional "seed" parameter to Hashtbl.create does exactly >> this in the new implementation of Hashtbl (the one based on Murmur3). > > It may be worth noting that Perl s

Re: [Caml-list] Hashtbl and security

2012-01-01 Thread Richard W.M. Jones
On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: > Indeed. The optional "seed" parameter to Hashtbl.create does exactly > this in the new implementation of Hashtbl (the one based on Murmur3). It may be worth noting that Perl solved this problem (back in 2003) by unconditionally using

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread oliver
On Fri, Dec 30, 2011 at 06:40:30PM +0100, ri...@happyleptic.org wrote: > I will probably tell something very stupid, but HTML specs > do not prevent a client to post 1M values with the same name, > so whatever your hash function you cannot do much, can you? [...] That's a feature. > > The simpl

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread oliver
On Sat, Dec 31, 2011 at 01:57:21AM +0100, oliver wrote: > On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: > > On 12/30/2011 05:44 PM, Gerd Stolpmann wrote: > > > > > 1) Avoid hash tables in contexts where security is relevant. The > > > alternative is Set (actually a balanced binary

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread oliver
On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote: > On 12/30/2011 05:44 PM, Gerd Stolpmann wrote: > > > 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. > > Highly recommend

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread oliver
On Fri, Dec 30, 2011 at 05:44:06PM +0100, 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 [...] Fixed in Perl in 2003. 28C3-Talk: http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Gerd Stolpmann
Am Freitag, den 30.12.2011, 15:52 -0500 schrieb Yaron Minsky: > It's not clever in that way. It does try to do a good job of keeping > the memory impact of the tree low, but you maintain O(1) by having a > low load factor, and therefore trees of constant size. You can take a > look at the code he

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Gerd Stolpmann
Am Freitag, den 30.12.2011, 18:06 +0100 schrieb Xavier Leroy: > > 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 > > impos

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Yaron Minsky
It's not clever in that way. It does try to do a good job of keeping the memory impact of the tree low, but you maintain O(1) by having a low load factor, and therefore trees of constant size. You can take a look at the code here: https://bitbucket.org/yminsky/ocaml-core/src/8e757d8f7309/base/co

RE: [Caml-list] Hashtbl and security

2011-12-30 Thread David Allsopp
Yaron Minsky wrote: > 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 hasht

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Edgar Friendly
Not a problem, other than memory waste (which doesn't matter the key). Hashtbl.add prepends to the front of the list, so it'll be fast. And Hashtbl.find will match the head of the list, and return quickly too. Hashtbl.find_all will have to go through the whole list, but that's expected. E. On Fr

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread rixed
I will probably tell something very stupid, but HTML specs do not prevent a client to post 1M values with the same name, so whatever your hash function you cannot do much, can you? The simplest solution I can think of that prevents all attacks of this kind (but could reject some valid POST in theo

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Xavier Leroy
On 12/30/2011 05:44 PM, Gerd Stolpmann wrote: > 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. Highly recommended. Nothing beats guaranteed O(log n) operations. > 2) Use cryptographical

Re: [Caml-list] Hashtbl and security

2011-12-30 Thread Yaron Minsky
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

[Caml-list] Hashtbl and security

2011-12-30 Thread Gerd Stolpmann
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