Hacker News Reader

Comment by corysama | Hacker News Reader

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.

View on HN

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.

https://www.usenix.org/legacy/events/sec03/tech/full_papers/...

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.

Reply on news.ycombinator.com