Re: Algorimic Complexity Attack on GLIB 2.2.1

[Sander Vesik <Sander Vesik Sun COM>]

On 30 May 2003, Scott A Crosby wrote:

> 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.
> 

which show you are at the very least 3 - 9 time slower than an example
simple hash like xor12. I really don't know where you got the idea that
the string hashing function was supposed to be secure or why you
overlooked the fact that the function to use on the keys is one of the
inputs the hash table creation function takes. I don't understand your
insistence of not even first looking at the problem domian before
attacking it.

> Scott
> 

	Sander

OpenOffice.org - conquering the world 14000 PC-s at a time