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).
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,
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
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
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
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
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
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
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).
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
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
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
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
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
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
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
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
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
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
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:
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
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.
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),
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
24 matches
Mail list logo
