From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pBUH6Y2w026173 for ; Fri, 30 Dec 2011 18:06:34 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgYCAHDu/U7UGyoClGdsb2JhbABDhQ+lCoI4IgEBAQEJCwkJFAMigXIBAQQBIzASEwYLCxoCBRYLAgIJAwIBAgFFEwgBAYd2AqREkUyBL4dGggSBFgSVAoVPjGY X-IronPort-AV: E=Sophos;i="4.71,433,1320620400"; d="scan'208";a="125089838" Received: from smtp2-g21.free.fr ([212.27.42.2]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Dec 2011 18:06:28 +0100 Received: from [192.168.1.3] (unknown [82.237.71.191]) by smtp2-g21.free.fr (Postfix) with ESMTP id 354DF4B03E6 for ; Fri, 30 Dec 2011 18:06:21 +0100 (CET) Message-ID: <4EFDEF92.3010204@inria.fr> Date: Fri, 30 Dec 2011 18:06:26 +0100 From: Xavier Leroy User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.23) Gecko/20110921 Thunderbird/3.1.15 MIME-Version: 1.0 To: caml-list@inria.fr References: <1325263446.5036.104.camel@samsung> In-Reply-To: <1325263446.5036.104.camel@samsung> X-Enigmail-Version: 1.1.2 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Hashtbl and security 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). > So, the question is how to do 3). I see two problems here: > > a) how to define the family of hash functions. Is it e.g. sufficient to > introduce an initialization vector for the Murmurhash algorithm, and > fill it randomly? IIRC, the Web pages for the Murmur family of hashes gives some statistical evidence that this approach works. > How to get a random number that is good enough? Hmm. /dev/random is your friend on the platforms that support it. Otherwise, there's always the Random module, but Random.self_init isn't very strong. - Xavier Leroy