On Sat, 7 Jun 2003, Nicholas Weaver wrote: > > First, let us observe the attacker needs no less than O(h) inserts (where > > h is the size of the hash table) to find a collision of an unknown hash > > function with a non-negligible probability of success. > > Actually, thanks to the Birthday paradox, it is O(sqrt(h)) when > collisions start to appear. Ugh. *bang* *bang* *bang* (This was my head hitting my desk.) Of course, you are right. Fortunately, the attacker needs much more than a single collision to carry out the kind of attack being discussed. He needs to find a set of keys S such that: 1. F(x) = F(y) for each x, y in S (where F is the hash function), 2. |S| is large enough, say \Omega(log h) (*). As far as I remember one needs to try out something like \Omega(h) randomly chosen keys to find such a set with a non-negligible probability (**). And any attacker's choice of keys can be considered random when the hash function is (pseudo)random from the attacker's POV. (*) Asymptotically equal or greater than C log h for some positive constant C. (**) Having a constant (i.e. not dependent on h) positive lower bound. > Likewise, another solution is to simply use a GOOD cryptographic > function for your hash. If, for an attacker to create h(y) == h(x), > requires the attacker to discover the key used in the hash function or > otherwise break the hash function, simply make sure that the key is > well created and use a strong cypher as the basis of the hash > function. We need a function having a (relatively) small set of results in order to build a hash table. We can also assume the information about collisions leaks out via a timing channel. Ergo, a persistent attacker can find enough collisions by trial and error. --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] "Resistance is futile. Open your source code and prepare for assimilation."
