Re: [Caml-list] Hashtbl and security

[Shawn Wagner <shawnw@speakeasy.org>]

On Fri, 30 Dec 2011 17:44:06 +0100
Gerd Stolpmann <info@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
shawnw@speakeasy.org