Re: Re: Re: Hash Clash on purpose

I'm impressed. 10,000 strings of 24 bytes sent in a 200kb query. I want to know how you pulled that off. :)

Thanks for the experimental result; I'll note this thread on the webpage. Also remember that the behavior is quadratic. 20,000 strings, 500kbyte, would take 12 minutes. 100,000 strings would run for 5 hours.

Scott Crosby

Comment on Re: Re: Re: Hash Clash on purpose

Replies are listed 'Best First'.
Re: Re: Re: Re: Hash Clash on purpose by iburrell (Chaplain) on Jun 03, 2003 at 01:03 UTC
200 KB comes from sloppy rounding. It is possible to use shorter strings. There is a bug in how Perl puts hashes in buckets that makes pathological hashes more likely. The paper generated strings that all have the same hash value. It is much easier to find strings that all go in the same hash bucket. tye wrote a patch that fixes this bug and recently got it accepted. tilly wrote a generator that uses the bug to quickly find strings that produce pathological hashes. About 1/8 of all strings fit the criteria. Using simple alphabetic strings, I can get 60000 strings encoded 300000 bytes that all go in the same bucket. Inserting all of those into a hash takes 10 minutes for direct insert and much longer for CGI parsing.	[reply]

Replies are listed 'Best First'.

Re: Re: Re: Re: Hash Clash on purpose
by iburrell (Chaplain) on Jun 03, 2003 at 01:03 UTC

It is possible to use shorter strings. There is a bug in how Perl puts hashes in buckets that makes pathological hashes more likely. The paper generated strings that all have the same hash value. It is much easier to find strings that all go in the same hash bucket. tye wrote a patch that fixes this bug and recently got it accepted.

tilly wrote a generator that uses the bug to quickly find strings that produce pathological hashes. About 1/8 of all strings fit the criteria. Using simple alphabetic strings, I can get 60000 strings encoded 300000 bytes that all go in the same bucket. Inserting all of those into a hash takes 10 minutes for direct insert and much longer for CGI parsing.

[reply]