Slashdot Mirror
Denial of Service via Algorithmic Complexity
dss902 writes "We (Department of Computer Science, Rice University) present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures... Using bandwidth less than a typical dialup modem, we can bring a dedicated Bro server to its knees; after six minutes of carefully chosen packets, our Bro server was dropping as much as 71% of its traffic and consuming all of its CPU. We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks."
I agree that DoS attacks are really lame, but at least this is fairly complex and has some interesting technological implications. Most DoS attacks are just floods of packets, and can't really be defended against. This attack can be prevented, and maybe will help improve security in other ways. I'd rather see 10 people who can pull off a preventable algorithmic complexity attack than 10,000 who just packet a server to death. People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
If you RTFA you'd see they also present ways in which to AVOID this problem, and that's the real goal.
well, maybe they're figuring out how to fix them. Would you rather a University figuring out how to do it, or some random black hat/chinese hacker?
With this information it shouldn't be too big of a deal to redesign the software to not be vulnerable anymore.
What they did is little more than algorithm analysis. They looked at all the different links in the chain then merely decided which algorithms were the weakest links and exploited them.
This is good because we can now fix those. Robustness abound.
That is something that the paper said, but they also gave specific examples of software that was vulnerable to that kind of attack. They determined that the Bro intrusion detection was highly vulnerable to this kind of attack, and mentioned different versions of Perl and Python that also experienced a significant perfrormance decrease given their input specifically made to bring down systems that use hash tables.
I don't know if anyone has *published* this before, but it's certainly not new.
It has been done. They mentioned similar related work where it was found that input to quicksort makes it take O(n^2) time instead of O(n lg n) and a that there was a vulnerability in the hash tables of the Linux route-table cache. The concept isn't new, it's just that different software has been found to have this sort of vulnerability.
And I just couldn't help but laugh at the irony of their PDF file on DOS attack prevention being the victim of the /. effect.