Re: Algorimic Complexity Attack on GLIB 2.2.1

[Scott A Crosby <scrosby cs rice edu>]

On Fri, 30 May 2003 23:24:09 +0100 (BST), Sander Vesik <Sander Vesik Sun COM> writes:

> On 29 May 2003, Scott A Crosby wrote:
> > 
> > I highly advise using a universal hashing library, either our own or
> > someone elses. As is historically seen, it is very easy to make silly
> > mistakes when attempting to implement your own 'secure' algorithm.
> > 
> > The abstract, paper, and a library implementing universal hashing is
> > available at   http://www.cs.rice.edu/~scrosby/hash/.
> > 
> 
> I *REALLY* hope that ghash functions do not get replace before it is shown
> that frequent heavy users like say nautilus don't suffer massive speed
> degradations as a result. Gnome as a whole is quite heavy user of teh
> hashing functions...
> 

Universal hash functions aren't performance hogs. We include benchmark
graphs in the paper. In almost all cases, an L2 cache miss dominates
the hashing cost. Also, the uhash function, for all inputs longer than
64 bytes, faster than perl's simplistic hash function.

Scott