5 ms·
An interesting technique - construct requests that produce pathological hashes (which degrade to linked lists, which have O(n^2) insertions). Make it big enoug
by Groxx 15y ago
An interesting technique - construct requests that produce pathological hashes (which degrade to linked lists, which have O(n^2) insertions). Make it big enough, and you tank the server. It may be useful to note their link to a previous article, which implies this has been known since 2003 in Perl.[1] Any news of actual attacks using this technique?
The great part is that, as long as you convert request params into hashes (a reasonable step, I'd imagine the vast majority of web frameworks do this), you're screwed if your language is vulnerable to this. Of course, you can tweak your framework to not use native hashes (or detect such attacks and handle them separately), but that's not generally an option as it's a pretty involved operation.
I wonder: would a hashtable that uses cuckoo hashes be vulnerable? Technically, sure, but would it make the attack infeasible due to the difficulty in creating double-collisions? Or is that not as hard as I'm thinking it could be?
[1]: http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec...
- extension 15y agoTo fix it at the framework level, assuming the language gives me access to the hash values, I would probably keep a second table mapping hashes to keys. Then I can tell the difference between collisions and dupes. Just kill the request once there are more than a few collisions.
- Groxx 15y agoDupes aren't the problem, it's duplicate hashes of different data. Dupes should just override the previous value, which matches other hashtable behavior, and works in O(1). Some frameworks may add them to an array, but that's likely to be a real array, or a double-ended queue, or something easier to append to than a plain linked list like hashtables use (because they don't need anything else - to append, they need to check equality on every entry in the list, so they must traverse the whole thing every time, causing the O(n^2) time).
- extension 15y agoThat's why I would keep a hash->key table. If the hash matches but the key doesn't, it's a collision.
- Groxx 15y agoThat's exactly what hashtables do. When they find collisions, they add it to a list of keys that hash to the same value. They do this to be able to return valid data when you request a key - otherwise, you'd find them rarely and seemingly randomly forgetting data or overriding with unrelated values. It's a useful behavior, and it's the very source of the problem. One way to prevent this attack is to use a hashtable that has a limit on the number of collisions per table, or per key, and throw an exception when it's exceeded. The problem is that doing so by default would break valid uses in very surprising ways in favor of protecting against an unlikely and probably unknown (when designed) attack, which you won't do, because that shouldn't be handled by basic datatypes.
- anonymoushn 15y agoWhile it is true that traversing the entire list takes O(n^2) time, it also takes O(n) time.
- deleted 15y ago[deleted]
- mdwe 15y agoHe is talking about the total creation time -- putting n distinct elements into the same hash bucket means traversing to the end n times for an overall o(n^2) time
- ced 15y agoIsn't it trivially easy to defend against by adding a secret character/number to all of your keys, eg.: "dog" becomes "dogu" and "julia" becomes "juliau"? In fact, why not do this at the language level? python could pick a random character at startup, and use it for the duration of the process.
- mikeash 15y agoA single character wouldn't be any good, since it would be trivial to discover which one was in use by brute force. A longer salt would probably work, but there may well be ways for an attacker to discover the salt in use, and longer salts mean more overhead.
- deleted 15y ago[deleted]
- obtu 15y agoA single pseudorandom byte chosen at container initialisation would work here, because url hashes are ephemeral. Persistent structures on the other hand are already DOS-prone, but need attacks more tailored to the application.
- mikeash 15y agoEven with a random per-initialization byte, you could still brute force it. Pick a random byte on your side, generate colliding keys with it, and send the request. If it doesn't work, just try again until it does. You'd expect to only have to try this ~256 times before succeeding, still seems pretty practical. Of course, bump this up to 2-4 bytes and it no longer is.
- oconnore 15y ago256 attempts is the upper bound. The expected value of attempts should be 128.
- Groxx 15y ago
- stock_toaster 15y agoNote that it would also likely work on something accepting json, not just post params.
- draegtun 15y ago> which implies this has been known since 2003 in Perl Known and also fixed because since then Perl has been using a random hash function. ref: http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-... (http://news.ycombinator.com/item?id=3402187 http://news.ycombinator.com/item?id=3402187)
- Groxx 15y agoGood to know, thanks!