3 ms·
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. A
by im3w1l 7y ago
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.
- 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.