Bugtraq mailing list archives
Re: Algorimic Complexity Attacks
From: Nicholas Weaver <nweaver () CS berkeley edu>
Date: Sat, 7 Jun 2003 12:35:58 -0700
Pardon me if this is obvious to everyone already... On Sat, Jun 07, 2003 at 07:01:06PM +0200, Pavel Kankovsky composed:
Changing the secret once in a while reduces this attack and may well make it impractical with many particular applications. Note that one doesn't have to use any additional true randomness (and possibly exhaust the randomness pool) for each new secret to be used with the keyed hash. If the secret itself is not leaked in the attack (and it shouldn't be), something as simple as secret++ could suffice. However, this does have its difficulty: maintaining existing entries.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.
This means the attack will be thwarted if the secret hash function (e.g. a universal hash function using a secret parameter) is changed every O(h) inserts.
Actually, thanks to the Birthday paradox, it is O(sqrt(h)) when collisions start to appear. Possibly a better solution is to simply make the buckets themselves use (lg(n)) search behavior rather than linear search behavior. EG, if the hash buckets are based on skiplists rather than linked lists, this provides expected O(lg(n)) search time in the bucket instead of O(n), with O(lg(n)) instert, unless the adversary can predict the random sequence used by the skiplist. 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. In that case, for a smaller table size, collisions WILL occur, but as long as they can't be maliciously generated by an adversary, there isn't a problem as the attacker can't turn the expected O(1) search into expected O(n) search on a single bucket. The problem is not that hash-tables have collisions, but that a malicious attacker can generate collisions at-will. -- Nicholas C. Weaver nweaver () cs berkeley edu
Current thread:
- Re: Algorimic Complexity Attacks Solar Designer (Jun 01)
- Re: Algorimic Complexity Attacks Pavel Kankovsky (Jun 07)
- Re: Algorimic Complexity Attacks Nicholas Weaver (Jun 07)
- Re: Algorimic Complexity Attacks Pavel Kankovsky (Jun 09)
- Re: Algorimic Complexity Attacks Nicholas Weaver (Jun 09)
- Re: Algorimic Complexity Attacks Pavel Kankovsky (Jun 23)
- Re: Algorimic Complexity Attacks Götz Babin-Ebell (Jun 24)
- Re: Algorimic Complexity Attacks Nicholas Weaver (Jun 07)
- Re: Algorimic Complexity Attacks Pavel Kankovsky (Jun 07)