Re: Algorimic Complexity Attacks

["Pavel Kankovsky" <peak () argo troja mff cuni cz>]

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