Paper on Algorithmic Complexity Attacks

Scott A Crosby scrosby at
Thu Oct 23 02:26:48 PDT 2003

On Wed, 22 Oct 2003 12:03:34 -0600, mohit pande <pande at> writes:

> Hi Scott,
> I am a student at USC and am giving a presentation on your paper for
> a course I have taken here.

> I wanted to know what was the fix (patch) for the Bro IDS. Any idea
> on what was done to fix the problem. Was the library provided by you
> used or some other solution.

AFAIK, They have chosen to use a hybrid scheme that uses NH hash
construction (see UHASH) for small inputs and a cryptographic hash for
large inputs.

> Also, is Perl 5.8.1 vulnerable?  If not then what was the fix over
> the previous versions.

No, they fixed Perl 5.8.0. Perl 5.8.x uses a variant of Jenkin's hash
(a construction that uses two shifts, 2 adds and an XOR per byte). The
difference with 5.8.1 over 5.8.0 was to seed the initial state

In Perl 5.8.2, this will be partially reverted for binary
compatibility reasons. It will detect a long chain during insertion
and only switch to a randomized hash function if it detects itself
under attack.

The linux kernel has also been fixed to use a keyed variant of
jenkin's hash.


More information about the Bro mailing list