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: