So, would your holiness care to change her password?
January 1, 2012 6:26 PM   Subscribe

 
Effective Denial of Service attacks against web application platforms is terrifying for every webmaster/developer.
posted by Foci for Analysis at 6:50 PM on January 1, 2012 [1 favorite]


It's not going to get any better until magic bullet takes hold and makes this type of thing obsolete.
posted by MikeWarot at 6:53 PM on January 1, 2012 [1 favorite]


Wow, that algorithmic complexity attack is sheer beauty!

Anonymous must be probing payment APIs that beat them last year as we speak.. all that "we do not forget" jazz.
posted by jeffburdges at 8:10 PM on January 1, 2012


Wow, that algorithmic complexity attack is sheer beauty!

Yeah, sheer beauty that had me immediately firing off an email to the security team at my job.

I kind of want to see a full listing of bugs/vulnerabilities caused by people writing hash functions that shouldn't have been writing hash functions.
posted by spitefulcrow at 8:45 PM on January 1, 2012 [1 favorite]


Isn't that algorithmic complexity attack the same one that Perl added a workaround for in 2003 or so? I guess I'll know more once I watch the video of the presentation.

people writing hash functions that shouldn't have been writing hash functions

The hash function can be as good as you like; the complexity attack exploits a fundamental property of hash tables. If you want reliably decent worst-case behavior you should probably be using a balanced tree structure of some sort, not (or as backup for) a hash table.

(Not to say that there aren't a lot of truly awful string hashes being used all over the place by people/companies who really ought to know better.)

until magic bullet takes hold

From what I see, of the three linked presentations, capability-based systems would mitigate at most one of the problems.
posted by hattifattener at 9:37 PM on January 1, 2012


The hash function can be as good as you like; the complexity attack exploits a fundamental property of hash tables. If you want reliably decent worst-case behavior you should probably be using a balanced tree structure of some sort, not (or as backup for) a hash table.

No, the complexity attack exploits that fundamental property of hash tables in conjunction with a flaw in the hash functions used by all of the languages/runtimes mentioned. Specifically, finding hash collisions in these languages is 1) easy to do and 2) precomputable once for any and all instances of applications on these runtimes, because the hash functions employed are deterministic and invariant across executions of the runtime.

If you read the note in perl581delta (which you linked), they explicitly state that they changed the hashing algorithm to add a random seed generated on startup.

The fundamental property of hash tables is useless without a cheap way to generate data that will trigger it. Randomizing a piece of the hash function at startup means precomputation is rendered useless and a would-be attacker will spend lots of effort brute-forcing his way to an attack string that will only work on one specific process.
posted by spitefulcrow at 9:53 PM on January 1, 2012 [1 favorite]


Capability based security allows for strong firewalling of applications from each other and the operating system. The problems with privilege escalation get stopped, which makes any other exploits much less useful.

The believe seems to be that we can fix all the holes, and obtain security, if anything the recent presentations show that this is foolish, at best. A different strategy is required, and I submit that capability based security is a good path to pursue.
posted by MikeWarot at 10:12 PM on January 1, 2012


Yes, MikeWarot, but how would capability-based security help here? In one case you have firmware updates on an embedded device, in another case you have an algorithmic complexity attack. Even if they would have totally prevented the prison PLC exploit, a 1/3 success rate is awfully poor for a "magic bullet".
posted by hattifattener at 10:32 PM on January 1, 2012


From the DoS talk:

"Thank You!

- Perl for fixing this in 2003"
posted by benzenedream at 11:22 PM on January 1, 2012


The holiday season isn't always relaxing for those in the computing security field.

Maybe the computer security field needs to hire more people who believe that forewarned is forearmed.
posted by Kid Charlemagne at 12:29 AM on January 2, 2012


Don't forget this talk:

The Science of Insecurity

Which applies actual science to computer security problems and, unsurprisingly, comes up with some answers about how to prevent a lot of the problems that have been bugging us all for the past few decades.
posted by Djinh at 1:34 AM on January 2, 2012 [1 favorite]


