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 q020M5S5016634 for ; Mon, 2 Jan 2012 01:22:05 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AuoDAAT4AE/PkYDzmWdsb2JhbABDggWqUiIBAQEBAQgLCwcUJYFyAQEFOiskCxguVxmvMIw0iHWDGgSIN4xKhXCMZg X-IronPort-AV: E=Sophos;i="4.71,442,1320620400"; d="scan'208";a="137458582" Received: from asbnvacz-mailrelay01.megapath.net ([207.145.128.243]) by mail1-smtp-roc.national.inria.fr with ESMTP; 02 Jan 2012 01:21:59 +0100 Received: from mail5.sea5.speakeasy.net (mail5.sea5.speakeasy.net [69.17.117.49]) by asbnvacz-mailrelay01.megapath.net (Postfix) with ESMTP id D347BA70783 for ; Sun, 1 Jan 2012 19:21:57 -0500 (EST) Received: (qmail 21185 invoked from network); 2 Jan 2012 00:21:57 -0000 Received: by simscan 1.4.0 ppid: 27654, pid: 3071, t: 0.4818s scanners: clamav: 0.88.2/m:52/d:10739 spam: 3.0.4 Received: from unknown (HELO localhost.localdomain) (shawnw@[75.146.51.254]) (envelope-sender ) by mail5.sea5.speakeasy.net (qmail-ldap-1.03) with SMTP for ; 2 Jan 2012 00:21:57 -0000 Date: Sun, 1 Jan 2012 16:21:56 -0800 From: Shawn Wagner To: caml-list@inria.fr Message-ID: <20120101162156.2f2e49f1@speakeasy.org> In-Reply-To: <1325263446.5036.104.camel@samsung> References: <1325263446.5036.104.camel@samsung> X-Mailer: Claws Mail 3.8.0 (GTK+ 2.24.8; x86_64-unknown-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on mail5.sea5 X-Spam-Level: * Subject: Re: [Caml-list] Hashtbl and 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 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. > There's also an option 4 that's barely been mentioned in any discussion of this issue I've seen: Use a hash table implementation that handles collisions in another way than having each bucket be a linked list. Double hashing and cuckoo hashing come to mind, where an attacker would have to find keys that map to the same value for not one, but two or more different hash functions. -- Shawn Wagner shawnw@speakeasy.org