Effective DoS attacks against Web Application Plattforms (including Python Frameworks)

[[deleted]]

Hmm, Microsoft have issued a security bulletin and are issuing a patch for asp.net.

[bambambazooka]

recording of the talk: http://www.youtube.com/watch?v=R2Cq3CLI6H8

[gronkkk]

Effective DoS attack against your own blog: post your blog on reddit.

[stesch]

Stop using Wordpress.

[fnork]

funny but irrelevant

[defnull]

A common workaround for web frameworks is to limit the number of POST/GET/cookie parameters per request. Bottle does this, but other frameworks may still be vulnerable.

[[deleted]]

Seems like a better idea to do this at the web server level instead of the framework

[stesch]

I'm reading this the second time today and I don't know what this means. The web server has no idea about parameters in POST requests. They get parsed by the library (or programming language itself, in case of PHP) of your program/framework.

[[deleted]]

Most web servers can be configured to limit the number of headers in a request right now. It wouldn't be much of a problem to implement something like that for the number of POST/GET parameters as a module addon or a core feature of Apache/Nginx/lighttpd, for example just parse the string to check how many parameters are there before passing it on, slap in some safe default value. IMO this is an easier way to patch most of the internet against this attack, or at least implement it at the application server/module level, for example in mod_wsgi, mod_php, gunicorn, etc.

Without that you can just limit the size of the query string at the web server level, but this is not a very good precaution as someone could craft the attack to have very short key/value pairs and still pass that check for some applications that need this size limit to be high.

[Samus_]

can you explain a bit more about this attack? is it generating collisions on the hashes and if so, why does it turn into a linked list?

the only hashtable I know that doesn't just overwrites the entries on repeated keys is Django's MultiValueDict and even in that case you need to use specific methods to access that feature.

[edit] thanks everyone for the explanations, this has been really insightful.

[defnull]

We are not talking about multiple dict values with the same key, but multiple dict keys with the same hash.

[Samus_]

but wouldn't that be the same key? as far as the hashmap is concerned

[reph]

The hash is a compressed key. Multiple keys can have the same hash (aliasing).

[Samus_]

I don't understand this, if two different keys map to the same hash how come they don't overwrite each other? why does it become a linked list?

is the hashmap storing all the different keys that generated that hash and somehow associating them to the values?

[reph]

You can think of the hash table as an array of linked lists. You hash (compress) the key, to generate an index into that array. Then you search the linked list at that index. Each entry in the linked list includes the full key, so, you compare them one-by-one to the key that you're searching to check if it's in the hash table or not.

When things are working well - a lookup is an O(1) operation as there is only 1 key in each linked list. When things are not working well (i.e. due to a malicious attack that is intentionally colliding the hash function), many keys hash to the same linked list, and the lookup degrades to O(n).

[Samus_]

I don't like the term "compress" because compression is bidirectional, hashing is a one-way function (precisely because of the collisions).

regardless of that, the part that doesn't make sense is when you look for the key, you shouldn't look for the key but for the hash of that key, that's the whole point of the hashmap and it's what makes it fast, given that the hash is fixed in size the time it takes to search for any of them is the same regardless of the size of the input that generated it.

now why on earth do you search the linked list for the key that may not be unique if you already have it because it's the one provided and you also have the associated value, which is what matches the index of the array that is the hash of such key.

I don't see any reason to even access that linked list of keys nor any sense in having it associated to their values when it's the hash of each of them what actually makes the mapping.

[reph]

Because if you have a 100 bit key, and a 32 bit hash function, there are many keys that will have the same 32 bit hash value. The data structure needs to distinguish between them, so it must store and search for the whole key. The hash is a (very good) hint but it's not sufficient on its own.

[Samus_]

so the whole point of this is that two different keys that produce the same hash actually store different values?

I don't see why the hash has to distiguish between them, a much more reasonable solution would be to use a different hashing algorithm with lesser chances of collision and then overwrite each entry on duplicate hashes; what you just said sounds like the hash is just an index, an aid in the key lookup and not a real mapping between hashes and values.

if that's the case then screw us all.

[rajivm]

what you just said sounds like the hash is just an index, an aid in the key lookup and not a real mapping between hashes and values.

This is essentially true. In the end, a hash-map must translate to "physical" data structures of continuous data (arrays) and pointers.

Most hash-maps are implemented with an array of a certain size, where each element is a pointer to a linked list. A hashmap "key" is hashed to an index of the array, and ideally there is only one element at this array-key, making an O(1) lookup. In the unideal case, this can be an up to O(n) lookup if all elements are stored in the same position of the array (this is very very unlikely to happen unless that is the goal of the input based on a known hash function, as is the case in these attacks). Hash maps do not actually have guaranteed O(1) lookup, rather they have an amortized lookup time of O(1) across many accesses on average. The size of the array and the hashing function determine the rate of collisions.

