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 pBV0xqWg003081
	for <caml-list@sympa-roc.inria.fr>; Sat, 31 Dec 2011 01:59:52 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AswCABNd/k7AbSoIe2dsb2JhbABDhQ+lDYI4IgEBFiYEIYFyAQEFIwQ+FBALCQ8CAiYCAhQYMYgPpACRKBOBHIlKM2MEjUeHOpI2
X-IronPort-AV: E=Sophos;i="4.71,435,1320620400"; 
   d="scan'208";a="137328142"
Received: from einhorn.in-berlin.de ([192.109.42.8])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 31 Dec 2011 01:59:46 +0100
X-Envelope-From: oliver@first.in-berlin.de
Received: from first (e178004174.adsl.alicedsl.de [85.178.4.174])
	(authenticated bits=0)
	by einhorn.in-berlin.de (8.13.6/8.13.6/Debian-1) with ESMTP id pBV0xjKs031169
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT);
	Sat, 31 Dec 2011 01:59:46 +0100
Received: by first (Postfix, from userid 1000)
	id C2BC5154036A; Sat, 31 Dec 2011 01:59:45 +0100 (CET)
Date: Sat, 31 Dec 2011 01:59:45 +0100
From: oliver <oliver@first.in-berlin.de>
To: Xavier Leroy <Xavier.Leroy@inria.fr>
Cc: caml-list@inria.fr
Message-ID: <20111231005945.GB2801@siouxsie>
References: <1325263446.5036.104.camel@samsung>
 <4EFDEF92.3010204@inria.fr>
 <20111231005721.GA2801@siouxsie>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <20111231005721.GA2801@siouxsie>
User-Agent: Mutt/1.5.20 (2009-06-14)
X-Scanned-By: MIMEDefang_at_IN-Berlin_e.V. on 192.109.42.8
Subject: Re: [Caml-list] Hashtbl and security

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), which does not
> > > show this problem.
> > 
> > Highly recommended.  Nothing beats guaranteed O(log n) operations.
> > 
> > > 2) Use cryptographically secure hash functions.
> > 
> > Hopeless: with a hash size of 30 bits, as in Caml, or even 64 bits,
> > there are no 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. 
> > 
> > Indeed.  The optional "seed" parameter to Hashtbl.create does exactly
> > this in the new implementation of Hashtbl (the one based on Murmur3).
> [...]
> 
> 
> Where is this?
> 
> I found  Hashtbl.HashedType.hash  with type t -> int.

And there is "val hash_param : int -> int -> 'a -> int"
but I'm not sure if this adresses the issue.

Ciao,
   Oliver