Bugtraq mailing list archives
Re: Algorimic Complexity Attacks
From: Solar Designer <solar () openwall com>
Date: Sat, 31 May 2003 07:13:35 +0400
On Thu, May 29, 2003 at 03:33:06PM -0500, Scott A Crosby wrote:
They exploit the difference between 'typical case' behavior versus worst-case behavior. For instance, in a hash table, the performance is usually O(1) for all operations. However in an adversarial environment, the attacker constructs carefully chosen input such that large number of 'hash collisions' occur.
This is precisely one of the attacks which have been considered, avoided(*), and documented in my Phrack #53 article entitled "Designing and Attacking Port Scan Detection Tools" - "Data Structures and Algorithm Choice" back in 1998. Now you report another port scan detector (Bro) still vulnerable to this attack. I'm not surprised. (*) http://www.openwall.com/scanlogd/ As for solutions, while using a keyed hash function offers the best performance with a large enough number of entries (but not with a small one!), it is rather complicated when done right, too easy to do wrong, and may be imperfect anyway because of timing leaks (see below). It requires that a cryptographically random secret is used (and really kept secret!), that it is large enough to not be successfully brute-forced, and a cryptographic hash function is used (or it might be possible to infer the secret). This is why a hashing library like yours is needed. But for many applications it could make more sense to use another data structure and algorithm (such as binary search). Now the promised attack on using a keyed hash function with the above requirements met. Let's assume that all input to the hash function, except for the secret, is under control of an attacker. Further, let's assume that she is able to infer if a hash collision occurs by measuring the time it takes to process a request (possibly repeating each request multiple times). After a bit of trying, she will know that inputs A and B produce a collision. She will then keep A and B fixed and search for an input C which will collide with A and B. And so on. 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. -- Alexander Peslyak <solar () openwall com> GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598 http://www.openwall.com - bringing security into open computing environments
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)