Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Java Hash Collision Vulnerability

 
Preet Prasannan.
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Preet Prasannan.
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just to add, at all trials, I tried using the default implementation of hashcode.
 
Hebert Coelho
Ranch Hand
Posts: 754
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.

 
Paul Clapham
Sheriff
Posts: 21107
32
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic