Re: Algorimic Complexity Attacks

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

On Sun, 8 Jun 2003, Nicholas Weaver wrote:

> IF the hash is good, FINDING collisions doesn't necessarily help the
> attacker, as the attacker really needs to generate lots of collisions
> to make the searches O(n) instead of O(1), since that is teh key
> behind this attack.

First, I myself assume the hash function is quite difficult to crack and
it takes \Omega(n) (oracle) operations to find a large set of colliding
keys (with a nonnegligible probability, as usual) using the implementation
as a "collision oracle". On the other hand, I do not assume the function
is really uncrackable and this makes it possible to use simpler functions
that take *much* less time to compute than crypto hashes.

Second, indeed, it is much easier to carry out this kind of attack when
an attacker is able to compute colliding keys asking the oracle as few
questions as possible (i.e. hash function that is easy to crack), perhaps
even not asking any questions (i.e. any hardcoded hash function).
Nevertheless, even a situation when one needs a long and tedious
preparation phase to find collisions by trial and error (e.g. insert
a pair of entries into the hash table, ask the oracle whether a
collision was found, remove those entries from the table to keep a low
profile (!), repeat ad nauseam) may be interesting: an attacker spends
a day, a week or perhaps a month probing a target system for hash
collisions but once a sufficiently large set of collisions is found,
he can strike and disable/slow down the target system at will (assuming
the hash function is not changed in the meantime).


--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."