Date: Thu, 29 Dec 2011 13:24:25 -0600
From: adam <adam@...sy.net>
To: sd <sd@...ksheep.org>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: n.runs-SA-2011.004 - web programming
 languages and platforms - DoS through hash table

In any case, the concept is pretty interesting. It's not a vector that most
people would think of when securing their applications/servers. At least,
most people I've come in contact with, anyway.

On Thu, Dec 29, 2011 at 12:59 PM, sd <sd@...ksheep.org> wrote:

> This is practically limited to java, 32bit python and ruby1.8.
> PHP-suhosin killed this issue long time ago.
>
> 2011/12/28  <security@...ns.com>:
> >
> >
> > n.runs AG
> > http://www.nruns.com/                              security(at)nruns.com
> > n.runs-SA-2011.004                                           28-Dec-2011
> > ________________________________________________________________________
> > Vendors: PHP, http://www.php.net
> >                    Oracle, http://www.oracle.com
> >                    Microsoft, http://www.microsoft.com
> >                    Python, http://www.python.org
> >                    Ruby, http://www.ruby.org
> >                    Google, http://www.google.com
> > Affected Products: PHP 4 and 5
> >                    Java
> >                    Apache Tomcat
> >                    Apache Geronimo
> >                    Jetty
> >                    Oracle Glassfish
> >                    ASP.NET
> >                    Python
> >                    Plone
> >                    CRuby 1.8, JRuby, Rubinius
> >                    v8
> > Vulnerability:      Denial of Service through hash table
> >                    multi-collisions
> > Tracking IDs:       oCERT-2011-003
> >                    CERT VU#903934
> > ________________________________________________________________________
> > Vendor communication:
> > 2011/11/01 Coordinated notification to PHP, Oracle, Python, Ruby, Google
> >           via oCERT
> > 2011/11/29 Coordinated notification to Microsoft via CERT
> >
> > Various communication with the vendors for clarifications, distribution
> > of PoC code, discussion of fixes, etc.
> >
> ___________________________________________________________________________
> > Overview:
> >
> > Hash tables are a commonly used data structure in most programming
> > languages. Web application servers or platforms commonly parse
> > attacker-controlled POST form data into hash tables automatically, so
> > that they can be accessed by application developers.
> >
> > If the language does not provide a randomized hash function or the
> > application server does not recognize attacks using multi-collisions, an
> > attacker can degenerate the hash table by sending lots of colliding
> > keys. The algorithmic complexity of inserting n elements into the table
> > then goes to O(n**2), making it possible to exhaust hours of CPU time
> > using a single HTTP request.
> >
> > This issue has been known since at least 2003 and has influenced Perl
> > and CRuby 1.9 to change their hash functions to include randomization.
> >
> > We show 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.
> >
> > Description:
> >
> > = Theory =
> >
> > Most hash functions used in hash table implementations can be broken
> > faster than by using brute-force techniques (which is feasible for hash
> > functions with 32 bit output, but very expensive for 64 bit functions)
> > by using one of two "tricks": equivalent substrings or a
> > meet-in-the-middle attack.
> >
> > == Equivalent substrings ==
> >
> > Some hash functions have the property that if two strings collide, e.g.
> > hash('string1') = hash('string2'), then hashes having this substring at
> > the same position collide as well, e.g. hash('prefixstring1postfix') =
> > hash('prefixstring2postfix'). If for example 'Ez' and 'FY' collide under
> > a hash function with this property, then 'EzEz', 'EzFY', 'FYEz', 'FYFY'
> > collide as well. An observing reader may notice that this is very
> > similar to binary counting from zero to four. Using this knowledge, an
> > attacker can construct arbitrary numbers of collisions (2^n for
> > 2*n-sized strings in this example).
> >
> > == Meet-in-the-middle attack ==
> >
> > If equivalent substrings are not present in a given hash function, then
> > brute-force seems to be the only solution. The obvious way to best use
> > brute-force would be to choose a target value and hash random
> > (fixed-size) strings and store those which hash to the target value. For
> > a non-biased hash function with 32 bit output length, the probability of
> > hitting a target in this way is 1/(2^32).
> >
> > A meet-in-the-middle attack now tries to hit more than one target at a
> > time. If the hash function can be inverted and the internal state of the
> > hash function has the same size as the output, one can split the string
> > into two parts, a prefix (of size n) and a postfix (of size m). One can
> > now iterate over all possible m-sized postfix strings and calculate the
> > intermediate value under which the hash function maps to a certain
> > target. If one stores these strings and corresponding intermediate value
> > in a lookup table, one can now generate random n-sized prefix strings
> > and see if they map to one of the intermediate values in the lookup
> > table. If this is the case, the complete string will map to the target
> > value.
> >
> > Splitting in the middle reduces the complexity of this attack by the
> > square root, which gives us the probability of 1/(2^16) for a collision,
> > thus enabling an attacker to generate multi-collisions much faster.
> >
> > The hash functions we looked at which were vulnerable to an equivalent
> > substring attack were all vulnerable to a meet-in-the-middle attack as
> > well. In this case, the meet-in-the-middle attack provides more
> > collisions for strings of a fixed size than the equivalent substring
> > attack.
> >
> > = The real world =
> >
> > The different language use different hash functions which suffer from
> > different problems. They also differ in how they use hash tables in
> > storing POST form data.
> >
> > == PHP 5 ==
> >
> > PHP 5 uses the DJBX33A (Dan Bernstein's times 33, addition) hash
> > function and parses POST form data into the $_POST hash table. Because
> > of the structure of the hash function, it is vulnerable to an equivalent
> > substring attack.
> >
> > 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).
> >
> > On an i7 core, the 60 seconds take a string of multi-collisions of about
> > 500k. 30 seconds of CPU time can be generated using a string of about
> > 300k. This means that an attacker needs about 70-100kbit/s to keep one
> > i7 core constantly busy. An attacker with a Gigabit connection can keep
> > about 10.000 i7 cores busy.
> >
> > == ASP.NET ==
> >
> > ASP.NET uses the Request.Form object to provide POST data to a web
> > application developer. This object is of class NameValueCollection. This
> > uses a different hash function than the standard .NET one, namely
> > CaseInsensitiveHashProvider.getHashCode(). This is the DJBX33X (Dan
> > Bernstein's times 33, XOR) hash function on the uppercase version of the
> > key, which is breakable using a meet-in-the-middle attack.
> >
> > CPU time is limited by the IIS webserver to a value of typically 90
> > seconds. This allows an attacker with about 30kbit/s to keep one Core2
> > core constantly busy. An attacker with a Gigabit connection can keep
> > about 30.000 Core2 cores busy.
> >
> > == Java ==
> >
> > Java offers the HashMap and Hashtable classes, which use the
> > String.hashCode() hash function. It is very similar to DJBX33A (instead
> > of 33, it uses the multiplication constant 31 and instead of the start
> > value 5381 it uses 0). Thus it is also vulnerable to an equivalent
> > substring attack. When hashing a string, Java also caches the hash value
> > in the hash attribute, but only if the result is different from zero.
> > Thus, the target value zero is particularly interesting for an attacker
> > as it prevents caching and forces re-hashing.
> >
> > Different web application parse the POST data differently, but the ones
> > tested (Tomcat, Geronima, Jetty, Glassfish) all put the POST form data
> > into either a Hashtable or HashMap object. The maximal POST sizes also
> > differ from server to server, with 2 MB being the most common.
> >
> > A Tomcat 6.0.32 server parses a 2 MB string of colliding keys in about
> > 44 minutes of i7 CPU time, so an attacker with about 6 kbit/s can keep
> > one i7 core constantly busy. If the attacker has a Gigabit connection,
> > he can keep about 100.000 i7 cores busy.
> >
> > == Python ==
> >
> > Python uses a hash function which is very similar to DJBX33X, which can
> > be broken using a meet-in-the-middle attack. It operates on register
> > size and is thus different for 64 and 32 bit machines. While generating
> > multi-collisions efficiently is also possible for the 64 bit version of
> > the function, the resulting colliding strings are too large to be
> > relevant for anything more than an academic attack.
> >
> > Plone as the most prominent Python web framework accepts 1 MB of POST
> > data, which it parses in about 7 minutes of CPU time in the worst case.
> > This gives an attacker with about 20 kbit/s the possibility to keep one
> > Core Duo core constantly busy. If the attacker is in the position to
> > have a Gigabit line available, he can keep about 50.000 Core Duo cores
> > busy.
> >
> > == Ruby ==
> >
> > The Ruby language consists of several implementations which do not share
> > the same hash functions. It also differs in versions (1.8, 1.9), which -
> > depending on the implementation - also do not necessarily share the same
> > hash function.
> >
> > The hash function of CRuby 1.9 has been using randomization since 2008
> > (a result of the algorithmic complexity attacks disclosed in 2003). The
> > CRuby 1.8 function is very similar to DJBX33A, but the large
> > multiplication constant of 65599 prevents an effective equivalent
> > substring attack. The hash function can be easily broken using a meet-
> > in-the-middle attack, though. JRuby uses the CRuby 1.8 hash function for
> > both 1.8 and 1.9. Rubinius uses a different hash function but also does
> > not randomize it.
> >
> > A typical POST size limit in Ruby frameworks is 2 MB, which takes about
> > 6 hours of i7 CPU time to parse. Thus, an attacker with a single 850
> > bits/s line can keep one i7 core busy. The other way around, an attacker
> > with a Gigabit connection can keep about 1.000.000 (one million!) i7
> > cores busy.
> >
> > == v8 ==
> >
> > Google's Javascript implementation v8 uses a hash function which looks
> > different from the ones seen before, but can be broken using a meet-in-
> > the-middle attack, too.
> >
> > Node.js uses v8 to run Javascript-based web applications. The
> > querystring module parses POST data into a hash table structure.
> >
> > As node.js does not limit the POST size by default (we assume this would
> > typically be the job of a framework), no effectiveness/efficiency
> > measurements were performed.
> >
> > Impact:
> >
> > Any website running one of the above technologies which provides the
> > option to perform a POST request is vulnerable to very effective DoS
> > attacks.
> >
> > As the attack is just a POST request, it could also be triggered from
> > within a (third-party) website. This means that a cross-site-scripting
> > vulnerability on a popular website could lead to a very effective DDoS
> > attack (not necessarily against the same website).
> >
> > 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 "shutdown 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.
> >
> > ________________________________________________________________________
> > Credits:
> > Alexander Klink, n.runs AG
> > Julian Wälde, Technische Universität Darmstadt
> >
> > The original theory behind this attack vector is described in the 2003
> > Usenix Security paper "Denial of Service via Algorithmic Complexity
> > Attacks" by Scott A. Crosby and Dan S. Wallach, Rice University
> > ________________________________________________________________________
> > References:
> > This advisory and upcoming advisories:
> > http://www.nruns.com/security_advisory.php
> > ________________________________________________________________________
> > About n.runs:
> > n.runs AG is a vendor-independent consulting company specialising in the
> > areas of: IT Infrastructure, IT Security and IT Business Consulting.
> >
> > Copyright Notice:
> > Unaltered electronic reproduction of this advisory is permitted. For all
> > other reproduction or publication, in printing or otherwise, contact
> > security@...ns.com for permission. Use of the advisory constitutes
> > acceptance for use in an "as is" condition. All warranties are excluded.
> > In no event shall n.runs be liable for any damages whatsoever including
> > direct, indirect, incidental, consequential, loss of business profits or
> > special damages, even if n.runs has been advised of the possibility of
> > such damages.
> > Copyright 2011 n.runs AG. All rights reserved. Terms of use apply.
> >
> >
> >
> >
> > _______________________________________________
> > Full-Disclosure - We believe in it.
> > Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> > Hosted and sponsored by Secunia - http://secunia.com/
>
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/
>

Content of type "text/html" skipped

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

Powered by blists - more mailing lists