logo
DATABASE RESOURCES PRICING ABOUT US

Hash table implementations vulnerable to algorithmic complexity attacks

Description

### Overview Some programming language implementations do not sufficiently randomize their hash functions or provide means to limit key collision attacks, which can be leveraged by an unauthenticated attacker to cause a denial-of-service (DoS) condition. ### Description Many applications, including common web framework implementations, use hash tables to map key values to associated entries. If the hash table contains entries for different keys that map to the same hash value, a hash collision occurs and additional processing is required to determine which entry is appropriate for the key. If an attacker can generate many requests containing colliding key values, an application performing the hash table lookup may enter a denial of service condition. Hash collision denial-of-service attacks were first [detailed](<http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf>) in 2003, but [recent research](<http://www.nruns.com/_downloads/advisory28122011.pdf>) details how these attacks apply to modern language hash table implementations. --- ### Impact An application can be forced into a denial-of-service condition. In the case of some web application servers, specially-crafted POST form data may result in a denial-of-service. --- ### Solution **Apply an update** Please review the Vendor Information section of this document for vendor-specific patch and workaround details. --- **Limit CPU time** Limiting the processing time for a single request can help minimize the impact of malicious requests. **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. --- ### Vendor Information 903934 Filter by status: All Affected Not Affected Unknown Filter by content: __ Additional information available __ Sort by: Status Alphabetical Expand all **Javascript is disabled. Click here to view vendors.** ### Apache Tomcat __ Affected Updated: December 28, 2011 ### Status Affected ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information According to the n.runs AG advisory: "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." ### Vendor References * <http://tomcat.apache.org/tomcat-7.0-doc/changelog.html> ### Microsoft Corporation __ Affected Notified: November 01, 2011 Updated: December 29, 2011 ### Status Affected ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information Microsoft has released an update to the .NET Framework with [Microsoft Security Bulletin MS11-100](<http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx>), which addresses this issue. ### Vendor References * <http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx> * <http://technet.microsoft.com/en-us/security/advisory/2659883> * <http://blogs.technet.com/b/srd/archive/2011/12/27/more-information-about-the-december-2011-asp-net-vulnerability.aspx> ### Oracle Corporation __ Affected Notified: November 01, 2011 Updated: February 15, 2016 ### Status Affected ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information We are not aware of further vendor information regarding this vulnerability. ### Addendum New information regarding this vulnerability in Java 8 was provided in Februrary 2016, which was sent to Oracle for review. If you have feedback, comments, or additional information about this vulnerability, please send us [email](<mailto:cert@cert.org?Subject=VU%23903934 Feedback>). ### Ruby __ Affected Notified: November 01, 2011 Updated: December 28, 2011 ### Status Affected ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information According to the n.runs AG advisory: "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)." ### Vendor References * <http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/391606> ### The PHP Group __ Affected Updated: December 28, 2011 ### Status Affected ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information According to the n.runs AG advisory: "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." From the Workarounds section: "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." PHP 5.4.0 RC4 has been released which adds a max_input_vars directive to help mitigate hash collision attacks. Please note that this is a release candidate, not a stable release. ### Vendor References * <http://www.php.net/archive/2011.php#id2011-12-25-1> ### Adobe Unknown Notified: November 01, 2011 Updated: November 01, 2011 ### Status Unknown ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information We are not aware of further vendor information regarding this vulnerability. ### IBM Corporation Unknown Notified: November 01, 2011 Updated: November 01, 2011 ### Status Unknown ### Vendor Statement We have not received a statement from the vendor. ### Vendor Information We are not aware of further vendor information regarding this vulnerability. ### CVSS Metrics Group | Score | Vector ---|---|--- Base | 0 | AV:--/AC:--/Au:--/C:--/I:--/A:-- Temporal | 0 | E:ND/RL:ND/RC:ND Environmental | 0 | CDP:ND/TD:ND/CR:ND/IR:ND/AR:ND ### References * <http://www.ocert.org/advisories/ocert-2011-003.html> * <http://www.nruns.com/_downloads/advisory28122011.pdf> * <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf> * <http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx> ### Acknowledgements Thanks to Alexander Klink and Julian Wälde for reporting these vulnerabilities. This document was written by Jared Allar and David Warren. ### Other Information **CVE IDs:** | [CVE-2011-4815](<http://web.nvd.nist.gov/vuln/detail/CVE-2011-4815>), [CVE-2011-3414](<http://web.nvd.nist.gov/vuln/detail/CVE-2011-3414>), [CVE-2011-4838](<http://web.nvd.nist.gov/vuln/detail/CVE-2011-4838>), [CVE-2011-4885](<http://web.nvd.nist.gov/vuln/detail/CVE-2011-4885>) ---|--- **Severity Metric:** | 10.80 **Date Public:** | 2011-12-28 **Date First Published:** | 2011-12-28 **Date Last Updated: ** | 2016-02-15 20:05 UTC **Document Revision: ** | 41


Related