Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com