Am Sonntag, den 01.01.2012, 16:21 -0800 schrieb Shawn Wagner: > On Fri, 30 Dec 2011 17:44:06 +0100 > Gerd Stolpmann <i...@gerd-stolpmann.de> 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 g...@gerd-stolpmann.de Creator of GODI and camlcity.org. Contact details: http://www.camlcity.org/contact.html Company homepage: http://www.gerd-stolpmann.de ------------------------------------------------------------ -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
