#2381 Red Hat: Possible XML Hash DoS in sblim

Security
closed-fixed
6
2012-03-15
2012-03-07
No

Hi, the reason I'm emailing you is that your program appears to have an internal implementation of an XML parser. As you may or may not know a Hash DoS vulnerability has been found to affect a large number of programming languages (C, C++, Java, PHP, Python. Ruby, etc.) and a large number of programs that implement data arrays using hash functions to generate key values from user supplied input (especially in the XML space). If you've already found and fixed this vulnerability in your code please let me know (I wasn't able to find a fix, but that doesn't mean one hasn't been committed already).

So what is the problem? Put simply an attacker can provide a specially formatted XML file with a few hundred or thousand entries that will cause a pathological worst case behavior for array insertions thatwill consume several seconds or possibly even minutes of CPU time resulting in a denial of service (DoS).

However, strictly speaking, not all XML implementations are vulnerable to exploitation. For example an implementation that only reads an administrator supplied XML configuration file are highly unlikely to be attacked (since the attacker would need administrative access and could likely cause the program to do bad things in other ways as well). Also depending on the language the applications is written in and how the implementation is done it may be addressed by a language update (e.g. Python).

So what I am trying to find out is:

1) Can users pass data to your XML parser (or is it used on trusted data or internally generated data only)?
2) Does your implementation of hashing the key values use randomness, or is it deterministic (e.g. does it simply hash the key with MD5 or something else that will always produce the same hash value for the same input)? If it uses randomness can you let me know how (e.g. a function name or something that I can check quickly).

I would appreciate answers either way (if you are vulnerable or not vulnerable or it is unknown), that way I can cross you off the list if not vulnerable. If you need help researching this I'm more than willing to provide assistance.

