• Subject: Re: Hash Table Collisions (n.runs-SA-2011.004)
• From: Gé Weijers <ge@...>
• Date: Thu, 29 Dec 2011 11:46:09 -0800

I should probably rephrase that:

C(N,K) is the number of different sets of K hash positions on an N-character string

C(N-K,4)/C(N,4) is the probability of selecting 4 positions that do not match any of the K positions selected by a randomized hash.

On Thu, Dec 29, 2011 at 11:43 AM, Gé Weijers wrote:

On Thu, Dec 29, 2011 at 11:07 AM, Javier Guerra Giraldez wrote:
I think that a simple solution, like making the char-skipping method
different for every Lua State should be enough.

The question is: how likely would it be to select, say, 4 character positions at random and not select any of the positions a perfectly randomized skipping method uses to calculate the hash.

On an N-character string and a K (31 for Lua) character hash there are C(N,K) hash positions and the likelyhood of selecting those positions is C(N-K,4)/C(N,4).

If my math is correct an adversary would have about 50% chance of selecting 4 different (unequal to the 31 being used by Lua) positions if N=200, and still have about 20% chance if N=100. And the adversary can try again with different values. Probably not good enough.

--

--