Date: Sat, 31 May 2003 07:13:35 +0400
From: Solar Designer <solar@...nwall.com>
To: Scott A Crosby <scrosby@...rice.edu>
Subject: Re: Algorimic Complexity Attacks


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@...nwall.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

Powered by blists - more mailing lists