Denial of Service on Bro via Scott Crosby and Dan Wallach's method...fixed in bro-pub-0.8a32?

Zeek
1

Hi,

I am interested to do some further testing of this, but does the a32 release have the fixes for the hashing issue inside? (I am referring to their paper at: http://www.cs.rice.edu/~scrosby/hash/.)

Has this been extensively tested?

Tx!

Chris

2

Christopher Jay Manders wrote:

Hi,

I am interested to do some further testing of this, but does the a32
release have the fixes for the hashing issue inside? (I am referring to
their paper at: http://www.cs.rice.edu/~scrosby/hash/.)

Has this been extensively tested?

Tx!

Chris

if you look in Hash.cc, you'll see the use of MD5 as a hashing function,
although the old hashing function can still be used - it certainly is
lighter weight & thus retains a performance advantage, less the DOS
attack.

3

Jim Mellander wrote:

Christopher Jay Manders wrote:
>
> Hi,
>
> I am interested to do some further testing of this, but does the a32
> release have the fixes for the hashing issue inside? (I am referring to
> their paper at: http://www.cs.rice.edu/~scrosby/hash/.)
>
> Has this been extensively tested?
>
> Tx!
>
> Chris

if you look in Hash.cc, you'll see the use of MD5 as a hashing function,
although the old hashing function can still be used - it certainly is
lighter weight & thus retains a performance advantage, less the DOS
attack.

By the way, it seems to me that the use of MD5 as a hash function is
overkill. As I understand it, the issue is not the hash function, per
se, but the predictability of the hashing function potentially leading
to excessive chaining by the insertion of crafted packets, and thus
degrading the hashing function to a linear search.

MD5, of course, makes it computationally infeasable to develop this
chaining, but I would argue that a lighter weight solution would also
give good results, to wit:

Since the issue is the predictability of the hash, the problem really
boils down to determing a way to increase the unpredictability. One
method would be to introduce a reproducable random factor, that varies
each run of Bro.

So, on startup of Bro, precompute a 2^n size table of random numbers
derived from /dev/random, or other non-reproducable source. Then the
hashing function could select n bits from the hashed value (using the
original hash function), lookup the table & xor the value with the
computed hash. The chaining problem still exists, of course, but what
is removed is the predictability, since the table (& thus the hash
function) is specific to *that* run of bro.

Any comments?

4

but I would argue that a lighter weight solution would also give good
results, to wit:

Since the issue is the predictability of the hash, the problem really
boils down to determing a way to increase the unpredictability. One
method would be to introduce a reproducable random factor, that varies
each run of Bro.

So, on startup of Bro, precompute a 2^n size table of random numbers
derived from /dev/random, or other non-reproducable source. Then the
hashing function could select n bits from the hashed value (using the
original hash function), lookup the table & xor the value with the
computed hash. The chaining problem still exists, of course, but what
is removed is the predictability, since the table (& thus the hash
function) is specific to *that* run of bro.

Any comments?

Jim,

Thanks for your suggestion. Yes, we are looking for an implementation of a
*universal* hash function (e.g. one option is to find a stable
implementation of UMAC). I'd love to hear if you have any suggestion on
this regard.

As to the hash function you suggested, I think it would suffer the same
kind of DoS attack. Scott's paper explains it quite well -- the problem
with the original function is that it first reduces the value down to a
32-bit value with a simple function, and it is easy to find collisions for
this step so that the attacker can generate numerous strings that will be
reduced to the same 32-bit number. Afterwards, no matter what you do on
the 32-bit number can prevent collisions.

Ruoming

5

Ruoming Pang wrote:

<snip>

Jim,

Thanks for your suggestion. Yes, we are looking for an implementation of a
*universal* hash function (e.g. one option is to find a stable
implementation of UMAC). I'd love to hear if you have any suggestion on
this regard.

As to the hash function you suggested, I think it would suffer the same
kind of DoS attack. Scott's paper explains it quite well -- the problem
with the original function is that it first reduces the value down to a
32-bit value with a simple function, and it is easy to find collisions for
this step so that the attacker can generate numerous strings that will be
reduced to the same 32-bit number. Afterwards, no matter what you do on
the 32-bit number can prevent collisions.

Ruoming

Hmm, thats a good point - the reduction to a 32-bit number would still
be predictable. Why not apply the xor function to the input, then,
before the reduction takes place? - this presumably would remove the
predictability of the reduction step.