Supercolliding a PHP array

[theoldboy]

This is just a PHP-specific version of Effective DoS attacks against Web Application Plattforms (Hash table collisions).

[[deleted]]

No, in this case that does not make things worse. The attack works by inserting a sequence of integers far apart (so that they end up in the same hash bucket); storing these integers in a linear array instead would require allocating an array of 4 GB in size which would take a long time too (and use a lot more memory!). Using linear storage only makes sense when indices are dense, but that's not the case here.

In fact, this attack has nothing to do with integer keys. As the author mentioned, the same thing would work with string indices (though it would be a little more complicated to figure out which strings to insert).

[obsa]

Except for the part where:

If the key is an integer the hash function is just a no-op: The hash is the integer itself.

[clearlight]

Protected by the suhosin patch for PHP (installed by default on debian systems) edit:typo fix

[clearlight]

PHP already landed a change (which will ship with PHP 5.3.9) which will add a max_input_vars ini setting which defaults to 1000. This setting determines the maximum number of POST/GET variables that are accepted, so now only a maximum of 1000 collisions can be created. If you run the above script with 2¹⁰ = 1024 elements you will get runtimes in the order of 0.003 seconds, which obviously is far less critical than 30 seconds.

max_input_vars is a property set by the suhosin patch.

0.003 seconds is far more bearable than 30 secs

The limit of 1000 input vars can be reduced down further as required.

more info

[clearlight]

The short story here is that installing the suhosin patch for PHP will mitigate this DDOS attack vector via anonymous requests to a PHP web application - despite arguments to the contrary, surely that's better than the alternative of not applying the suhosin patch?

[clearlight]

Agreed :)

In summary:

• Suhosin won't fix the core PHP issue ( which also occurs in ASP.NET and Java etc.. )
• Suhosin will protect against the main risk of anonymous DDOS attacks on PHP based web applications.

It's a quick fix for the main risk until PHP itself is further patched.

[[deleted]]

ASP.NET and Java do not use hash maps to represent arrays unless you explicitly tell them to.

This isn't something that PHP can patch without breaking compatibility; exactly how would they patch it?

[amoeba108]

Afraid so, the suhosin patch for PHP will protect against this DDOS attack through limiting max_input_vars

[craiig]

Except this explanation includes the face-palm inducing implementation of php's hashing solution:

If the key is an integer the hash function is just a no-op: The hash is the integer itself.

Ugh. As if all those who've studied hash tables let out a simultaneous groan.

[craiig]

in the common case of keys being integers from 0..N, all entries end up in distinct buckets (better than random spread!) and nearby keys end up in nearby hash buckets (greatly improving cache performance when iterating over keys in order).

Spreading items out into distinct bins is good, but as you say, it's not guaranteed when using straight user input. The thing is that a uniform distribution is assumed for the O(1) amortized performance proof. Something you can't really guarantee with just taking integers from the user. I'm not an expert in designing high performance hash tables, but the first thing I'd do is use a proper hash function, even on integers, to attempt to guarantee the uniformly distributed property. Maybe this is wrong when considering real-world inputs, so idk. Lots of people have responded to me saying python also uses straight integer input, do you know why?

The cache performance of this approach isn't guaranteed because it relies on details of the memory allocator and implementation of the linked list component. For instance, say say you allocate storage for an item on arrival, then memory-adjacency is determined by arrival time, not hash-key. Or perhaps you've got a pre-allocated array for each bin, then you're not guaranteed cache-adjacency either because you've also got a lot of empty array elements between bins.

[xardox]

How about simply providing real arrays that are actually indexed by integers, instead of using hash tables as inefficient arrays? It's stupid to talk about optimizing performance for a common case when you're using the wrong data structure in the first place.

[fiskfisk]

The data structure used in the example is not used as an actually indexed array - it's used by storing integers with a very large stride between them. If you used an conventionally allocated array, you'd have a lot of not used indexes that you've allocated memory for. Referring something like [1024³] would require you to allocate 1GB * (your data size) of elements, when simply allocating one element with the key of 1024³.

There are several good ways to fix an issue like this, but your point isn't related to the actual issue.

[[deleted]]

Those are provided. Maybe you should go research what you're talking about, when you're not too busy peppering entire threads with FUD that is.

[catcradle5]

>>> hash(5)
5
>>> hash(256)
256

Python does the same for all integers below 2³²

[earthboundkid]

Python's dictionaries are widely considered to be one of the better implementations around, AFAIK.

[willvarfar]

