Re: [Caml-list] Hashtbl and security

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Am Sonntag, den 01.01.2012, 16:21 -0800 schrieb Shawn Wagner:
> 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. 

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
------------------------------------------------------------