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