This is not a thread about capability-based security. Don't turn it into one.
posted by scalefree at 3:51 AM on January 2, 2012 [4 favorites]


Jesus. Roll on PHP 5.4.0.
posted by grubby at 5:51 AM on January 2, 2012


I mean, terrifying as the hashtable is, I don't think anyone cares enough about my site to use this attack. For me the risk of updating to a RC PHP outweighs the risk of having this happen to me. I understand that the PHP workaround is not perfect even in 5.4.0 and they need to randomize their hash tables like Perl, too. Randomization makes the whole attack too expensive. PHP's limiting input vars makes it more expensive, but probably still worthwhile for sites that someone really wants to take down.
posted by grubby at 5:56 AM on January 2, 2012


Um. For those of us who worked through the hash table slides, but find our mind vexed at anything more complicated than tying our shoes, can someone provide a kindergarten-level summary of what was found and how, say, a site running wordpress on an apache box on a shared host might fear from it?
posted by maxwelton at 7:29 AM on January 2, 2012


Um. For those of us who worked through the hash table slides, but find our mind vexed at anything more complicated than tying our shoes, can someone provide a kindergarten-level summary of what was found and how, say, a site running wordpress on an apache box on a shared host might fear from it?

When you send stuff to a server, it gets placed in different buckets. Usually you don't have much stuff that's going in these buckets, and in the worst case, you can just find some more buckets if the ones you have get too heavy.

What these guys figured out is how to make it so everything they send to the server gets placed in a single bucket, no matter how many buckets the server has. And when the bucket overflows*, everything goes slow as molasses, effectively eating all the server's resources.

*The buckets can't really overflow since they're practically infinite, but the more stuff you put into a bucket, the slower the system goes.
posted by ymgve at 7:57 AM on January 2, 2012 [1 favorite]


a site running wordpress on an apache box

The question is whether Wordpress ever stores anonymous user data in the keys of an associative array (which is implemented with a hash table). It's likely that it does.
posted by phrontist at 8:48 AM on January 2, 2012


The issue is that PHP does by default. http://foo.com/index.php?bar=baz&biz=boo&anonuser=data

This is true for nearly every PHP application, regardless of which application PHP is serving. The issue is even processing to see if we can discard these values already has them stored, and thus the attack has already taken place.
posted by yeahwhatever at 9:52 AM on January 2, 2012


Ah, got it. (Well, I'll nod like I seem I've got it, but you guys can still keep your well-founded doubts.)
posted by maxwelton at 10:18 AM on January 2, 2012


The issue is that PHP does by default. http://foo.com/index.php?bar=baz&biz=boo&anonuser=data

This is true for nearly every PHP application, regardless of which application PHP is serving. The issue is even processing to see if we can discard these values already has them stored, and thus the attack has already taken place.


PHP and nearly every other web-application framework in existence. All of them have to parse an incoming HTTP request and transform it into a data structure usable by the application logic, and pretty much all of them do it by stuffing key/value pairs into a dictionary object which is backed by a hash table in the language runtime. Perl is safe for having fixed this eight years ago, but Python, Java, Ruby, and PHP (read: the runtimes behind probably 80% of web applications) are all vulnerable.
posted by spitefulcrow at 10:21 AM on January 2, 2012 [1 favorite]


The issue is that PHP does by default. http://foo.com/index.php?bar=baz&biz=boo&anonuser=data

This is true for nearly every PHP application, regardless of which application PHP is serving. The issue is even processing to see if we can discard these values already has them stored, and thus the attack has already taken place.

PHP and nearly every other web-application framework in existence.
Yup. Today when I read this I had a heart attack and started furiously reading through the source code of the Python web framework that I use, Tornado. It took me about a minute to figure out that httpserver.py line 390 implies that Tornado will also put all arguments from an HTTP request into a dictionary, via the urlparse module.

My first thought was to implement some of the cheap workarounds that the researchers have suggested; counting the number of arguments and capping them at 1000, limiting the size of POSTs, limiting the execution time per request. However, as the researches themselves conclude, there are so many places where every single web framework stores incoming data into hash tables that the only real solution is to implemented randomised hashing within the language's hash table implementation. This is exactly the approach that PHP and Ruby took, and the author's actively credit Ruby's developers with being extremely helpful and responsive.