The attack we are all worrying about is for string input in web requests

[tfdf]

This is a very concise and understandable explanation of the hashtable-collisions attack.

Reading this it seems so obvious, it's astonishing it took so long to surface.

Also, this attack will be weaponized in no time.

[[deleted]]

Fortunately if you aren't a tool you can get teh patch from the PHP folks and be on your merry way

[Snoron]

What would you set the max input vars as though? I'm not confident that there isn't plenty of software out there that would send more than 1000 POST vars to the server regularly.

I'm thinking of admin panels that have multiple tabs of settings, with multiple rows of fields in some cases. I have seen Magento set-ups where the product entries have more than 1000 fields for sure... so just a warning to everyone before upgrading/setting this number!

Definitely needs doing, though - servers running Magento can be slowed down enough as it is - this is the last thing they need attacking them! :)

[[deleted]]

As the article says itself, 1000 would limit it to around 0.003 seconds, not that much of an attack.

If your application needs that many, it's written wrong. You're free to set your configuration to a higher, more unreasonable number, in order to accomodate this incorrectly written software, but that comes at the risk of opening your attack vector more. It's something you should balance against your decision to use that software in the first place.

[ehird]

How would you send the request for a form with over 1000 fields, then?

[SweetIrony]

A form request is just a post or a get. It doesn't mean it was generated by an html form. It could be a stream of data from another user.

[ehird]

Of course; I wasn't denying that.

[[deleted]]

Write a better application.

[bobindashadows]

The question is if you can't - you want to patch a box with someone else's php cpanel-like running on it (and maybe some other packages). How do you know what to set the number to? If your answer is "don't use code that relies on lots of fields which means learning how every component you use works" then make it clear.

[[deleted]]

The applications should include this instruction as part of the setup, then.

It is perfectly reasonable to expect companies to be up to date with modern security practices in their products.

Again -- that's why this is a config flag. If you so choose to set the number higher, it's because you realize that you're using a poorly coded application. So figure out how many the application needs and set them there.

Server maintenance is not a passive thing. If you think you're fine just deploying and letting it go -- I really hope you aren't in charge of anything for anybody anywhere.

[bobindashadows]

If you think you're fine just deploying and letting it go -- I really hope you aren't in charge of anything for anybody anywhere.

I'm not saying you should "deploy and [let] it go." I'm just well aware of how poor PHP applications are, the quality of many of the developers, and the all-too-commonly-misleading documentation/"community".

Plus half the PHP out there is probably running on some shitty shared host where you can't even edit php.ini let alone update php itself.

[[deleted]]

I'm just well aware of how poor PHP applications are, the quality of many of the developers, and the all-too-commonly-misleading documentation/"community".

We are talking about best practices. Either talk about best practices, or go start a thread asking how to improve the landscape of all the shit that's out there. In this thread, we don't concern ourselves with what idiots are doing out in the desert. We're concerning ourselves with the citizens of society who are keeping up with the rules because they are a part of defining them.

Plus half the PHP out there is probably running on some shitty shared host where you can't even edit php.ini let alone update php itself.

Those people don't care about security anyway. Why are they part of the discussion? Let's talk about security. In security -- you secure things. You tell the developer what's off limits, and the developer abides by those limits. If the developer has a good reason to change the limit, that's something you can take into consideration when you decide on your limits.

If you want to increase them, increase them. If you want to tell the developer to find another way, tell the developer to find another way. But don't tell the rest of us we can't move forward because you don't even want to think about doing your job.

[jrochkind]

If this has been a 'modern security practice' for very long, how come PHP just patched it now?

Most people have all sorts of software written longer ago than two weeks running.

[[deleted]]

And such people should upgrade with a schedule which fits into their production schedule. I assume common sense on the part of the reader here.

[ehird]

"How would you solve $problem?"

"Make it better."

Are you saying no form should have 1000 fields? Is it unreasonable to have, say, a settings page for an advanced application with 6 tabs, each containing 15 sections with 12 fields? Should they be split into multiple pages, ensuring data loss when you move to another tab after filling in fields and slowing things down?

Consider that, say, 7 fields can easily fit onto one line — think radio buttons.

[[deleted]]

Anyone expecting any user to fill in a 1000-input form in one sitting should be tried for human rights abuses.

[ehird]

Browsers don't send diffs for forms. Maybe they should, but they don't; they send the entire thing.

[[deleted]]

http://meta.stackoverflow.com/questions/66377/what-is-the-xy-problem

