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

[Ruoming Pang]

> 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