However, this is much easier said than done. There's a very vigorous and lively discussion going on between the Python maintainers, including Guido Van Rossum, about whether randomised hashing will negatively affect the traditional stability of Python dictionaries. I hope they figure it out soon because honestly this issue is giving me chills.

posted by asymptotic at 10:47 AM on January 2, 2012


Dear God and now I'm not closing my HTML tags. Been a bad day.
posted by asymptotic at 10:49 AM on January 2, 2012


Yes, MikeWarot, but how would capability-based security help here? In one case you have firmware updates on an embedded device, in another case you have an algorithmic complexity attack. Even if they would have totally prevented the prison PLC exploit, a 1/3 success rate is awfully poor for a "magic bullet".
By the "algorithmic complexity attack", I assume you mean the denial of service attack against web servers by confusing their parsers. If each process has limited capabilities, one of those is the number of cpu cycles it can consume in total, and/or per unit time. This can mitigate these types of attacks, but not solve them.

As for firmware that blows up printers, segregating the firmware update code from the code that does day to day printing would be a good start. You can't fix stupid.

Data diodes are a wonderful way to isolate critical systems from those that need their output for reporting, etc.

There are lots of things that can be done here, looking outside the traditional approaches is a good investment of time and energy.
posted by MikeWarot at 10:54 AM on January 2, 2012


However, this is much easier said than done. There's a very vigorous and lively discussion going on between the Python maintainers, including Guido Van Rossum, about whether randomised hashing will negatively affect the traditional stability of Python dictionaries.

Oh for fuck's sake.

Anyone who relies on a dict's key ordering is an idiot who should have rolled their own data structure for whatever ass-backwards thing they were trying to do in the first place.

At least the BFDL has come down on the right side of this one, which means that it will (eventually) get implemented in CPython.
posted by spitefulcrow at 11:09 AM on January 2, 2012 [1 favorite]


At least the BFDL has come down on the right side of this one, which means that it will (eventually) get implemented in CPython.
spitefulcrow, what about using a tree-based data structure for all unsanitised user inputs, i.e. HTTP headers, HTTP query arguments, structured data within HTTP POSTS (i.e. JSON)? I'm not a big fan of the hand-wavy argument "Frameworks are too spaghetti like, we can't figure out where all the hash tables are used!", and I see the appeal, at least in Python, of using a tree-like data structure that looks like a dictionary.

But I have no sympathy for people who rely on the stability of dictionaries, they need to RTFM.
posted by asymptotic at 11:31 AM on January 2, 2012


...and before we start talking about algorithmic complexity, surely O(log n) for n < 1000 is equivalent to O(1)?
posted by asymptotic at 11:43 AM on January 2, 2012


A tree-backed map is probably a decent solution here. Red-black trees (or other B-treeā€“like structures) guarantee O(log n) worst-case performance (the key situation here), which is plenty fast for sane inputs. In combination with aborting requests with more than 1000 parameters, should be just fine.
posted by spitefulcrow at 12:01 PM on January 2, 2012


I love arguments for leaving broken things the way they are, based on the rest of the world conforming to some arbitrary and unrealistic standard of competence.
posted by benzenedream at 5:11 PM on January 2, 2012


Insurance Against Cyber Attacks Expected to Boom

Isn't that just inviting cyber attacks even more? "We'll spend millions fighting our insurance company if you hack us!" lol
posted by jeffburdges at 7:15 PM on January 2, 2012




There are 28C3 videos on youtube and elsewhere. Did we link the weblog or wiki yet?
posted by jeffburdges at 12:26 PM on January 3, 2012


There is an awesome 28C3 talk on Tor by Roger Dingledine and Jacob Appelbaum.

"Everybody that I've taught anything other than Tor to is in jail."
posted by jeffburdges at 4:20 PM on January 8, 2012


« Older A very confused Bob Hope   |   Sort of like Pandora for YouTube Newer »


This thread has been archived and is closed to new comments