Bug 750533 (CVE-2012-2739)

Summary: CVE-2012-2739 java: hash table collisions CPU usage DoS (oCERT-2011-003)
Product: [Other] Security Response Reporter: Jan Lieskovsky <jlieskov>
Component: vulnerabilityAssignee: Red Hat Product Security <security-response-team>
Status: NEW --- QA Contact:
Severity: medium Docs Contact:
Priority: medium    
Version: unspecifiedCC: ahughes, aph, dbhole, jpazdziora, jvanek, mjc, pahan, security-response-team, wnefal+redhatbugzilla
Target Milestone: ---Keywords: Reopened, Security
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard: impact=moderate,public=20111228,reported=20111101,source=distros,cvss2=5.0/AV:N/AC:L/Au:N/C:N/I:N/A:P,rhel-5/java-1.6.0-openjdk=wontfix,rhel-6/java-1.6.0-openjdk=wontfix,rhel-4/java-1.6.0-sun=wontfix,rhel-5/java-1.6.0-sun=wontfix,rhel-6/java-1.6.0-sun=wontfix,rhel-4/java-1.5.0-ibm=wontfix,rhel-5/java-1.5.0-ibm=wontfix,rhel-6/java-1.5.0-ibm=wontfix,rhel-4/java-1.6.0-ibm=wontfix,rhel-5/java-1.6.0-ibm=wontfix,rhel-6/java-1.6.0-ibm=wontfix,openshift-1/java-1.6.0-openjdk=wontfix
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2011-12-29 07:40:08 EST Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Bug Depends On:    
Bug Blocks: 770929, 750536    

Description Jan Lieskovsky 2011-11-01 10:13:47 EDT
Julian Wälde and Alexander Klink reported that the String.hashCode() hash function is not sufficiently collision resistant.  hashCode() value is used in the implementations of HashMap and Hashtable classes:

http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
http://docs.oracle.com/javase/6/docs/api/java/util/Hashtable.html

A specially-crafted set of keys could trigger hash function collisions, which can degrade performance of HashMap or Hashtable by changing hash table operations complexity from an expected/average O(1) to the worst case O(n).  Reporters were able to find colliding strings efficiently using equivalent substrings and meet in the middle techniques.

This problem can be used to start a denial of service attack against Java applications that use untrusted inputs as HashMap or Hashtable keys.  An example of such application is web application server (such as tomcat, see bug #750521) that may fill hash tables with data from HTTP request (such as GET or POST parameters).  A remote attack could use that to make JVM use excessive amount of CPU time by sending a POST request with large amount of parameters which hash to the same value.

This problem is similar to the issue that was previously reported for and fixed
in e.g. perl:
  http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf
Comment 2 Jan Lieskovsky 2011-11-01 10:18:44 EDT
Acknowledgements:

Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Comment 12 Tomas Hoger 2011-12-29 07:40:08 EST
Upstream does not believe this issue should be addressed in Java language itself, and rather needs to be addressed in affected applications.  28C3 slides quote following Oracle Security Team statement:

  As for Java itself, it does not seem like there is anything that would
  require a change in Java hashmap implementation.

Hence there's currently no plan to address this issue in Java JREs.  The issue is going to be addressed in application servers such as Tomcat and JBossWeb (bug #750521), and Glassfish (Oracle bug S0104869).
Comment 15 Tomas Hoger 2012-05-24 04:06:44 EDT
(In reply to comment #12)
> Upstream does not believe this issue should be addressed in Java language
> itself, and rather needs to be addressed in affected applications.  28C3
> slides quote following Oracle Security Team statement:
> 
>   As for Java itself, it does not seem like there is anything that would
>   require a change in Java hashmap implementation.
> 
> Hence there's currently no plan to address this issue in Java JREs.

It seems there is actually going to be a fix for this in Java 7 and Java 8:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-May/010238.html
Comment 16 David Jorm 2012-06-18 01:07:03 EDT
Statement:

This flaw affects various versions of Java as shipped with Red Hat products. A patch is available for Java 7 and Java 8, but not for previous versions of Java shipped with Red Hat products. Although no patch is available for previous versions of Java as shipped with Red Hat products, the impact of this flaw has been addressed in several components that utilize Java HashMap in such a way that may expose a denial of service flaw.
Comment 17 Jan Lieskovsky 2012-06-18 08:41:36 EDT
Other related reference:
http://armoredbarista.blogspot.de/2012/02/investigating-hashdos-issue.html