User: Password:
|
|
Subscribe / Log in / New account

Denial of service via hash collisions

Denial of service via hash collisions

Posted Jan 12, 2012 17:50 UTC (Thu) by niner (subscriber, #26151)
In reply to: Denial of service via hash collisions by luto
Parent article: Denial of service via hash collisions

"Some of them can be very fast, at least on long inputs."

That's probably just not good enough. Languages like Perl and Python use hashes at the very core of their object models for accessing object attributes and methods (a bit of a simplification but the point stands). So even a small decrease in hashing performance will have serious impact on the performance of programs written in those languages.


(Log in to post comments)

Denial of service via hash collisions

Posted Jan 13, 2012 20:46 UTC (Fri) by wahern (subscriber, #37304) [Link]

A hash need only be computed once for an object, so it all depends on what the code is doing. For $bar->foo(), "foo" can be hashed once at compile time. But if I'm doing $bar{generatekey()}->(), where &generatekey creates a brand-spanking new string object each time, then, yes, it *might* matter.

But a lot depends on the algorithm. If the algorithm can be parallelized using SIMD or MIMD instructions--or just operating on longer words than a single (char)--then it doesn't necessarily matter that the hash is more complex; all that matters is whether the CPU can finish the job as fast as a simpler algorithm that updates state on every character.

The reason why universal hashes, etc, are competitive with brain-dead hashes for longish strings is because of cache locality--it takes longer to move data back-and-forth from cache then it does to compute even the more complex operations. So, again, you might still be able to compete with simpler algorithms if you still share the same bottleneck. There may be exploitable bottlenecks even for short, cache-local strings.

I don't think there has been enough work in this area. People have continued using the same hashes invented in the 1990s, in particular DJB's algorithm. As an aside, DJB fawns over "crit-bit" trees: http://cr.yp.to/critbit.html


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds