Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Goswin von Brederlow
Gerd Stolpmann i...@gerd-stolpmann.de 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).

Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Goswin von Brederlow
AUGER Cédric cedric.au...@lri.fr 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,

Re: [Caml-list] Hashtbl and security

2012-02-09 Thread Gerd Stolpmann
AUGER Cédric cedric.au...@lri.fr 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

Re: [Caml-list] Hashtbl and security

2012-02-08 Thread Goswin von Brederlow
Gerd Stolpmann i...@gerd-stolpmann.de writes: Gerd Stolpmann i...@gerd-stolpmann.de 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

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 goswin-...@web.de a écrit : Gerd Stolpmann i...@gerd-stolpmann.de writes: Gerd Stolpmann i...@gerd-stolpmann.de writes: You are forgetting a variable in this. To create a DOS in the hashtable you need to hit the same bucket again

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

Re: [Caml-list] Hashtbl and security

2012-01-31 Thread Gerd Stolpmann
Gerd Stolpmann i...@gerd-stolpmann.de 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

Re: [Caml-list] Hashtbl and security

2012-01-30 Thread Goswin von Brederlow
Gerd Stolpmann i...@gerd-stolpmann.de 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

Re: [Caml-list] Hashtbl and security

2012-01-30 Thread Goswin von Brederlow
Xavier Leroy xavier.le...@inria.fr 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).

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 will

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 make hash

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 a

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 Hashtbl (the

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

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

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 cryptographically

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

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

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:

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 impossible to

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 recommended.

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 tree),

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 simplest