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. -- Shawn Wagner sha...@speakeasy.org -- 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