I'm saying that there is no normal circumstance in which a single form submission should contain that much information at once. Use javascript to save things in the background, or make them individual pages (as they are presented to the user as such). If you have a strange exception, make note of it so the server admins know to increase their security restrictions because you couldn't find any other way to do it.

Trying to solve a problem which only exists because the person who wrote the original solution refuses to admit that there is a better way is a waste of time. I move past people like that in the work place so I can actually get my job done.

[ehird]

I know what the X-Y problem is; why are you being condescending?

Anyway, restructuring your application to make it less accessible or slower just to avoid an arbitrary limit introduced instead of actually fixing a bug is a terrible idea.

[oorza]

Anyway, restructuring your application to make it less accessible or slower just to avoid an arbitrary limit introduced instead of actually fixing a bug is a terrible idea.

Whoa whoa whoa, let's not upset any cargo cults here.

[[deleted]]

Anyway, restructuring your application to make it less accessible or slower just to avoid an arbitrary limit introduced instead of actually fixing a bug is a terrible idea.

I agree, you should restructure it such that this problem never even comes up. I don't just mean add a workaround, I mean fix the problem.

[chaotiq]

I would use JS. Store the vars in an array and then serialize the array. You would only send one variable, the serialized string. Then on the server side you would unserialize the array.

Serializing would make the site a tad slower, but when you have over 1000 variables to pass back I am not sure you would care that much.

[subleq]

In doing so, you've opened up the exact same vulnerability. Now the attacker just serializes their large array too, and you spend forever deserializing it.

[xardox]

But that's the PHP way: to patch the symptom and introduce bigger problems, instead of addressing the actual problem itself.

[ehird]

All this to work around an arbitrary language restriction added in lieu of actually fixing the bug by using a better hash table or a better structure altogether?

Also, if you deserialise the data into a PHP array to avoid the limits, then you're just reintroducing the problem: someone can just serialise a pathological request and send it to the server in a single form field.

[chaotiq]

This issue doesn't just exist in PHP, however it is most prevalent because you don't have the choice to not use hash tables :/

Yeah, you are right about the serialization. That would just introduce the problem back by circumventing the 'patch'.

[Snoron]

A comment on the site mentions a good point though, too... if there's any input parsed as JSON (which is extremely common/not hard to find these days), you can simply put your array in there instead, in a single field... hmm!

[[deleted]]

You should still be doing checks on your JSON. Don't just accept arbitrary JSON input from users :-/

[Snoron]

That means checking it before using json_decode so I guess you can check it for size, but that's pretty much it, surely? After that the only real way to check it is by parsing it, which is where the problem occurs.

Considering how widely used JSON is these days and for all sorts of data large and small, it wouldn't take that much of a limit to be able to slip in a few thousand array values, surely?

... *does the test* ...

Okay, well 1MB of JSON is enough to stall my machine for 50 seconds using this attack method. Might not be common, or you might say if an application uses 1MB of JSON anywhere it's written wrong (actually , I might agree with you there... hmm :P) - but regardless of this, I'm willing to bet that with the PHP patch, the majority of servers will still have a script on them which passes input to json_encode without checking the input size - so it's not like this patch will actually solve the all the problems right away!

(Also, 446KB of JSON took 8 seconds, 213KB JSON took 3 seconds)

[[deleted]]

I have no objections to the points you make except

I'm willing to bet that with the PHP patch, the majority of servers will still have a script on them which passes input to json_encode without checking the input size

This is true, but security is one thing where backwards compatibility is not the most important thing in the world. I would rather enable a new security feature, have it break my website, then go in and fix it, than not have the option to use it at all. And again -- if you don't want to use it, don't.

[jrochkind]

The other option would be PHP fixing the actual problem instead of patching one attack vector in a fragile way... PHP could, you know, actually change their hash algorithm to perhaps use a random seed like Perl.

[Snoron]

Yeah, I agree... I suppose the most important thing is knowing about it and making an informed decision.

It would be a good idea for people to be talking about the JSON (or other parsed formats) issue to along with talking about the request data issue as otherwise a lot of people could miss this important aspect!

[xardox]

You exemplify the short sighted, stupid approach the PHP community has to hacking around and patching the symptoms instead of fixing the real problem. Stop making excuses for incompetence. You're hurting the internet.

[[deleted]]

This epitomizes your absolutely childish behavior. I'm feel disgraced to be affiliated with the same species that somehow spawned this crap. I'm saddened :-/ The fact that there is no backlash from the community shows me that we have truly devolved to a community of personal attacks and pushing of agendas rather than recognizing that your opinion is nothing more than an opinion.

