Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: