4 ms·
Be careful using this with hash tables of integers in small hash tables. It looks like if applied naively it would be quite easy for this method to end up flatt
by josephg 7y ago
Be careful using this with hash tables of integers in small hash tables. It looks like if applied naively it would be quite easy for this method to end up flattening all small integer keys into bucket 0.
- corysama 7y agoI heard a story recently about that being exploited as an attack. Attackers knew some site used some DB that used a specific hash and items that hash to the same value end up in a linked list. So, the submitted a ton of user data that all hashed to the same value then DOS’d with requests that ran through the whole linked list every time.
- im3w1l 7y agoIt's called an algorithmic complexity attack, and yeah it's a known issue with hashmaps. One solution is to us a parametrized hash function with a secret key. And a second is to use another data structure entirely.
- baby 7y agoIt’s actually called a hashmap collision attack, fixed by randomizing your hash function at the program start. For example generating a key at program start that will be used with siphash.
- pbsd 7y agohttps://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf https://www.usenix.org/legacy/events/sec03/tech/full_papers/...
- baby 7y agoAlso called a hash flooding attack. I like hashmap collision though.
- rurban 7y agoNot fixed by a random seed and not fixed by siphash. Only fixable by not allowing a linear search in the collisions. (counting or promote to a tree) The random seed can by extracted, exposed or calculated, and then siphash doesn't help you at all, it just makes everything 2x slower.
- baby 7y agoHow do you extract/calculate The random seed? This is what all (non-vulnerable) programming languages do btw. PS: saw your other post, interesting take. https://news.ycombinator.com/item?id=12401920 https://news.ycombinator.com/item?id=12401920 I’ll venture a guess: a lot of practical attacks in the lab becomes completely impractical on a network.
- minitech 7y agoI like how you’ve been saying for 3+ years that it’s possible to recover a SipHash key based on its output, something it’s specifically designed not to allow, but never given any evidence for it.
- hinkley 7y agoIt doesn’t even have to be that complicated. Query parameters for HTTP requests are almost always stuffed into a hash table. You can get up to mischief a couple of packets at a time. If you’ve been watching, there have been a series of articles over the last five or so years as each language upgrades their hash table implementation to thwart this class of attack.
- lakshayg 7y agoBy naively, you mean using a hash function that does not “scatter” the values properly, something like defining hash(n) = n, right?
- josephg 7y agoYes. hash(n) = n is fine in lots of cases, though its still vulnerable to the algorithmic complexity attacks as others mentioned in this thread.
- starmole 7y agoThat was the first thing that came to my mind as well. There are two definitions of what a hash function is, and they are almost always under specified. (1) Map key to an integer (2) Map key to a uniformly distributed integer In case of (1) the hash map implementation needs to do the mixing step, (2) is much better for benchmarking as in the article.