> 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
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
"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
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-
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.
> >>
> >
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
>
"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
> 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
34 matches
Mail list logo