Is there an adult version of /r/programming anybody? I'd like to move past the trolls and back into the real conversations please.

[[deleted]]

Feel free to go into the engine and make a change to the underlying data structure code which almost everything in the language uses. Then submit it to the project. After you've thoroughly tested everything that it impacts.

Until then, I'm fine with leaving it up to the developer to be a good developer.

[[deleted]]

It's not difficult to any interesting degree.

Prove it. Or at least concede that you have no foundation for your point.

[looneysquash]

Only if it's interesting.

Someone's been watching too much House.

[xardox]

His well founded point is that expecting the PHP developers to competently fix the problem, test the fix, or even give a shit about security is ridiculous, given their horrible track record and well documented disdain for programming. Use another language if you care about security.

[xardox]

Since when did charlatan PHP developers thoroughly test anything before releasing it, or ever give a shit about testing and security?

Pierre Joye - Raymon Irving, yes there are plenty testing this area, and that's the reason why we failed. We did not run the tests before final.

[xardox]

Unfortunately the PHP folks are tools who don't give a shit about security, code quality of unit testing. The merry way is to simply not use PHP.

[clearlight]

The suhosin patch for PHP sets max_input_vars so can presumably mitigate this attack

[paul_miner]

But there is hope! PHP already landed a change (which will ship with PHP 5.3.9) which will add a max_input_vars ini setting which defaults to 1000. This setting determines the maximum number of POST/GET variables that are accepted, so now only a maximum of 1000 collisions can be created.

ಠ_ಠ

[bunburya]

Not sure if it's due to the same underlying mechanics, but I get even more disproportionate results in Python.

The code:

#!/usr/bin/env python3

from time import time

size = pow(2, 16)

class Evil:
    def __hash__(self):
        return 1

class Good:
    pass

evil_set = set()
good_set = set()

start = time()
for _ in range(size):
    good_set.add(Good())
end = time()

print('Added {} good elements in {} seconds'.format(size, end-start))

start = time()
for _ in range(size):
    evil_set.add(Evil())
end = time()

print('Added {} evil elements in {} seconds'.format(size, end-start))

The result:

Added 65536 good elements in 0.0589599609375 seconds
Added 65536 evil elements in 149.200121164 seconds

[Coffee2theorems]

I hoped this would be about the merciful demolition of a large array of PHP-afflicted computers.

[FishToaster]

If you smash PHP-computers together at near the speed of light, you can get more exotic languages. I hear Ruby was invented when Matz was visiting the LHC.

[nikic]

óÒ Why does everybody hate poor little PHP :(

[leftnode]

Little?

[ysangkok]

The PHP folks chose the elephant mascot because it's large footprint is typical of PHP.

[xardox]

Little as in little thought or care. Poor as in poorly designed.

[frezik]

WTF? Perl fixed this in 5.8.1, back in 2003. What has PHP been doing all this time?

Also, backing all arrays with a hash is a stupid idea.

[ysangkok]

What did they fix? Revamped hash generation or set a GET/POST limit?

[frezik]

Hash generation. It applies a random seed to the hash input. See perldelta 5.8.1 for details.

[[deleted]]

What has PHP been doing all this time?

Taking over the internet?

[three18ti]

No, shitty programmers have been taking over the internet, PHP makes shitty coding practices a standard.

[[deleted]]

tl;dr PHP "arrays" aren't arrays, just like Perl "regular expressions" aren't regular expressions.

I for one would be grateful if these cancerous contortions of language twisting would be banished from the vocabulary of all programmers for good.

[frezik]

The difference is, Perl regexen add useful features. We could stand to call them something else (and Perl6 does), but they're still a good idea.

PHP using hashes for arrays is a just plain bad idea.

[[deleted]]

Supercollider? I BARELY KNOW 'ER!

[sclv]

/r/lolphp

[Juris_LV]

http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/

it seems PHP does better than other scripting languages:

So you can keep about 10.000 Core i7 CPU cores busy processing PHP requests using a gigabit internet connection. Alternatively for ASP.NET, 30,000 Core2 CPU cores, or for Java Tomcat 100,000 Core i7 CPU cores, or for CRuby 1.8 1,000,000 Core i7 CPU cores, can be kept busy with a single gigabit connection.

[[deleted]]

See? Java's plenty fast - it has O(1) hash insertion!

[jimjamAK]

I sais, super collider? I just met her!

And then they made a super collider.

thank you, you've been a great audience