[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20030608134749.2D0.0@Bobanek.nowhere.cz>
Date: Sun, 8 Jun 2003 18:17:38 +0200 (MET DST)
From: "Pavel Kankovsky" <peak@...o.troja.mff.cuni.cz>
To: Nicholas Weaver <nweaver@...berkeley.edu>
Subject: Re: Algorimic Complexity Attacks
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."
Powered by blists - more mailing lists