Slashdot Mirror
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.'"
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.
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]
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.
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.
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".
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.
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
In short, sloppy programming.
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.
Religous speak to God. Insane are spoken to by God. When all shut up, one can finally hear Shostakovich in peace
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
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 ;)
...) 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).
Also the fixes PHP 5.4rc (and tomcat, and
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 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.
I miss the borg icon. :(
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:
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.
Please correct me if I got my facts wrong.
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.
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?
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):
Personally, I think it this is a pretty obvious attack to think of when designing a hash compression function.
MaraDNS is an open-source DNS server.
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
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?
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
Put the parameters into an indexed array and let the script that deals with the data sort it out. Much simpler and less likely to be exploited because you aren't doing calculations based on the input data.
If you aren't limiting the amount of data you accept in your application than hashtable performance is the least of your concerns
Improve performance of parameter processing for GET and POST requests. Also add an option to limit the maximum number of parameters processed per request. This defaults to 10000. Excessive parameters are ignored. Note that FailedRequestFilter can be used to reject the request if some parameters were ignored. (markt/kkolinko)
nosig today
if (paramHashValues.containsKey(key)) {
values = paramHashValues.get(key);
} else {
values = new ArrayList(1);
paramHashValues.put(key, values);
}
values.ensureCapacity(values.size() + newValues.length);
for (String newValue : newValues) {
values.add(newValue);
}
which means that if a hash-collision is detected the values are added to the valueset (instead of modifying the hash algorithm).
nosig today
I wonder if your favorite web application firewall (https://www.owasp.org/index.php/Web_Application_Firewall) has been patched.
nosig today
How could you moddown my post that had facts in it from a good source?
Answer the question!
(That's to the TRUE coward that modded down my post here that only posted FACTS about this issue -> http://developers.slashdot.org/comments.pl?sid=2596014&cid=38527098 )
APK
P.S.=> So, that "all said & aside": Who's the little weasel that's been doing this to MOST of my posts whenever I make them? Is that the "best you've got"?? Apparently so, & since that's the case here, that's truly, "piss poor" of you... apk
How will Dan Bernstein respond to the discovery that his hash functions are insecure?
a) "I never said they were secure"
b) "They are secure, they were just implemented wrongly"
c) "You idiots"
So if I read this correctly then web applications programmers of today do process POST data like this:
1. Web Server receives complete POST string, splits the string into its paramter=value pairs and inserts these into a hashmap
2. The Web Service programmer then finds out which parameters where posted by issuing a lookup for each and every parameter the service knows about
Is it really that bad? So the 2,0 programmers cannot process data as streams and act upon the data as it is processed?
Nice eggcorn ya got there.
http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx
The real solution is to use a data structure with good upper bounds for all the relevant operations. Such as trees with O(n log n). There is that pesky (log n), but not to worry... with a high enough branching factor this is a small constant for all practical purposes.
(As a bonus you also get a persistent data structure, but that's not really relevant here.)
Because Perl switched to a better hash function _and_ randomised it ages ago.
Having looked at many different fast hashing functions, I'm amazed at how many in the vulnerability report are still using the ancient multiply-by-small-constant and xor/add. That sort of thing tends to need a prime hash table size and a slow 'mod' operation. We have better hash functions that work on a 2^n table sizes.
MS patched it yesterday -> http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx
* Other vendors with the SAME issue released some fixes, you can read about them here:
http://www.nruns.com/_downloads/advisory28122011.pdf
---
PERTINENT QUOTES/EXCERPTS:
Fixes:
The Ruby Security Team was very helpful in addressing this issue and both CRuby and JRuby provide updates for this issue with a randomized hash function (CRuby 1.8.7-p357, JRuby 1.6.5.1, CVE-2011-4815).
Oracle has decided there is nothing that needs to be fixed within Java itself, but will release an updated version of Glassfish in a future CPU (Oracle Security ticket S0104869).
Tomcat has released updates (7.0.23, 6.0.35) for this issue which limit the number of request parameters using a configuration parameter. The default value of 10.000 should provide sufficient protection.
Workarounds:
For languages were no fixes have been issued (yet?), there are a number of workarounds.
= Limiting CPU time =
The easiest way to reduce the impact of such an attack is to reduce the CPU time that a request is allowed to take. For PHP, this can be configured using the max_input_time parameter. On IIS (for ASP.NET), this can be configured using the âoeshutdown time limit for processesâ
parameter.
= Limiting maximal POST size =
If you can live with the fact that users can not put megabytes of data into your forms, limiting the form size to a small value (in the 10s of kilobytes rather than the usual megabytes) can drastically reduce the impact of the attack as well.
= Limiting maximal number of parameters =
The updated Tomcat versions offer an option to reduce the amount of parameters accepted independent from the maximal POST size. Configuring this is also possible using the Suhosin version of PHP using the suhosin.{post|request}.max_vars parameters.
---
* Think that about "covers it"...
APK
P.S.=> Downmod my initial post http://developers.slashdot.org/comments.pl?sid=2596014&cid=38527098 all you like but it doesn't look good downmodding something that's pure fact (which my 1st post was, & nothing but fact (yet it was down moderated? Please, lol!))...
... apk
This type of reaction should be the norm not the exception.