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 q02EqixU014993 for ; Mon, 2 Jan 2012 15:52:44 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvkQAELEAU/U4367kWdsb2JhbABEggWDCqdJIgEBAQEJCwsHFAMigXIBAQUjQhQQCxgCAiYCAlcGEwmHcwajLJBhgS+JSoEWBI0ajTeMZg X-IronPort-AV: E=Sophos;i="4.71,444,1320620400"; d="scan'208";a="125305360" Received: from moutng.kundenserver.de ([212.227.126.187]) by mail4-smtp-sop.national.inria.fr with ESMTP; 02 Jan 2012 15:52:18 +0100 Received: from office1.lan.sumadev.de (dslb-094-219-218-084.pools.arcor-ip.net [94.219.218.84]) by mrelayeu.kundenserver.de (node=mreu1) with ESMTP (Nemesis) id 0Mewsn-1S5bvV0dVx-00P5r3; Mon, 02 Jan 2012 15:52:16 +0100 Received: from [192.168.178.30] (546BF816.cm-12-4d.dynamic.ziggo.nl [84.107.248.22]) by office1.lan.sumadev.de (Postfix) with ESMTPSA id C31DDC00C7; Mon, 2 Jan 2012 15:52:15 +0100 (CET) From: Gerd Stolpmann To: Shawn Wagner Cc: caml-list@inria.fr In-Reply-To: <20120101162156.2f2e49f1@speakeasy.org> References: <1325263446.5036.104.camel@samsung> <20120101162156.2f2e49f1@speakeasy.org> Content-Type: text/plain; charset="UTF-8" Date: Mon, 02 Jan 2012 15:52:14 +0100 Message-ID: <1325515934.5036.199.camel@samsung> Mime-Version: 1.0 X-Mailer: Evolution 2.32.2 Content-Transfer-Encoding: 7bit X-Provags-ID: V02:K0:/0yqq8F9zbMK3pfSguFi4aFoJ+CWrz+tlLF3/dLzOtB aCIvV0qtzixiCCIfjMVW5Mp6Gingm7Hztn3IaAAtfK/OTByJjo E1a6jn8d3L/orNdKU3ISv4WJkLBocr3JuWPcTmGl5+dwfO8lVn 2FzlaSwg+kU8snm/JplW+erQLzQeMRAOV2pnQcoJA0pWdJ8PNA wKQ0/IQbcAs/jNbrYhSMKQfBK40N+EhJn141TthV6rZitwf0Hm 2VGdY81Twx/9fsqVv8xePB8YdgBD+5kpBR7ImvE0o6GHKIONPt FJN98VKq6qwJLgapvlsPnzFpc4LhLZvmE8bBADEBJQDjl2yUwn KrbNH5Vfo9657VmQeiVso1//Ek4QsfnYeAVWExetV Subject: Re: [Caml-list] Hashtbl and security 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 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. When I overlook this correctly, this is just a trick to use more bits. So when you double-hash with two functions that deliver 30 bits each you'll effectively have the same security as 60 bits - provided these functions are really independent of each other. The choice of the functions is crucial, IMHO. I have no idea how you would choose them so that when you crack one of these, you don't know anything about the other. Of course, you could use a secure hash function like SHA-1 and take distinct ranges of bits, but I think this is more an implementation of 2), and not what you really mean. Is there any cryptanalysis of this approach? Gerd -- ------------------------------------------------------------ Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de Creator of GODI and camlcity.org. Contact details: http://www.camlcity.org/contact.html Company homepage: http://www.gerd-stolpmann.de ------------------------------------------------------------