Meet the New DOS, Same as the Old DOS
(For those who don't get the title, listen the last few seconds of this).
Recently, Microsoft released an emergency out of cycle patch. The patch addresses a low-bandwidth DDoS attack where an attacker can cause anASP.NET server handle HTTP requests in a very inefficient manner. While the server processes the attacker’s requests, it cannot respond to other users’ requests- in effect, denying the service from legit users.
Why the urgency? The vulnerability stems from implementation flaw in the application server code. It is not specific to a particular application and cannot be mitigated through better coding of the application code. Any application built on top of the vulnerable application server (ASP.NET, Java, PHP) is exposed.
How does this attack work? Applications commonly store HTTP request parameters in a data structure called “hash tables”. These are very common structures as they work, on average, quickly. And that’s the point: on average. If a hacker creates an HTTP request in a particular manner, using many parameters, the “hash table” begins to run in its worst case scenario – which is actually very slow. If hackers slow the server down too much, they can effectively cause a DoS.
Is this a new attack? It depends on how you look at it. This class of attacks, which exploits the worst case scenario of an algorithm, or a data structure, are called “Algorithmic Complexity Attacks”. As the following list shows, we’ve seen them before. However, as you can see, all these attacks were demonstrated against lower level devices – such as routers or firewall – and not against Web applications:
- The notion of a low-bandwidth attack exploiting an algorithm’s worst case can be traced back to an attack using nested HTML tables. In 1996, Garfinkel showed how some browsers’ algorithms perform super-linear work to determine the layout of the table. Thus, a maliciously crafted web page can cause the browser to freeze
- In 2001, Dean and Stubblefield proposed a solution to an attack against an SSL server that may lead to the paralysis of e-commerce websites. In their scenario, the attacker requests the server to engage in expensive RSA decryptions without first having done any work.
- Another example includes the attack presented in 2004 by Gal A., Probst C and Franz M. In their work, the attacker takes advantage of the fact that the Java bytecode verification scales quadratically with the size of the program and so keeps the verifier busy in order to constitute a denial of service. The authors develop this notion in order to construct complexity attacks against mobile-code systems.
- In 2003, Crosby and Wallach introduced this family of low-bandwidth denial of service attacks called algorithmic complexity attacks. These attacks exploit algorithms’ worst-case behaviors. Using their method the adversary can create specific inputs that all fall into the same hash bucket, causing the hash table to degenerate into a simple linked list. They successfully carried out their attacks on different applications, such as the IDS, Bro (Paxson, 1999) and several Perl versions. They showed how within 6 minutes they were able to cause the server to consume all of its CPU as well as to drop most of its received packets.
Why should I care that this attack basically “moved up the stack”? This attack is not about using a bunch of bots in order to flood the network. It’s not about causing the network-layer devices – such as routers – to slow down. It’s not even about bringing down network-layer defenses, such as firewalls. It’s all about sending one single Web request specifically crafted – and legit. In fact, the HTTP RFC never put a restriction on the number of parameters so application developers would not necessarily see the request as abnormal. This attack sets to remind us once again how DDoS is moving up the stack.
What can be done to mitigate this threat? The initial recommended solution is to block any HTTP request which has a large number of POST parameters. The suggested threshold is currently set to 1000. Web application firewalls, for instance, can apply such a policy quickly to thwart any attacks before the underlying languages will be patched.
As for the language developers, the researchers who disclosed this attack suggest randomizing hash functions. This type of randomization should also be considered carefully. In 2006, Prof. Avishai Wool and Noa Bar-Yosef showed how under different scenarios and parameters, randomization does not necessarily solve Algorithmic Complexity Attacks. You can read the paper here.
