apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dean gaudet <d...@arctic.org>
Subject Re: [PATCH 2] speedup for apr_table_t
Date Mon, 19 Nov 2001 04:14:27 GMT
On Sat, 17 Nov 2001, Brian Pane wrote:

>   * A rewrite of apr_table_overlap() that uses a hash
>     table (sort of) instead of qsort

i'm not sure this part of the patch is a good idea.  the reason
apr_table_overlap() uses qsort is to prevent various O(n^2) DoS attacks
(both time & space).  with your hash i think it's possible for attackers
to carefully construct headers such that they all hash the same, which
would result in an O(n^2) time attack.

also -- if i understand the hash you're using, it appears that all headers
less than 4 characters in length will hash to position 0?  (i'm looking at

(otherwise nice work, as always :)


View raw message