Re:A fast alternative to the modulo reduction (2016)
by im3w1l on Sunday October 06, 2019 @08:44PM
(#21176285)
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.
[ Parent
| on HN ]
Re:A fast alternative to the modulo reduction (2016)
by baby on Sunday October 06, 2019 @09:56PM
(#21176658)
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.
Re:A fast alternative to the modulo reduction (2016)
by baby on Monday October 07, 2019 @12:58PM
(#21183134)
Also called a hash flooding attack. I like hashmap collision though.
Re:A fast alternative to the modulo reduction (2016)
by rurban on Monday October 07, 2019 @04:09AM
(#21178515)
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.
Re:A fast alternative to the modulo reduction (2016)
by baby on Monday October 07, 2019 @12:53PM
(#21183067)
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.
Re:A fast alternative to the modulo reduction (2016)
by minitech on Wednesday October 09, 2019 @06:03PM
(#21208663)
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.