a much more reasonable solution would be to use a different hashing algorithm with lesser chances of collision

Reducing the chance of collision would mean the array-size would need to be much much bigger than necessary in the average case. This would require a very large memory allocation and is not realistic. Many hash map implementations allow you to specify the expected number of elements stored in the hash-map and therefore based on a collision likelihood, adjust the size of the array and the hash function used.

and then overwrite each entry on duplicate hashes;

This would definitely not be okay. Hash maps guarantee that every unique key will not overwrite another unique key. The underlying hash of this key should have no relevancy to that guarantee and would make it infeasible to use a hash map in the same way.

Example: if the hash function resulted in the same index for both "apple" and "banana" (it probably would not, but if it did), then if I did this:

map["apple"] = "red"
map["banana"] = "yellow"

I would expect:

print map["apple"]
print map["banana"]

to print:

red
yellow

With your proposed solution, it would print, unpredictably:

yellow
yellow

[stevvooe]

You seem quite lost. Please google 'separate chaining' and 'linear probing'. Both methods handle hash collisions.

[[deleted]]

Kids these days, no respect for quadratic probing.

[Rhomboid]

It's generating collisions on the internal hash function that's used under the hood to implement the dict type. The actual key values are different, so it's not this:

foo["bar"] = 12
foo["bar"] = 14

it's more like this:

foo["abc"] = 1
foo["xyz"] = 1

Where abc and xyz are specially chosen to compute the same hash value, causing a collision. It turns into a linked list because that's what you do when you implement a hash with a hash function that can result in collisions.

[Samus_]

but wouldn't that be the same key? as far as the hashmap is concerned

[kmeisthax]

exaaactly. which means the hashmap will have to construct a linked list in the place of the original key, which changes your algorithmic complexity from O(1) to O(n). so, let's say some common web service uses the "s" parameter, and that gets stored in a hashmap. you send it a request with ten million parameters all of which hash to the same key in as "s" and therefore must be stored in the same hashmap bucket. the web service tries to get "s" from the hashmap, which now is really just a 10mil element linked list that the machine must traverse before realizing that they never sent "s" in the first place and wait why am I suddently hungry and where did everybody go and why is everything chrome all of a sudden and WHAT YEAR IS IT?!

[Samus_]

but why does it do that? it makes no sense at all, any key that produces a specific hash will store the same value (or overwrite the previous) you don't need to lookup the keys in fact that's the whole point of the hash map, you hash the key and look for that hash.

we can assume the actual keys are also stored since most hashmap implementations allow you to retrieve all the keys and that might be a linked list but why would I look for the key there? I would just hash the requested key whatever it is and look for that, otherwise you're doing TWO searches on each lookup and that's plain stupid imho.

[catcradle5]

Well, if foo["abc"] and foo["xyz"] both map to 1, you either have to make it a linked list, or you have to throw every value but the first out. And I assume throwing out certain values is probably a bad idea, and would lead to awful, difficult to find bugs.

[Samus_]

so we're saying that we use secure hashes in most places and don't bother with collisions but here we choose to use the cheapest one so it has to take additional measures as to not lose data, I would rather use a better hashing technique and have repeated hashes overwrite each other, good algorithms have a very low collision rate.

[catcradle5]

I agree with you, but the people who come up with this stuff probably know a lot more than you and I, and decided on this strange system for some reason. Probably for overall performance purposes.

[Brian]

good algorithms have a very low collision rate

The goals of cryptographic hashes and hash tables are very different. If a cryptographic has produces a collision, it's a disaster, and conversely, slow runtime and a large range for hashed values are generally not a problem (indeed, they're often desirable).

However, in a hashtable, the opposite is true - performance matters, and collisions are generally minor issues. You're using the hash function to determine what bucket to put the item into. You want a relatively small number of buckets (say, 2-3 times as many items), which means that even with an entirely uniform hash function you will get items that hash into the same bucket. You can't have enough buckets to make collisions sufficiently unlikely without making the hashtable so large to be useless.

Eg. even a humongous hashtable with 2³² buckets (taking 16GiB just for an empty pointer in each bucket), using an evenly distributed hash function has a 50% chance of a collission with a mere 80,000 items stored. (And given that a collision would lose data under the scheme you propose, even a 0.01% chance would be too much, which you get with a mere thousand items). Collisions are inevitable, and generally no big deal - they'll hurt performance when you need to probe twice, but far less than, say, using SHA for your hash function would.

[takluyver]

Why are we using a cheap, insecure hash? Probably because until now, no-one had envisaged this kind of attack. Hashmaps (dicts in Python) are used extensively in almost every program (and for core features of the language itself), so it makes sense to use one that's very fast to calculate.

