lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAE6fNr+MuTMK+JNyAn6y2h3XixN=fZ-GAyr+2-UcZJLuaGJ4og@mail.gmail.com> Date: Thu, 29 Dec 2011 19:59:08 +0100 From: sd <sd@...ksheep.org> To: full-disclosure@...ts.grok.org.uk Subject: Re: n.runs-SA-2011.004 - web programming languages and platforms - DoS through hash table 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/
Powered by blists - more mailing lists