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

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

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

Also called a hash flooding attack. I like hashmap collision though.

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

How 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

I’ll venture a guess: a lot of practical attacks in the lab becomes completely impractical on a network.

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

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

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

By naively, you mean using a hash function that does not “scatter” the values properly, something like defining hash(n) = n, right?

Yes. hash(n) = n is fine in lots of cases, though its still vulnerable to the algorithmic complexity attacks as others mentioned in this thread.