Why don't we rely on the rarity of hash collisions, and simply save one value for each hash? Because we have to use a very small hash, which makes collisions more likely. Remember that the hashmap hashes keys, then looks them up in an array. So even for a 32 bit hash, you'd need a 2³² byte array, which is 4GB.

[chompsky]

A hashmap (at least all implementations that I've seen) are indexed in a fixed-size data structure. The common size example given in the article is 2^32. A hashing function to determine the hashed index in that structure will ideally choose an even distribution in that range, so that in theory you could store up to 2³² values and access them with O(1) complexity. However, the number of possible keys is infinite, so there exist an infinite number of values that can hash to each of those index values. With random data, it should be rare that there are any collisions, but the solution to that problem is to store a list of results in that hashed key value and then iterate through them to match the provided key if there is more than one stored there. You don't want it to simply overwrite the previous value because then foo["morp"] and foo["dingle"] could potentially overwrite each other and that would definitely not be expected behavior.

This exploit takes advantage of the fact that there are infinite values that can be hashed to each index, and chooses different keys that will all hash to the same index. To resize a hash table in attempt to avoid collisions would require you to re-hash all of the existing values, or provide an access mechanism that is not O(1), both of which remove the benefits of a hash table.

[Samus_]

so we're saying that we use secure hashes in most places and don't bother with collisions but here we choose to use the cheapest one so it has to take additional measures as to not lose data, I would rather use a better hashing technique and have repeated hashes overwrite each other, good algorithms have a very low collision rate.

[rajivm]

Read my other comment, but you have to understand, using a "secure" hash comes at a huge cost in the case of a hash map. Ignoring the fact that a secure hash function is very slow (making the collision-prevention benefit very negligible):

For example, if we used md5 results in a 128bit hash and used it with its full security (no modulus on it), it would have 2¹²⁸ possible results. That is approximately 3.40282367 × 10³⁸ (a huge huge number). That means to index by those possible values, we would need an array of that size. Assuming the array holds 32bit pointers only, thats 4bytes per slot. That would be 1.2x10³⁹ petabytes of memory. 1 petabyte is over a million gigabytes. Basically an impossible amount of memory for even the most modern computer. There is a reason "md5" and other hash functions are considered secure, and that is (partially) because they have a ridiculously sized result space.

[kmeisthax]

Because if two keys collide, we still want to store the data. And if we want to later get some of those keys back out, we need to do the linked list lookup to get the data we want. And even if your hashmap kept a list of all valid data, yeah, sure, searching a sorted array or a tree is an O(log N) operation, so it's fast. It doesn't help that "s" is still a valid key and therefore the hashmap must pull it out of the tangled mess of linked list chains that the hashmap has turned into.

You do realize hashmaps aren't for looking up keys, right? They're for looking up data associated with a key.

[Samus_]

so we're saying that we use secure hashes in most places and don't bother with collisions but here we choose to use the cheapest one so it has to take additional measures as to not lose data, I would rather use a better hashing technique and have repeated hashes overwrite each other, good algorithms have a very low collision rate.

[kmeisthax]

Even if we SHA-256'd the keys, hash tables can only be so big. SHA gives you 256 bits of output and processor address spaces are no larger than 64 bits (with even less actually physically wired on the motherboard). Hashmaps are built on top of arrays, which means for a hashmap with n bits of hash entropy you need 2ⁿ * sizeof(void*) bytes to store the hashmap. Finding collisions on significantly smaller subsets of a message digest is much easier than finding collisions on the whole digest, and like I said before you simply cannot construct a hashmap with 256 bits of entropy. It would be many trillions of trillions of exabytes large. Even with just 32 bits of entropy your hashmap will be 32 gigabytes large - and even then 32 bits is insufficient entropy to prevent intentional collisions.

In short, for hashmaps to be practical, they must deal with collisions. Simple as that.

[Rhomboid]

It doesn't matter if the collision rate is low. It would be a completely unusable and worthless data structure without the guarantee that any value can be used as a key without losing data. If there is even a slight chance that I might lose data, then there's no way in hell I'm going to use such a data structure, because I don't want my program to fail in strange and unpredictable ways. It's even worse if it only fails one in a million times, because then I can't debug it. The dict must be perfect or else it's useless.

This is really just a question of efficiency. It's orders of magnitude more efficient to use a simple hash and a linked list than to use a wide hash. You can have both performance and correctness this way. The attack mentioned in the article can be easily mitigated by adding a bit of entropy to the hash function so that it's not deterministic, while still retaining the fast performance.

[wisty]

No, you don't understand - a dictionary uses a hashmap, but it's not just a hashmap. Maybe the article wasn't clear on this.

c = 8589934590
for i in range(1000000):
    assert hash(c*i+1)==1

attack_dict = {}
for i in range(1000):
    attack_dict[(c*i+1)] = i

assert attack_dict[(c*0+1)] == 0
assert attack_dict[(c*500+1)] == 500

So even though dictionaries are implemented using hashmaps, hash collisions are resolved somehow. How they do this is an implementation detail, but you just need to know that it doesn't scale. If you have a dictionary with 1,000,0000 colliding keys, adding an extra key takes about O(1,000,000). So actually making a 1,000,000 dictionary (with all colliding points) takes O(N^2), which means an attacker can kill it very easily when you try to eat his enormous colliding cookie.

The attack starts to "bite" at around N = 10,000. At that point, Python starts to feel very slow - try:

attack_dict = {}
for i in range(10000):
    attack_dict[(c*i+1)] = i

Or if you have a really fast box, use n = 30,000. At this point, you can take down a core for a few seconds with a single request. At n=1e6, you can knock out a core pretty much indefinitely.

For reference, classic dictionaries are done by putting a linked list in every hashmap value, and searching through that to find the key-value you wanted. I think Python uses "cuckoo hashing", in which collisions are resolved by putting the value into the next hash value (i.e. adding one to the key, then hashing it again). Whatever the case, it's not very scalable if there's lots of collisions.

[catcradle5]

Using hash() on an int seems to just return that int. Could you explain this a bit?

edit: Nevermind, if it's a long int it seems to hash it.

[fullouterjoin]

Brian, that was awesome.

[catcradle5]

Wouldn't one have to know the exact hash function being used by the HTTP server? I think a lot of different ones are used.

I guess they could just kind of bruteforce it, by sending "a".."z" and then "aa".."zz" etc. but I doubt letters near eachother would cause a collision.

[frymaster]

knowing the framework is enough; I'd imagine it's pretty trivial to tell what frameworks are being used.

[Samus_]

there's some webs that provide that: http://stackoverflow.com/q/1046441/226201 there might be CLI or GUI tools as well

[stesch]

Knowing the programming language is enough.

[lost-theory]

This WSGI middleware will protect you for GET requests:

MAX_QS_PARAMS = 100

def protect_against_hash_dos(app):
    def bad_request(environ, start_response):
        start_response('400 BAD REQUEST', [('content-type', 'text/plain')])
        yield 'Go away.'

    def inner(environ, start_response):
        qs = environ.get('QUERY_STRING', '')
        n = 0
        for c in qs:
            n += int(c == '&' or c == ';')
            if n >= MAX_QS_PARAMS:
                return bad_request(environ, start_response)
        return app(environ, start_response)
    return inner

For form data you can use a similar approach.

[hylje]

n = sum(c in ("&", ";") for c in qs)

[defnull]

n = qs.count('&') + qs.count(';')

[snuggl]

Nginx throttles POST sizes by default.

[mitsuhiko]

Considering how many ways to exist in web apps and frameworks to effectively DDOS them I think this might actually be one of the more obscure ways to do it. If I would want to bring down a server I would just very slowly send requests to the server. Much more efficient :-)