Please note that while the following URLs have some information on this class of issue they do not list every single vulnerable language and application (the original focus was on web services, it was only later found to affect XML and other parsers that handle user serializable data. Also if you would like any assistance in correcting this issue please feel free to poke me back.

It should be noted that fixing this issue is relatively simple, just add a small random seed so that the hashed key values are not predictable. Please note that the level of randomness needed is not huge, for example using srand(time(NULL)) on a typical Linux system gives you 2^32 possible values (about 4 billion) which makes pre-computation and testing of collision values nearly impossible (the amount of testing to find a correct value would in itself constitute a significant flood of data). This is in fact the exact solution used by libxml2 to correct this vulnerability.

http://www.ocert.org/advisories/ocert-2011-003.html - #2011-003
multiple implementations denial-of-service via hash algorithm collision

https://rhn.redhat.com/errata/RHSA-2012-0324.html - libxml2 security
update

http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/
- - Effective DoS attacks against Web Application Plattforms ? #hashDoS
[UPDATE3]

http://en.wikipedia.org/wiki/Hash_table - Hash table explanation

Discussion

  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Opened on behalf of Kurt Seifried at Red Hat... dialog to follow

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Kurt>

    In the file:

    sblim-cim-client2-2.1.11-src/src/org/sblim/cimclient/internal/cimxml/CIMXMLParserImpl.java

    which uses arrays, the arrays use hashing internally, and since Java can't fix it (they specified how arrays are handled and a random seed can't be added which is the fix used in libxml, expat, etc.) some other solution (typically limiting the number of inputs if possible) is being used. In the case of XML this doesn't work super well since many legitimate XML implementations have to process large amounts of XML. Now I'm not sure if sblim is vulnerable (e.g. is the XML passed in user controlled?) but I'm alerting all the projects that potentially have this vulnerability as much as I can in case things can be fixed.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Dave>

    I am the SBLIM Java CIM Client developer. The Client indeed includes an internal implementation of an XML parser so that it can provide support for DOM, SAX and PULL parsers to its applications. So, to answer your two questions from another note NOT included below:

    1) Yes, users can pass data to the Client's XML parser. The Client supports the CIM-XML over HTTP(S) protocol - the one and only protocol it currently supports - so that is what it is all about, and while some connections may be trusted/secure, most are not. This is especially true of indications, where the Client just listens on a port for someone/anyone to send it CIM-XML.

    2) The hashing used is deterministic, usually based on just the key, IF I am understanding what the issue is. Are you referring to the HashMaps used in CIMObjectFactory.java and NodeFactory.java (both in org.sblim.cimclient.internal.cimxml.sax.node package)? I am not seeing what hashes you are referring to in the file mentioned below, CIMXMLParserImpl.java.

    I would be happy to work with you on this, but could use a couple more pointers to see what you are referring to within CIMXMLParserImpl.java.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Kurt>

    So for example:

    https://access.redhat.com/security/cve/CVE-2012-0841

    libxml simply added an srand(time(NULL)) as a seed to the hash function to prevent exploitation of this issue.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Dave>

    Yes, I understand the workaround of introducing some bit of randomness to the hash key such that successive Client instances produce different values for the same XML input. What I'm wondering is where inside of CIMXMLParserImpl.java do you think this hashing is taking place? There are a couple classes in the SAX parser that use the Java language construct HashMap, are those what you are referring to?

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Kurt>

    To be honest I haven't looked in depth, you are one of about 30 affected applications I'm dealing with (and in total across the Open Source world there are several hundred). If they're strictly using the Java HashMap than there's not much that can be done, Oracle has refused to fix (largely valid as they defined the hashing algorithm, and now cannot change it), so your only real choice is to limit the number of inputs (e.g. what tomcat did https://bugzilla.redhat.com/show_bug.cgi?id=750521\) which may/may not work for some XML implementations. Mostly I'm expecting the Java XML stuff to largely end up being "CANTFIX" and we live with it.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Dave>

    Sorry for the interruptions, I'm just trying to figure out what you want me to attempt to address. I looked through

    sblim-cim-client2-2.1.11-src/src/org/sblim/cimclient/internal/cimxml/CIMXMLParserImpl.java

    and while I see plenty of array usage, I don't see where any hashing comes into play with them. The product uses HashMaps in

    sblim-cim-client2-2.1.11-src/src/org/sblim/cimclient/internal/cimxml/sax/NodeFactory.java

    and these are used during XML parsing to lookup CIM-XML keywords.

    If these are what you are talking about, can I append a random string to the String keys so that different hashcodes will be generated every time the product executes? i.e. CIMd59msqdjpwqf)q for one, then CIMbdq4^%afvnff the next time, etc.

    I can't switch to Integer keys because then a collision would return a false positive ("CIM" returned when some bogus string produces same hash value), so I'd have to do a strcmp for each non-null get() to make sure it is CIM and not bogus.

    Also, I can't limit number of inputs, the Client needs to be able to parse an entire CIM-XML response, and these are already easily approaching 256K+ on larger systems.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Kurt>

    Yeah the problem is Oracle can't fix the Hashmaps because the spec defines how hashing takes place. Languages like Python, ruby and Perl were able to fix the array code which means all the underlying XML stuff (like PyXML, etc) is no longer affected. Unfortunately this is not the case with Java.

    Yah. One solution would be to append a random string to each key, the same random string would work (effectively you're adding the random seed in the data rather than in the hash array). Remember, it doesn't need to be super strong, just enough to defeat precomputed attacks. Something like Random() should be plenty. My one thought/concern would be performance impacts, speed and memory, I'd be curious to know if it's a noticeable problem (on modern hardware I doubt it, but I could be wrong).

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Dave >

    So this is what I threw together to generate an 8-byte random string that I would append to keys (this only runs once during initialization):

    Random generator = new Random(System.currentTimeMillis());
    byte randomByte[] = new byte[1];
    StringBuilder randomString = new StringBuilder();
    while (randomString.length() < 8) {
    ____generator.nextBytes(randomByte);
    ____if (randomByte[0] > 0) {
    ________char ch = (char) randomByte[0];
    ________if (Character.isLetterOrDigit(ch)) randomString.append(ch);
    ____}
    }
    iRandomString = randomString.toString();

    Suggestions?

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Proposed patch

     
    Attachments
  • Dave Blaschke

    Dave Blaschke - 2012-03-07

    Proposed patch sent in for performance analysis

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-09

    The following Java HashMap was fixed:

    1) NodeFactory.NODENAME_HASH

    The following HashMaps were NOT fixed:

    1) NodeFactory.cParserMap - used after XML element verified as CIM
    2) CIMObjectFactory.cTypeStrMap - used on valid CIM objects
    3) NodePool.iPoolMap - used after XML element verified as CIM

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-09

    Dennis did a couple runs with the old jar (Experimental) and new jar (Experimental + patch) and there was a 6.28% performance impact:

    Run1 Run2 Run3 Run4 Sum of total time

    old jar 124012 110801 112688 104527 452028

    New jar 126662 116046 124387 113319 480414

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-10

    Dennis did a more extensive test, and the numbers came out much better (1.10% degradation):

    Sum of total time Run1 Run2 Run3 Run4 SUM of Runs
    before fix 134847 138194 136270 131682 540993
    after fix 137588 132645 138014 138583 546830

    Sum of averages
    before fix 6715 6880 6788 6559 26942
    after fix 6852 6607 6874 6902 27235

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-10
    • status: open --> open-fixed
     
  • Dave Blaschke

    Dave Blaschke - 2012-03-10

    Patch sent for community review. During a 2 week period any
    exploiter may comment on the patch, request changes or turn it
    down completely (with good reason). For the time being the patch is part of the "Experimental" branch in CVS.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-14

    Patch against HEAD

     
    Attachments
  • Dave Blaschke

    Dave Blaschke - 2012-03-14
    • status: open-fixed --> pending-fixed
     
  • Dave Blaschke

    Dave Blaschke - 2012-03-14

    The community review has completed and we received no substantial criticism. Therefore the patch has been approved and merged into the "HEAD" branch. The next release will pick it up.

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-14

    Review was shortened so this patch could make 2.1.12 release, which should be included in RHEL 6.3...

     
  • Dave Blaschke

    Dave Blaschke - 2012-03-14
    • status: pending-fixed --> open-fixed
     
  • Dave Blaschke

    Dave Blaschke - 2012-03-14
    • status: open-fixed --> pending-fixed
     
  • Dave Blaschke

    Dave Blaschke - 2012-03-15
    • status: pending-fixed --> closed-fixed
     
  • Dave Blaschke

    Dave Blaschke - 2012-03-15

    The patch was picked up by release 2.1.12 and will therefore be closed.

     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks