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 Stolpmann, Darmstadt, Germany
Creator of GODI and
Contact details:
Company homepage:

Caml-list mailing list.  Subscription management and archives:
Beginner's list:
Bug reports:

Reply via email to