5 ms·
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 sa
by corysama 7y ago
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.
- im3w1l 7y agoIt'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.
- hinkley 7y agoIt 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.