aspose file tools*
The moose likes Security and the fly likes Java Hash Collision Vulnerability Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Engineering » Security
Bookmark "Java Hash Collision Vulnerability" Watch "Java Hash Collision Vulnerability" New topic
Author

Java Hash Collision Vulnerability

Preet Prasannan.
Ranch Hand

Joined: Feb 09, 2009
Posts: 64
Hi All,

I recently came across the hash collision vulnerability in multiple programming languages including Java.
As I could understand that this happens when two or more objects have the same hashcode.
But I tried generating some strings but was unsuccessful in getting same hashcodes. Hashcodes returned were always unique.

Can anyone spray some light as to how it can be possible to generate objects with the same hashcode?
It got me particularly interested as this issue creates a serious vulnerability with DOS attack on servers.

Regards
Preet


"The more I learn,the more,I get to know, is left to learn."
Preet Prasannan.
Ranch Hand

Joined: Feb 09, 2009
Posts: 64
Just to add, at all trials, I tried using the default implementation of hashcode.
Hebert Coelho
Ranch Hand

Joined: Jul 14, 2010
Posts: 754


By this sample you got the same hashCode all the time.

How are you generating your hashCode? A class may have the same hashCode but is not equals.


[uaiHebert.com] [Full WebApplication JSF EJB JPA JAAS with source code to download] One Table Per SubClass [Web/JSF]
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18986
    
    8

You didn't try very hard, then. The number of possible Strings is about 2 ^ ( 2 ^ 36), but there are only about 2^32 possible hashcodes. That means that for each possible hashcode there are about 2 ^ (2 ^36 - 32) different Strings with that hashcode. That's a number with about 20 billion digits. Not a number about 20 billion, but a number with that many digits.

So that's a lot. A straightforward brute-force piece of code should be able to find some. Any good hacker could do that. Whether they would actually do it is another question. It seems to me that to put enough entries into one bucket of a hash table to cause it to start using significant CPU would require sending enough requests to constitute a DOS just from having to process all those requests. Although the hacker could spread them out so that after a week or a month the machine would start to slow down. Besides, the hacker would have to know which parts of the request would be hashed by the server. That would probably require inside knowledge, although of course it's perfectly possible for hackers to acquire such knowledge. It just seems like an unlikely attack vector to me... although I am no security expert.
Preet Prasannan.
Ranch Hand

Joined: Feb 09, 2009
Posts: 64
Editing as I just saw the previous post which gave me a way to find the solution but created some more doubts that I would first look at, code and if not solvable, will ask.
Preet Prasannan.
Ranch Hand

Joined: Feb 09, 2009
Posts: 64
Thanks a lot for the answer Hebert and Paul.
Will dig into it a bit more and come up with questions if any I come across.
Ben Simmons
Greenhorn

Joined: Jan 03, 2012
Posts: 1
@Paul hahaha love it

As for this part:

Besides, the hacker would have to know which parts of the request would be hashed by the server.


At least four major application servers (Tomcat, Geronimo, Jetty, Glassfish) put the HTTP request parameters into a Hashtable or a HashMap. So... no mystery there. Expect to see this weaponized in the next few days.

Here's the original paper that was released on 12/28/2011:
http://www.nruns.com/_downloads/advisory28122011.pdf

Author claims:

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Java Hash Collision Vulnerability