Microsoft Issuing Unusual Out-of-Band Security Update

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.'"

Comments

Microsoft updates before Google and Oracle?

[InterestingFella]

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?

[Anonymous Coward]

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.

Re:Microsoft updates before Google and Oracle?

[Eirenarch]

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?

[neokushan]

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?

[jhigh]

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?

[Minwee]

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.

Patents could have saved us!

[nman64]

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!

[Nerdfest]

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!

[Nerdfest]

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

Priorities

[rsmith-mac]

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

[nman64]

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 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

[Eirenarch]

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

[AmiMoJo]

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

[datavirtue]

What do you run, a System/36?

Re:Priorities

[Eirenarch]

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

[Anonymous Coward]

"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...

 

Now, now...

[idbeholda]

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.

That is *not* out-of-band

[Anonymous Coward]

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

[Shatrat]

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

[neokushan]

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

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

[neokushan]

So because I only linked one source, it must be the ONLY one?

How about this one from 2008? https://msevents.microsoft.com/CUI/EventDetail.aspx?culture=en-US&EventID=1032393979&CountryCode=US

Or this one from last year? http://blogs.technet.com/b/msrc/archive/2010/09/30/q-amp-a-from-the-september-2010-out-of-band-security-release-webcast.aspx

Or this one from waaay back in 2006? http://blogs.technet.com/b/msrc/archive/2006/09/26/459194.aspx

And someone other than Microsoft: http://isc.sans.edu/diary.html?storyid=8062

And someone else: http://my.opera.com/wikipedian/blog/2011/09/28/for-reasons-unknown-microsoft-has-released

And someone else: http://www.dataprotectioncenter.com/antivirus/sunbelt/microsoft-will-do-out-of-band-patch-for-lnk-vulnerability/

Need I go on?

Re:That is *not* out-of-band

[HTH NE1]

"Oracle issues rare out-of-band update for Apache DDoS vulnerability"

"This is only the fifth time Oracle has issued an alert outside its routine quarterly patch cycle since introducing its own version of Patch Tuesday at the start of 2005."

That would be Microsoft's "Patch Tuesday". Oracle doesn't call it "out-of-band".

"Adobe Releases Out-of-Band Patch"

Adobe called it a "Security bulletin", and judging from when Adobe releases updates for Flash Player, I'm not even seeing a regular schedule to classify it as "out-of-band" as Microsoft defines it.

"Installing out-of-band updates for IBM BladeCenter devices using Telnet fails"

They're actually talking about delivery of patches via FTP and TFTP. Another talks about SNMP as the method. That is out-of-band and not what Microsoft is doing.

If anything about Microsoft releasing a patch off-schedule is "out-of-band" it is that they call special attention to it via press release rather than otherwise silently informing people via Windows Update. And that's assuming that they don't issue press releases anyway that usually get ignored by the press when they're on the regular schedule. It's not delivering the patch out-of-band, it's informing the public out-of-band, i.e. via an alternate band of communication. But it isn't delivery of the patch; that still occurs through the normal channel: Windows Update. It's conflating security "update" as a deliverable fix with security "update" as bulletin about the availability of the fix via the usual channels.

And that's the closest to a concession you'll get out of me on this.

Technical Background

[Light303]

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

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

[nahdude812]

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

Changing a hash function...

[vikingpower]

...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...

[vikingpower]

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...

[Waffle Iron]

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...

[iluvcapra]

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...

[Anonymous Coward]

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.

Re:Changing a hash function...

[shutdown -p now]

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.

28th chaos communication congress revelead this

[Anonymous Coward]

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

[HTD]

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

[Hentes]

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

[Anonymous Coward]

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)

[praseodym]

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

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

If using PHP5, change max_input_time

[Maow]

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 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

[inglorion_on_the_net]

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

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

[thsths]

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.

MaraDNS' Deadwood is immune

[MaraDNS]

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 (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.