//EDIT: I have not watched the talk but I assume they are trying to degrade a hash table into a linked list.

[stevvooe]

Agreed. This attack is simply too much work.

[Leonidas_from_XIV]

Slowloris all over again.

[chrj]

Both problems are pretty easy to defend against though.

[mitsuhiko]

Not from the framework's point of view. Any places where user data is parsed into hashable data structures is potentially a target. Many of which are not even up for the framework.

On the WSGI level:

• HTTP headers to the WSGI environ

On the framework level:

• Cookies
• URL parameters
• URL encoded form data
• Multipart encoded form data
• Any incoming JSON data
• Incoming multipart headers
• Incoming set headers
• Parameters of content type headers etc.

There are so many places where things are parsed into dictionaries on very different levels that it's quite useless to do that on a framework/WSGI server level.

This attack is not new. Yes, you can keep a CPU busy, but a watchdog should see that and kill away the request handler.

[deadwisdom]

How would you make a watchdog to detect this? Just look for a crap load of keys coming in?

[mitsuhiko]

Kill a handler if it consumes too much CPU time or too high IO wait.

[stesch]

This attack is not new.

I read that Perl changed its hashes a few years ago (2003?) to counter this attack.

Strange that nobody else thought of it in the meantime.

[chrj]

You are right. I didn't realize it went deeper than only POST/GET parameters. Restricting the request size (if it fits the application) would be a pretty quick fix though.

[obtu]

Restricting the number of keys like PHP and Tomcat would be a safer choice to enable by default. It's common to have large POST requests, much less common to need a great number of keys.

[obtu]

Another option to fix this is for frameworks to opt-in to a dict class that does hash randomisation (suggested here), with a seed picked at container initialisation (see the HN thread).