User: Password:
Subscribe / Log in / New account

Denial of service via hash collisions

Denial of service via hash collisions

Posted Jan 13, 2012 20:46 UTC (Fri) by wahern (subscriber, #37304)
In reply to: Denial of service via hash collisions by niner
Parent article: Denial of service via hash collisions

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:

(Log in to post comments)

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