Breaking Murmur: Hash-flooding DoS Reloaded(emboss.github.com)
emboss.github.com
Breaking Murmur: Hash-flooding DoS Reloaded
http://emboss.github.com/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/
2 comments
Hmm, that's an interesting idea. Although I could imagine that this approach ultimately leads to something like Universal Hashing. For example, if the functions you would use in your example are not randomized in some way, an attacker could still predict predict outputs and when the switches would be made and could adapt appropriately. So you would randomize your functions. From there, it is probably not too far until we end up with Universal Hashing. Still, very interesting thought!
What a delightful breath of fresh air. I get awfully tired of the hash-tables-are-constant-time and worst-case-behavior-is-too-rare-to-worry-about nonsense that floods the web.
And here we have the problem and proposed solutions clearly explained, and presented in a pleasant, readable design.
Excellent post. Keep up the good work.
And here we have the problem and proposed solutions clearly explained, and presented in a pleasant, readable design.
Excellent post. Keep up the good work.
Thank you! I hope we (or others) can manage to break some more hashes to raise the awareness of this problem! See also this nice example for btrfs:
http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/
http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/
That would mean you (except for that 'am I under attack' check, but that can be a single 'if' in code that, normally, rarely runs) only pay the price of having a robust hash when you are under attack. Your data structure would also have a 'hiccup' when switching hash algorithm, but that isn't that much different from what happens when you resize your hash table as it fills up.
Does that make sense, or am I overlooking something?