Paper on Algorithmic Complexity Attacks

[Scott A Crosby]

On Wed, 22 Oct 2003 12:03:34 -0600, mohit pande <pande at usc.edu> 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
randomly.

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.

Scott