Forgot your password?
typodupeerror
Microsoft Programming Security

Microsoft Issuing Unusual Out-of-Band Security Update 156

Posted by timothy
from the rolls-downhill dept.
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.'"
This discussion has been archived. No new comments can be posted.

Microsoft Issuing Unusual Out-of-Band Security Update

Comments Filter:
  • by InterestingFella (2537066) on Thursday December 29, 2011 @10:27AM (#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.
    • by Anonymous Coward

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

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

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

      • You can't limit POST sizes that much if you ever indent to take file uploads. They count on POST limit too.
        • by _0xd0ad (1974778)

          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.

        • Besides:

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

          This is disingenuous at best. It reduces the number of possible collisions, but increases the number of likely collisions, by reducing the size of the input set.

          This is easy to see by reducing the problem (reductio ad absurdum): imagine the likelihood of collisions given 1000 posts, limited to 1000 characters each. Now imagine the likelihood of a collision given 1000 posts, limited to 3 characters each. The number of collisions due to cryptographic weakness might become ridiculously small, but th

  • by nman64 (912054) * on Thursday December 29, 2011 @10:30AM (#38525502) Homepage

    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]

    • by Coldmoon (1010039)
      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...
    • by Nerdfest (867930) on Thursday December 29, 2011 @11:06AM (#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.
  • Priorities (Score:5, Insightful)

    by rsmith-mac (639075) on Thursday December 29, 2011 @10:36AM (#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 (Score:5, Informative)

      by nman64 (912054) * on Thursday December 29, 2011 @10:50AM (#38525738) Homepage

      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: (Score:3, Interesting)

      by Eirenarch (1099517)

      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: (Score:2, Interesting)

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

    • by AmiMoJo (196126)

      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.

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

  • by Anonymous Coward on Thursday December 29, 2011 @10:47AM (#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".

  • by Light303 (1335283) on Thursday December 29, 2011 @10:59AM (#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.

    • by nahdude812 (88157) *

      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 20

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

    • by Waffle Iron (339739) on Thursday December 29, 2011 @11:24AM (#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.

      • by 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 per

  • by Anonymous Coward on Thursday December 29, 2011 @11:03AM (#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

  • by HTD (568757) on Thursday December 29, 2011 @11:10AM (#38525940) Homepage
    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).
    • by Hentes (2461350)

      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.

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

  • by praseodym (813457) on Thursday December 29, 2011 @11:19AM (#38526082) Homepage

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

  • by Maow (620678) on Thursday December 29, 2011 @11:26AM (#38526184) Journal

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

    • An easy solution to this was pointed out in that article: limit the number of input parameters.

      And Apache Tomcat already has a release that does just this with a customizable property. The default is set to 10,000 parameters. If you use Tomcat as your servlet engine, then it should be resolved with 7.0.23 or 6.0.35.

      A direct quote from the article:

      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.

  • Better Writeup (Score:5, Informative)

    by inglorion_on_the_net (1965514) on Thursday December 29, 2011 @11:47AM (#38526422) Homepage

    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.

    • by thsths (31372)

      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

      • by swillden (191260)

        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.

        This isn't an MD5 issue. I doubt that most of these hash table implementations use any cryptographic hash function (why bother? Cryptographic collision resistance is expensive and not generally relevant to hash table uses), but even if they used iterated SHA-512 interspersed with RIPEMD, TIGER and WHIRLPOOL in a pseudo-random sequence, the implementation would still be vulnerable.

        How? Well, all the attacker has to do is to predict with reasonable accuracy the size of the hash table. Since the attacker

        • by rekoil (168689)

          That's how perl was fixed - XOR each incoming key with a random value generated when the hash is initialized.

    • by pmontra (738736)
      In the case of Ruby it looks like it is a flaw in the implementation of the Hash class. Ruby 1.9 is OK but Ruby 1.8 had to be fixed. The safe version is 1.8.7-p357.
  • 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?

    • by colfer (619105)

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

  • by MaraDNS (1629201) on Thursday December 29, 2011 @01:10PM (#38527700) Homepage Journal

    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.

    • by Skapare (16644)

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

      I agree it is obvious. But it's also simple to avoid. And you don't even need high entropy for it. Storing a random number ONCE (like at install time) and then used in all instances would be resistant in most cases. So if /dev/urandom isn't available for some reason, that's not a show stopper (fall back to a hash of the install date, perhaps)

      For some things I'm doing, I even skipped hash and went to BST. (My) BST (code) benched better than hash for scales up to what I usually do. I also made a HCBST (

  • 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

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

  • I wonder if your favorite web application firewall (https://www.owasp.org/index.php/Web_Application_Firewall) has been patched.
  • 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?

Men love to wonder, and that is the seed of science.

Working...