Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Microsoft Issuing Unusual Out-of-Band Security Update

timothy posted more than 2 years ago | from the rolls-downhill dept.

Microsoft 156

wiredmikey writes "In a rare move, Microsoft is breaking its normal procedures and will issue an emergency out-of-band security update on Thursday to address a hash collision attack vulnerability that came into the spotlight yesterday, and affects various Web platforms industry-wide. The vulnerability is not specific to Microsoft technologies and has been discovered to impact PHP 5, Java, .NET, and Google's v8, while PHP 4, Ruby, and Python are somewhat vulnerable. Microsoft plans to release the bulletin on December 29, 2011, at 10:00 AM Pacific Time, and said it would addresses security vulnerabilities in all supported releases of Microsoft Windows. 'The impact of this vulnerability is similar to other Denial of Service attacks that have been released in the past, such as the Slowloris DoS or the HTTP POST DoS,' said security expert Chris Eng. 'Unlike traditional DoS attacks, they could be conducted with very small amounts of bandwidth. This hash table multi-collision bug shares that property.'"

Sorry! There are no comments related to the filter you selected.

Microsoft updates before Google and Oracle? (5, Interesting)

InterestingFella (2537066) | more than 2 years ago | (#38525470)

Why is Google not updating v8? And where is Java update? If Microsoft rushes to update their software before others, it is kind of telling. Well, good job for MS.

Re:Microsoft updates before Google and Oracle? (-1)

Anonymous Coward | more than 2 years ago | (#38525520)

Shut the fuck up you stupid shill. It's precisely because it affects different platforms that MS is rolling out the update before others. It is good for their damaged PR. Other than that they don't really care about having a secure platform.

Re:Microsoft updates before Google and Oracle? (5, Insightful)

Anonymous Coward | more than 2 years ago | (#38525560)

Do you realize the irony of calling someone else a shill, given the content of your message?

It wasn't that long ago that Slashdot conversations were both rational and coherently written. Thanks for ruining both of those things for everyone.

Now, now... (4, Interesting)

idbeholda (2405958) | more than 2 years ago | (#38525628)

Everyone has the right to post things that clearly show they're a complete retard. Unfortunately, it doesn't mean that they have ability to comprehend the result of their actions.

Re:Microsoft updates before Google and Oracle? (1)

nstlgc (945418) | more than 2 years ago | (#38525680)

In my humble opinion, it's a VERY long time ago.

Re:Microsoft updates before Google and Oracle? (4, Funny)

jhigh (657789) | more than 2 years ago | (#38525932)

I've been here a long time, and I can't say that I ever remember conversations being rational - although they are occasionally coherent.

Re:Microsoft updates before Google and Oracle? (1)

decsnake (6658) | more than 2 years ago | (#38527792)

I've been here a long time, and I can't say that I ever remember conversations being rational - although they are occasionally coherent.

quoted for truth

Re:Microsoft updates before Google and Oracle? (1)

Short Circuit (52384) | more than 2 years ago | (#38525992)

It wasn't that long ago that Slashdot conversations were both rational and coherently written.

Honestly, I think that may be a sign you're growing up.

Re:Microsoft updates before Google and Oracle? (2)

Minwee (522556) | more than 2 years ago | (#38526020)

It wasn't that long ago that Slashdot conversations were both rational and coherently written.

Honestly, I think that may be a sign you're growing up.

Or sobering up.

Re:Microsoft updates before Google and Oracle? (1)

Anonymous Coward | more than 2 years ago | (#38526862)

Do you realize the irony of calling someone else a shill, given the content of your message?

It wasn't that long ago that Slashdot conversations were both rational and coherently written. Thanks for ruining both of those things for everyone.

Let me fix that for you...

It wasn't that long ago on a geological time scale that Slashdot conversations were both rational and coherently written.

There that's better. Continue with your point.

Re:Microsoft updates before Google and Oracle? (0)

Anonymous Coward | more than 2 years ago | (#38529040)

Bah, you're just a shill of that shill.

Re:Microsoft updates before Google and Oracle? (1)

HWMTM (2500070) | more than 2 years ago | (#38525592)

It's precisely because it affects different platforms that MS is rolling out the update before others.

Uh, what are you trying to say here? I thought trolls had to make some sense in order to be effective.

Maybe times are a-changing.

Re:Microsoft updates before Google and Oracle? (1, Insightful)

pro151 (2021702) | more than 2 years ago | (#38525768)

Will slashdot ever do away with the anonymous coward abilty to post? That would eliminate most of the trolls.

Re:Microsoft updates before Google and Oracle? (4, Insightful)

neokushan (932374) | more than 2 years ago | (#38525880)

No it wouldn't, there's PLENTY of obvious troll accounts on Slashdot. To be honest, it's all part of the parcel of Slashdot. The first post is generally a waste of time. The second post is usually also a waste of time, often someone trying to GET the first post. The real discussions happen further down, where the trolls can't be bothered to read.

Despite all the idiots, I still find slashdot to be a worthy place for discussion with plenty of insightful and knowledgeable people around - you just have to look for it.

Re:Microsoft updates before Google and Oracle? (1)

pro151 (2021702) | more than 2 years ago | (#38525944)

Sigh ....you are probably right.

Re:Microsoft updates before Google and Oracle? (1)

_0xd0ad (1974778) | more than 2 years ago | (#38527244)

The first post is generally a waste of time. The second post is usually also a waste of time, often someone trying to GET the first post.

Do you have any idea how weird that looks to a pedant like myself?

<form method="post"> => POST the first post

Re:Microsoft updates before Google and Oracle? (1)

ArsenneLupin (766289) | more than 2 years ago | (#38527560)

... at least he didn't say POST the first get...

But nice, anyways. Next time I'll have the opportunity, I'll shoot for frist get!

Re:Microsoft updates before Google and Oracle? (1)

AdamJS (2466928) | more than 2 years ago | (#38525828)

I love how ACs are almost always abrasive assholes who can't form a coherent argument.
It's like, classic reverse trolling. So antiquated that it has looped around into some weird sincerity.

Anyways, this is good on MS which is particularly a desktop software company, whereas web-oriented companies like Google should be expected to have acted on this sooner since this affects their entire market.

Re:Microsoft updates before Google and Oracle? (1)

datavirtue (1104259) | more than 2 years ago | (#38525926)

Not always. It is important to have AC despite the idiots who use it most often. Why is this even a discussion?

Re:Microsoft updates before Google and Oracle? (1)

AdamJS (2466928) | more than 2 years ago | (#38526054)

Hence why I said almost. I was not suggesting removing the feature or anything.

Re:Microsoft updates before Google and Oracle? (1)

Anonymous Coward | more than 2 years ago | (#38525682)

"before others" ?

A workaround so that Apache Tomcat (a Java webserver) ain't affected is already out. Oracle may be slower on that one but Java webservers are getting patched as we're writing this.

So, well, good job for Apache!

Re:Microsoft updates before Google and Oracle? (2)

Eirenarch (1099517) | more than 2 years ago | (#38525814)

In fact Oracle claims that a fix in Java is not needed and they will fix Glassfish. I believe MS will do the same and will fix the ASP.NET request/response pipeline and not the core HashTable implementation.

Re:Microsoft updates before Google and Oracle? (1)

datavirtue (1104259) | more than 2 years ago | (#38525900)

Because of this:

Limit maximum POST size: Limiting the maximum POST request size can reduce the number of possible predictable collisions, thus reducing the impact of an attack.

Limit maximum request parameters: Some servers offer the option to limit the number of parameters per request, which can also minimize impact.

If you aren't already doing the above you are bat shit crazy anyway.

Re:Microsoft updates before Google and Oracle? (1)

InterestingFella (2537066) | more than 2 years ago | (#38526030)

You can't limit POST sizes that much if you ever indent to take file uploads. They count on POST limit too.

Re:Microsoft updates before Google and Oracle? (0)

Anonymous Coward | more than 2 years ago | (#38526746)

And the software which is ready to receive a POSTed upload can't possibly know ahead of time a certain IP will be sending a file?

Limit all POST sizes, then for an exact IP in an already logged-in session, lift the size ban if they recently requested the file-upload form. Explicitly log all unlock attempts so you can trace it back if any users were being naughty.

Why is that logic so difficult?

Re:Microsoft updates before Google and Oracle? (0)

Anonymous Coward | more than 2 years ago | (#38527236)

Since the POST size limit is typically a static configuration property of the Web container, the problem is twofold:
- It requires understanding the Web container code enough to make this value dynamic, which will involve modifying source that the application team has never had to look at before.
- It violates the layering in typical Web stacks that allows for separation of concerns. Now the application is dependent on the specific version of the Web container and potentially vice-versa.

The solutions already suggested, of randomizing the hash function used to store parameters, is much easier because it is most likely simple, compartmentalized change.

Re:Microsoft updates before Google and Oracle? (1)

_0xd0ad (1974778) | more than 2 years ago | (#38527264)

If you use Flash to handle the uploads it'd be trivial to split it into multiple POSTs and recombine on the server-side afterward.

Re:Microsoft updates before Google and Oracle? (1)

TheDarkMaster (1292526) | more than 2 years ago | (#38527816)

If you can use Flash.

Re:Microsoft updates before Google and Oracle? (1)

_0xd0ad (1974778) | more than 2 years ago | (#38528188)

I like to think HTML5 will be there pretty soon.

Re:Microsoft updates before Google and Oracle? (0)

Anonymous Coward | more than 2 years ago | (#38526162)

Did you read the article? Oracle says nothing needs to be done. The editor post is quite questionable based on the article.

Patents could have saved us! (3, Funny)

nman64 (912054) | more than 2 years ago | (#38525502)

See, everyone here complains that patents are always causing trouble, forcing each developer to do something a little differently to avoid infringing on another patent. If the techniques used for parsing the hash tables had been patented, forcing each server developer to come up with their own unique implementation that didn't mimic the techniques of the others, then this whole situation might only have impacted one or two server technologies. Now, all of these different server technologies using similar implementations are all affected by this single type of attack. With all of the diversity that patents enforce, they could have prevented a single attack like this from affecting so many implementations at once!

[/sarcasm]

Re:Patents could have saved us! (1)

Coldmoon (1010039) | more than 2 years ago | (#38525806)

As far as I can see, there is no reason you should feel sarcastic about what you posted. Standardization is a good thing in technology and should be pursued over rent seeking activities for the betterment of all. The real issue I see is that it is going to take a very catastrophic failure before anything can be changed and that is the real tragedy of current copyright law...

Re:Patents could have saved us! (4, Informative)

Nerdfest (867930) | more than 2 years ago | (#38525898)

You do realize that patenting of patenting hash table parsing would mean that even if someone came up with a different way of doing it, it would still be in violation, don't you? That's one of the problems with software patents ... it's not the implementation that's patented, it's the idea.

Re:Patents could have saved us! (1)

nman64 (912054) | more than 2 years ago | (#38526014)

I refer (in jest) to patenting the methods of parsing the hash table, not to the practice of parsing the hash table (which could be seen as an obvious necessity of handling POST data.) This is all just pedantry, however. My point was simply to make fun of the popular issue of software patents by pointing to a potential benefit that would have actually been a cure worse than the disease.

Re:Patents could have saved us! (2)

Nerdfest (867930) | more than 2 years ago | (#38526126)

My apologies. it's difficult to determine what's a joke and what isn't when discussing software patents.

Re:Patents could have saved us! (1)

nman64 (912054) | more than 2 years ago | (#38526482)

Oh, that's simple: it's all a joke... a really bad joke.

Re:Patents could have saved us! (1)

Anonymous Coward | more than 2 years ago | (#38526118)

Bullshit. Methods are patented, ideas are not.

Re:Patents could have saved us! (1)

nman64 (912054) | more than 2 years ago | (#38526506)

That's the way it used to be. You must be new here.

Priorities (5, Insightful)

rsmith-mac (639075) | more than 2 years ago | (#38525570)

There's a giant fucking DDoS bug in the hash table implementations of Java, PHP5, and Windows, and Slashdot presents it as a Windows security update?! Get your priorities straight and fix the title and the summary you nitwits, so that other admins see that this article is important. This is going to affect a lot more of us than just the Windows users.

Re:Priorities (-1)

Anonymous Coward | more than 2 years ago | (#38525688)

Trololol, not using crap windows, crap java or crap php. Nothing to see here.

Re:Priorities (2)

datavirtue (1104259) | more than 2 years ago | (#38525954)

What do you run, a System/36?

Re:Priorities (5, Informative)

nman64 (912054) | more than 2 years ago | (#38525738)

That the DDoS exists is yesterday's news (nevermind that it didn't make the Slashdot front page.) The point of this post is that Microsoft is issuing an out-of-band update. A security-aware and in-touch admin should have already learned of the n.runs advisory [nruns.com] yesterday. If they were really on top of things, they may have been aware of the potential danger as far back as 2003.

Re:Priorities (3, Interesting)

Eirenarch (1099517) | more than 2 years ago | (#38525758)

You've gotta love how /. reports this in an unbiased way :)
BTW it is not DDoS but just DoS (no distributed coordinated attack needed just a single request). Also it is not a bug in the hashtable implementation per se. You could argue that in the general case of a library hashtable one should prefer speed and predictability to DoS protection and use separate kind of HashTable for this kind of input. I am curious how companies will choose to patch this vulnerability.

Re:Priorities (2, Interesting)

Anonymous Coward | more than 2 years ago | (#38526798)

"should prefer speed and predictability"

This is rubbish bullsh!t. Randomized hash function are as simple as adding a simple XOR with a value generated randomly when the application starts up.

For every get(...) or contains(...) in your hash maps you have do a SINGLE ADDITIONAL XOR.

Your "perfs" argument is full bullsh!t.

Btw Perl does just this and even if *you* consider it is a feature to not use a randomized hash function, today Perl is fine while web servers using hashmaps written in other languages are not...

 

Re:Priorities (2)

AmiMoJo (196126) | more than 2 years ago | (#38525846)

To be fair I think the poster was trying for the "OMG Micro$oft fixed it before everyone else after 1 day" angle, but in doing so missed the rather critical point that the DDoS is only effective against web servers so most Windows machines won't need the update (since they don't serve web pages). I expect it will be pushed to all versions anyway as there may be other ways of exploiting the OS hash functions in this way, but at the moment it isn't like random Windows users will get hit by this.

Re:Priorities (1)

nman64 (912054) | more than 2 years ago | (#38525876)

That's also giving Microsoft too much credit. They were informed of the vulnerability ("responsible disclosure") last month.

Re:Priorities (1)

will3477 (705414) | more than 2 years ago | (#38525902)

Could this be more then a giant DDoS bug?

In theory, could you submit a legitimate value for key 1. That value then is the one that gets validated. Could you then submit a second value with key 2 that hash's to the same value as key 1 overwriting the data for key 1 in the data structure. Since the application isn't expecting a get/post value with key 2 the data never gets validated. When the value for key 1 is retreived, the hashes have collided the the data for key 2 is retreived.

Thinking about PHP, the collision would occur before the script executes, so validation should get key2's value and thus validation should value. It might not be the best failure mode, but validation should catch the error. Is that a good assumption and is that true for all the implementations? I think this is theoretical, but I can't convince myself to ignore the possibility either.

Re:Priorities (3, Informative)

Eirenarch (1099517) | more than 2 years ago | (#38526064)

No, this is not how hashtables work. The hashcode is not identity value but a means to sort elements into buckets for faster lookup. It won't get "confused" by equal hashes, it just gets somewhat slower when a large number of elements with equal hashes are added.

Re:Priorities (1)

will3477 (705414) | more than 2 years ago | (#38526140)

My bad. I know in theory they shouldn't, but I thought the article was saying they were not properly handling equal hashes; especially since one link talked about collision avoidance. Reading about it some more that isn't correct; thanks for the clarification, please mod my post down.

Re:Priorities (0)

Anonymous Coward | more than 2 years ago | (#38526446)

...or in this case, *much* slower, asymptotically speaking.

Re:Priorities (1)

Anonymous Coward | more than 2 years ago | (#38526106)

nerd rage much?

By default, not a problem (-1)

Anonymous Coward | more than 2 years ago | (#38527098)

"Mitigating Factors:

By default, IIS is not enabled on any supported Windows operating system.

Sites that disallow application/x-www-form-urlencoded or multipart/form-data HTTP content types are not vulnerable" FROM -> http://technet.microsoft.com/en-us/security/advisory/2659883 [microsoft.com]

---

* It's NOT just Microsoft products affected either as you noted - AND, MS is out there "beating this to the punch" BEFORE it can go outta control, by putting out an "out-of-band" patch fix!

APK

P.S.=> And, there you are...

... apk

RHEL Tomcat 5? (1)

bill_mcgonigle (4333) | more than 2 years ago | (#38529368)

I see Tomcat 6 and 7 got fixes from Apache. I can't find a bugzilla for tomcat5 at Redhat, though sometimes they like to hide security work from us until the update is out (which just frustrates us, especially after public disclosure).

I assume they're working on it, since RHEL5 is so massively deployed.

Anybody see anything I'm missing?

That is *not* out-of-band (4, Informative)

Anonymous Coward | more than 2 years ago | (#38525702)

Out-of-band would involve them mailing a CD to recipients, or some other form of delivery other than the Internet.

The phrase for which you were searching is "off-schedule".

Re:That is *not* out-of-band (1)

gumbi west (610122) | more than 2 years ago | (#38525910)

Since the affects servers, that would make a lot of sense too.

Re:That is *not* out-of-band (1, Insightful)

neokushan (932374) | more than 2 years ago | (#38526010)

No, I believe "out-of-band" is correct, if you go by the following definition:

"In general language, out-of-band refers to communications which occur outside of a previously established communication method or channel"

The "Method or Channel" in this instance is Patch Tuesday.

Re:That is *not* out-of-band (2, Interesting)

Shatrat (855151) | more than 2 years ago | (#38526382)

You're wrong, though. Out-of-band has a very specific meaning. It refers to having a backup management channel that is independent from your main network in case you accidentally turn off the wrong port or get a cut. For example many of our Fiber Optic sites also have a dial-up modem tied to copper, just in case all the fiber goes down at once.
This security update is in no sense out of band, it's just expedited a bit.

Re:That is *not* out-of-band (5, Interesting)

neokushan (932374) | more than 2 years ago | (#38526484)

Out-of-band doesn't have a "specific" meaning, though, that's kind of the point. In your workplace, it may mean one thing, however in this context the meaning is different. It means something else entirely when you talk about network protocols, for example.

However, if you're still sure you're correct, rather than posting about it on slashdot, you might want to tell Microsoft themselves that they're using the wrong term: http://blogs.technet.com/b/msrc/archive/2011/12/28/advanced-notification-for-out-of-band-release-to-address-security-advisory-2659883.aspx [technet.com]

Today we’re providing advance notification for an out-of-band security update to address the publicly disclosed issue described in Security Advisory 2659883. The release is scheduled for tomorrow, December 29, at approximately 10 a.m. PST.

Re:That is *not* out-of-band (1)

HTH NE1 (675604) | more than 2 years ago | (#38528378)

Citing the first (and only?) source to misuse the term is not citing an authority.

Re:That is *not* out-of-band (2)

neokushan (932374) | more than 2 years ago | (#38528984)

Re:That is *not* out-of-band (1)

HTH NE1 (675604) | more than 2 years ago | (#38529360)

Those all talk about Microsoft, originator of the misuse of "out-of-band". It's all just parroting the same source, reporting what Microsoft called it.

One company's misused term in marketing does not an agreed-upon definition make. Find an independent source that doesn't source or reference Microsoft and its off-schedule releases. And not one you make yourself, either.

The term "off-schedule" already existed and is specific and precise. There's no just cause for expanding the definition of "out-of-band" to encompass "off-schedule", that a regularly scheduled release date is a "method or channel".

Now, if you'll excuse me, I need to mambo dogface to the banana patch.

Re:That is *not* out-of-band (1)

neokushan (932374) | more than 2 years ago | (#38529492)

Find an independent source that doesn't source or reference Microsoft and its off-schedule releases. And not one you make yourself, either.

Ok then,

http://nakedsecurity.sophos.com/2011/09/17/oracle-issues-rare-out-of-band-update-for-apache-ddos-vulnerability/ [sophos.com] "Oracle issues rare out-of-band update for Apache DDoS vulnerability"

http://www.simplysecurity.com/2011/09/27/adobe-releases-out-of-band-patch/ [simplysecurity.com] "Adobe Releases Out-of-Band Patch"

http://publib.boulder.ibm.com/infocenter/director/v6r1x/index.jsp?topic=/director.tbs_6.1/fqm0_r_tbs_um_installing_out_of_band_updates_for_bc_using_telnet_fails.html [ibm.com] "Installing out-of-band updates for IBM BladeCenter devices using Telnet fails"

Re:That is *not* out-of-band (1)

HTH NE1 (675604) | more than 2 years ago | (#38528350)

Not unless the only date you can download your updates is on that single day of the month. The regular release date is not a method nor is it a channel. It's a schedule. This is out-of-schedule, or off-schedule.

"Rapid response" would be the marketable term they should have gone with.

I'm also not sure I'd call it unusual (1)

Sycraft-fu (314770) | more than 2 years ago | (#38526612)

While MS normally schedules updates to make things easier for people, they have issued updates out of the regular schedule numerous times in the past. I don't know precisely what their criteria is but if something is critical enough (maybe easy enough to exploit, already in the wild, serious enough consequences) they'll release a patch ASAP rather than waiting for patch Tuesday.

I always get grief about it because of whiny grad students. We have a number of grad students that run lengthy simulations and can't be bothered to make it save state every so often (which is funny because all other problem aside power failures happen here often enough). So they always want to turn off updates and we have to fight with them on that and explain that there is a given day they happen on. Then a really critical one will happen out of cycle and they'll cry and bitch, even though we always send out a warning e-mail.

So it isn't common. Most MS updates happen on a patch cycle, but this isn't some unprecedented move.

Re:That is *not* out-of-band (1)

oldhack (1037484) | more than 2 years ago | (#38526902)

You're fighting a losing battle, AC. IT security guys and their press like to think themselves as ninjas and delta force.

Re:That is *not* out-of-band (1)

hypermike (680396) | more than 2 years ago | (#38529014)

From Microsoft: "This bulletin summary lists an out-of-band security bulletin released on December 29, 2011."

Still trying to understand the attack? (-1)

Anonymous Coward | more than 2 years ago | (#38525784)

As I gather, the idea is to create keys (parameters) that hash to the same value, which fills up the buckets with the same key, over and over, thus causing a lot of server load?

Couldn't this be solved easily & quickly by limiting the NUMBER of parameters accepted? (in the parse phase, prior to them being hashed) ?

Re:Still trying to understand the attack? (1)

Anonymous Coward | more than 2 years ago | (#38525840)

Couldn't this be solved easily & quickly by limiting the NUMBER of parameters accepted? (in the parse phase, prior to them being hashed) ?

Yup. That is exactly what the Apache Tomcat people are doing: https://mail-archives.apache.org/mod_mbox/www-announce/201112.mbox/%3C4EFB9800.5010106@apache.org%3E [apache.org]
In short, sloppy programming.

Technical Background (5, Insightful)

Light303 (1335283) | more than 2 years ago | (#38525830)

Just to make it clear - this affects a whole lot of systems and is based on a flaw in the design of hash-tables:

http://packetstormsecurity.org/files/108209/n.runs-SA-2011.004.txt [packetstormsecurity.org]

Basically you can pre-calculate a huge set of POST parameter names which will all be hashed to the same value. Since these are stored in a hash-map by most web-frameworks - this will lead to a o(n) lookup time instead of a o(1) lookup time, when testing the hash-map for a given parameter name.
This will max out your cpu quite quickly depending on how many lookups you perform per request.

Since the attack has "script kiddie" difficulty, this needs to be patched ASAP by all vendors ... or we will see a lot a downtime on many public servers.

Re:Technical Background (0)

Anonymous Coward | more than 2 years ago | (#38526544)

I disagree. This not a flaw in the hash-tables in general. Hash-tables do not guarantee O(1) lookup.
The flaw is in assuming exactly this (not guaranteed) property for unvalidated, possibly malicious external data.
Or in other words: The problem is using a (ordinary) hash-table for something it is not suitable for.
To avoid the DOS issue you need to look at the _worst case_ performance of the data structure/algorithm.
There are loads of ways, but randomizing the hash is questionable enough since it still does not fix the worst case performance (just makes it harder to trigger on purpose).

Re:Technical Background (2)

nahdude812 (88157) | more than 2 years ago | (#38528322)

More importantly, although lookup is O(n), the insert growth is O(n**2). The request environment preparation for many web languages such as PHP, .NET, Java, Ruby, and Python will time out before script execution even begins (while maxing out a CPU for whatever the request timeout is, usually at least 30 seconds).

The vulnerability is essentially that it's easy to generate intentional key hash collisions for these hash table implementations. This class of vulnerability has been known about since at least 2003.

Source: http://www.nruns.com/_downloads/advisory28122011.pdf [nruns.com]

Changing a hash function... (2)

vikingpower (768921) | more than 2 years ago | (#38525860)

...like the one used in Java is not going to be easy. The existing one has been around from the very beginnings on. A new one must:

1) be at least as "strong" ( read: as hard to reverse ) as the old one

2) a manifest patch against the bug described in the OP's references, which, indeed, *does* look like a serious bug

3) be thoroughly tested against criteria 1 and 2

That is a helluvajob.

Re:Changing a hash function... (1)

nman64 (912054) | more than 2 years ago | (#38525906)

They don't necessarily have to replace a hash function. They have to implement collision resolution [wikipedia.org] .

Re:Changing a hash function... (1)

nman64 (912054) | more than 2 years ago | (#38525934)

...that is, they must implement a new collision resolution strategy that avoids the problem described in the advisory.

There are also other ways of mitigating this problem in web servers without addressing the root problem.

Re:Changing a hash function... (4, Informative)

vikingpower (768921) | more than 2 years ago | (#38526144)

Be advised that there IS collision resolution present in e.g. java.util.Hashtable; the default load factor is 0.75, which in practical use ( I've been playing with that class for over 12 years now ) is very close to optimal for run-of-the-mill uses. Also, there is the stratetegy of internal collision recording. I do agree, though, that it is not feasible to implement such tactics in the hashCode() method of any POJO. Which is, IMHO, a re-design of the java.lang.Object.hashCode() method would be worth thinking of.

Re:Changing a hash function... (1)

iluvcapra (782887) | more than 2 years ago | (#38527844)

Hopefully not too many people depend on hashCode() always returning the same value for identical objects between runs. Fixing this vulnerability, the way TFA recommends, would necessarily break this expectation. I see in the documentation [oracle.com] they word the contract in such a way that people should be scared off from doing it this way, but you never know :)

Re:Changing a hash function... (2)

shutdown -p now (807394) | more than 2 years ago | (#38529100)

I don't know about Java, but for .NET there is a specific disclaimer that Object.GetHashCode() can not be relied upon to return the same value between different versions of the framework, or even between different runs - even for well-known value types such as int or string.

Re:Changing a hash function... (0)

Anonymous Coward | more than 2 years ago | (#38529812)

Hopefully not too many people depend on hashCode() always returning the same value for identical objects between runs.

It might break compatibility of Serialized objects though...

In any case, the problem isn't with the Java HashMap implementation - it's more that webserver software is using this structure without considering its worst case behaviour. Java's HashMap need not change - it's the applications which need a more specialised data structure.

Re:Changing a hash function... (1)

Eirenarch (1099517) | more than 2 years ago | (#38526006)

Your statement is correct but your reasons are wrong. First of all the function is not hard to reverse. It is not cryptographic hash its only purpose is to give even distribution in the common case so that it can be used for hashtables. The only way to fix the function would be to add some kind of randomness but chances are that people are depending on the hash being stable (and they shouldn't!) so Java designers will be reluctant to change it. On the other hand if a random salt is added each time the JVM is started that may give a hash distribution that is not even in some real world case which means that some programs may suffer performance hit randomly. And finally this can be patched in the request/response pipeline for web requests. The vendors will probably prefer patching the web parts instead of the whole platform.

Re:Changing a hash function... (1)

vikingpower (768921) | more than 2 years ago | (#38526048)

First of all the function is not hard to reverse.

Really ? Well, I would like to see your best attempt at reversal. Feel free to email me. This is getting interesting.

Re:Changing a hash function... (1)

iluvcapra (782887) | more than 2 years ago | (#38527954)

He's not right but it's relatively easy to find collisions in the fast hashing algorithms that platforms use, like adler or CRC32.

Re:Changing a hash function... (1)

bezpredel6 (1796620) | more than 2 years ago | (#38526566)

The problem with this approach is that the next target will be XML based services, JSON services, and whatever else that is out there that accepts user input and turns it into a map. Feels like yet another pointless rule that developers will have to remember till the end of days (and will probably keep ignoring in 99% of the cases). Processing input from users? Use String objects with a cryptographically strong hash. Pay the price, keep track of them all the way downstream.

Re:Changing a hash function... (2)

iluvcapra (782887) | more than 2 years ago | (#38527892)

A more simple solution would be to simply go through submitted POST keys and filter out unexpected or illegitimate keys -- the application made the form, so it should know exactly what it should be getting back. If you load the key strings into a vector or an array, filter it, and THEN create a map/hash/whatever, you should be safe.

I admit this is an eye-opening vuln. I'd never thought twice about using tainted strings as hash keys.

Re:Changing a hash function... (1)

Ice Station Zebra (18124) | more than 2 years ago | (#38529800)

I don't think you understand the vulnerability. By the time the POST parameters get to you, they may already be in a hashtable. For example $_POST in php.

Re:Changing a hash function... (4, Insightful)

Waffle Iron (339739) | more than 2 years ago | (#38526168)

This is not an issue with a hash function. This is a security issue that involves validating external inputs to a program before attempting to operate on them.

The web servers shouldn't be attempting to store these values in a hashtable at all. Sanity checks should be rejecting requests that have too many parameters in the first place.

Re:Changing a hash function... (2)

Anonymous Coward | more than 2 years ago | (#38528084)

This is a security issue that involves validating external inputs to a program before attempting to operate on them.

Not at all. This is not a case of lack of input validation, this is a case of software not being able to handle a valid input correctly. The vulnerable code is a generic piece of code, it doesn't know what the higher level application considers valid.

You could "fix" it by having the higher level application tell the lower layer the maximum number of parameters, or even better a list of all permitted names. However either of those "fixes" would change the API.

A hash table is a way to optimize the average case performance at the expense of an increased performance penalty in the worst case. The vulnerability really is that average performance in this case means average over random inputs, and an adversary is not going to choose random inputs, he will choose worst case inputs.

There are two ways to really fix the root problem. Either randomize the algorithm such that it is not good on average over all inputs, but rather such that on any input chosen by an adversary you will have good performance on average over choices made by the algorithm. Or make an algorithm that is not just good on average but also good in the worst case.

There are well known ways to solve the problem in O(log n) time. A hash table improves the performance to O(1) in typical use cases, but increases the worst case to O(n). And then somebody decided to use a hash table in a scenario where the worst case complexity was what mattered.

A simple fix is to put a cap on the length of any hash chain and fall back to a balanced tree in case the chain reaches maximum size. A better way is to simple replace the chain in each hash bucket with a balanced tree. As long as each hash bucket has 0-2 elements there will be no rebalancing, thus there will be no rebalancing and performance will be the same for the tree and the linked list. Once the bucket size grows, the balanced tree will be logarithmic in the size of the bucket, the standard linked list is linear in the size of the bucket. Guess, which would deal best with adversarial inputs.

Combining randomized hashing with an efficient way of dealing with large buckets is a good algorithm for a variety of scenarios. If your hash function is good you can simply choose a random value once you initialize the hash table and instead of computing h(x) you compute h(r||x). The adversary doesn't know r, so he cannot produce collisions. And r remains constant for the life time of the hash table, so you will always be able to find x again. As far as I know MD5 is still good enough for such a use case, a simple CRC may not be, the adversary could be able to produce a collision without knowing r.

Comparing this DoS attack with the cryptographic attacks on MD5 is a bit misleading. A cryptographic hash function produces a large output, and applications assume it will not produce any single collision ever. A hash function for a hash table produces a much shorter output, and you accept that it produces collisions even on random input. If the hash table is so large that you don't have any collisions at all, it is a waste of memory. So for a hash table collisions are a normal part of normal operation, and the code can deal with them, it just costs more CPU time if they are frequent. There is a major difference between the large hash outputs that must never ever collide, and the shorter outputs that are so short they are guaranteed to collide frequently, where the only requirement is that they don't collide too frequently.

28th chaos communication congress revelead this (5, Informative)

Anonymous Coward | more than 2 years ago | (#38525870)

the Chaos Computer Club is doing their congress at the moment and the hash collision problem was topic yesterday:

28c3: Effective Denial of Service attacks against web application platforms
http://www.youtube.com/watch?v=R2Cq3CLI6H8

no fix for Python in the making (5, Interesting)

HTD (568757) | more than 2 years ago | (#38525940)

What worries me the most is that according to the guys holding the presentation there was no reponse from the python team on that issue. Also plone, a web platform based on python, they tested their attack against it and notified the plone guys, didn't implement any countermeasures after being notified. This was fixed in perl in 2003, it's interesting that the opensource community didn't bother to check the hashtable implementations of all other languages back then. Are they in competition not telling others that something important needs to be fixed? Java devs, chose not to change their hash algo in 2003 BTW because it is a too integral part. Well the modified version is in use for 8 years in perl, might wanna upgrade it this time ;)
Also the fixes PHP 5.4rc (and tomcat, and ...) implemented are just workarounds that were already available before with the suhosin extension for example. Limiting the number of variables you can POST is a wannabe fix, can be circumvented with JSON for example (given that the app uses json_decode() on the receiving end).

Re:no fix for Python in the making (2)

Hentes (2461350) | more than 2 years ago | (#38526352)

According to these guys this attack on a 64bit Python system is impractical, and as the world is shifting to 64bit anyway the problem might solve itself given enough time.

The journalist is terribly confused (2, Informative)

Anonymous Coward | more than 2 years ago | (#38526076)

The journalist says the vulnerability resides in the "POST function" of... something? Then he mentions MD5 collisions, and goes on quoting extensively from a report by a security firm.

More technically accurate version:
Hash tables (key-value stores) use a hash function to generate an internal representation of the key. When accessing the hash, the key gets hashed and compared to the internal representation to find the correct value. If there are collisions for a certain key, the implementation must enumerate through the values, which is much more expensive than the O(log n) hash table read access is supposed to be. (Write access would probably be the O(n^2) the report quotes.) Therefore, it is preferable for a hash function to be both short and fast, have few collisions, and probably have some per-process randomisation to mitigate these attacks.

HTTP POST has nothing to do with this except that web frameworks/programming interfaces usually parse the GET/POST parametres into a hash table on every request. Therefore, if the attacker creates enough parametres (keys) that hash to the same internal representation, he can bog down the web server before any user code runs.

This presentation at 28C3 (with video) (4, Informative)

praseodym (813457) | more than 2 years ago | (#38526082)

This research was presented by n.runs at the 28th Chaoas Communication Congress: http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html [events.ccc.de] .

The presentation was recorded and can be viewed at http://www.youtube.com/watch?v=R2Cq3CLI6H8 [youtube.com] .

Re:This presentation at 28C3 (with video) (0)

Anonymous Coward | more than 2 years ago | (#38527192)

Is this how people talk at all of the presentations? I swear, they could had covered everything in 15 minutes tops.

no borg-bill (0)

Anonymous Coward | more than 2 years ago | (#38526112)

I miss the borg icon. :(

If using PHP5, change max_input_time (5, Informative)

Maow (620678) | more than 2 years ago | (#38526184)

I agree with others, this is not a Microsoft issue, it's an issue for all sysadmins.

Anyway, from http://packetstormsecurity.org/files/108209/n.runs-SA-2011.004.txt [packetstormsecurity.org] is this helpful bit to reduce your susceptibility to attack, if you're using PHP:

The maximal POST request size is typically limited to 8 MB, which when
filled with a set of multi-collisions would consume about four hours of
CPU time on an i7 core. Luckily, this time can not be exhausted because
it is limited by the max_input_time (default configuration: -1,
unlimited), Ubuntu and several BSDs: 60 seconds) configuration
parameter. If the max_input_time parameter is set to -1 (theoretically:
unlimited), it is bound by the max_execution_time configuration
parameter (default value: 30).

Better Writeup (5, Informative)

inglorion_on_the_net (1965514) | more than 2 years ago | (#38526422)

Here is a better writeup from Ars Technica: http://arstechnica.com/business/news/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack.ars [arstechnica.com]

From that page:

the flaw affects a long list of technologies, including PHP, ASP.NET, Java, Python, Ruby, Apache Tomcat, Apache Geronimo, Jetty, and Glassfish, as well as Google's open source JavaScript engine V8

the theory behind such attacks has been known since at least 2003

Klink and WÃlde showed that "PHP 5, Java, ASP.NET as well as V8 are fully vulnerable to this issue and PHP 4, Python and Ruby are partially vulnerable, depending on version or whether the server running the code is a 32-bit or 64-bit machine

The actual vulnerability seems to be that many web applications (or application servers or libraries or what have you) parse form data from HTTP POST requests into hash tables, using known hashing algorithms. If an attacker sends a POST request using specifically crafted parameter names that all hash to the same value, inserting these into the hash table will take O(n^2) time, which opens up affected software to a denial of service attack.

Re:Better Writeup (2)

thsths (31372) | more than 2 years ago | (#38527000)

Indeed, and it sounds more like a programming flaw than a platform flaw. If you need a hash function with cryptographic properties, don't use MD5. It may not always be obvious, but if you work with unverified user input, chances are that you need some level of cryptographic strength.

It is however peculiar that MS rolls out an out-of-band patch for a DOS flaw. I suppose this means it has been exploited in the wild in several places, and MS is moving into "proactive mode" - which is rare enough an occasion :-). The flaw itself certainly does not warrant this kind of rush.

Easy patch? (1)

colfer (619105) | more than 2 years ago | (#38526736)

The RC version of PHP has a new directive, max_input_vars. Should be easy to implement. The POST data come in as a string, just like a query string, as I recall it. So just count the number of ampersands.

Article says the DoS happens as the hash table is populated, so there is no easy fix for the PHP user. A patched version of PHP must be compiled. Or maybe some apache magic can be applied before the data hits PHP. Something in mod_rewrite in the .htaccess?

Re:Easy patch? (1)

colfer (619105) | more than 2 years ago | (#38527510)

Apache has an input filter mechanism. Could also proxy I guess. Easy to detect the bad input, just a question of how to hook.

MaraDNS' Deadwood is immune (3, Informative)

MaraDNS (1629201) | more than 2 years ago | (#38527700)

You know, I knew this issue would come out of the woodwork one day; I went to some bother to have a randomized hash compression function for MaraDNS 2.0's recursive resolver (Deadwood).

From the relevant man page [maradns.org] (this part was last updated in September of 2010):

To protect Deadwood from certain possible denial-of-service attacks, it is best if Deadwood's prime number used for hashing elements in the cache is a random 31-bit prime number. The program RandomPrime.c generates a random prime that is placed in the file DwRandPrime.h that is regenerated whenever either the program is compiled or things are cleaned up with make clean. This program uses /dev/urandom for its entropy; the file DwRandPrime.h will not be regenerated on systems without /dev/urandom.

[...]

If using a precompiled binary of Deadwood, please ensure that the system has /dev/urandom support (on Windows system, please ensure that the file with the name secret.txt is generated by the included mkSecretTxt.exe program); Deadwood, at runtime, uses /dev/urandom (secret.txt in Windows) as a hardcoded path to get entropy (along with the timestamp) for the hash algorithm.

Personally, I think it this is a pretty obvious attack to think of when designing a hash compression function.

Privilege Escalation? (1)

jpvlsmv (583001) | more than 2 years ago | (#38528268)

Am I missing something? The posts so far refer to this as a hash table collision DOS vulnerability, but MS categorizes it as "Elevation of Privilege" vulnerability.

--Joe

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?