An advanced DoS attack-Hash collision attack

Original link

This is the first attack method that scares me so far. It covers a wide range and is difficult to defend against, and the attack effect is immediate. A large number of websites and web interfaces are not protected against Hash collision attacks.

With the popularity of RESTful-style interfaces, programmers will use json as the data transfer method by default. The json format has less data redundancy and high compatibility. It has been widely used since it was proposed and can be said to have become a standard on the Web. No matter what language we use on the server side, after we get the data in json format, we need to do jsonDecode() to convert the json string into a json object. The object will be stored in the Hash Table by default, and the Hash Table is easily vulnerable to collision attacks. As long as I put the attack data in json, the server program will be infected when doing jsonDecode(). After being infected, the CPU will immediately surge to 100%. With a 16-core CPU, 16 requests can achieve the purpose of DoS.

All test programs are conducted under Mac Pro. For the convenience of testing, I only constructed 65536 json key-value pairs. When actually launching an attack, hundreds of thousands or even millions of data can be constructed.

A few simple Demos

I have converted the attack data to json format

1. ##Hash attack json data

2. Common json data

3. Java version Hash attack data

1. JavaScript test

//只需要一行代码就能看到效果var jsonSrc = '这里输入json数据'；

We only need to You can see the effect by entering one line of code in js. Both the normal data and the Hash attack data have 65536 lines of key-value pairs. The effect of my local test is as follows:

Through the task manager that comes with Chrome, you can see that the CPU immediately rises to 100%, and it takes nearly 1 minute to complete the execution, while ordinary data can be completed in a few milliseconds;

2. PHP test

$json = file_get_contents("https://raw.githubusercontent.com/laynefyc/php_thread_demo/master/hashNomal.json");
$startTime = microtime(true);
$arr = json_decode($json,true);
$endTime = microtime(true);
echo "Nomal:".($endTime - $startTime)."\r\n";
$json = file_get_contents("https://raw.githubusercontent.com/laynefyc/php_thread_demo/master/hash.json");
$startTime = microtime(true);
$arr = json_decode($json,true);
$endTime = microtime(true);
echo "Attack:".($endTime - $startTime)."\r\n";

In PHP, we use file_get_contents to get data remotely, and compare the running times. The difference is more than 10 seconds, and the single process of php-fpm takes up 100% of the CPU.

3. Java test

public String index(){String jsonStr = "";try
    {
        FileReader fr = new FileReader("t.log");//需要读取的文件路径BufferedReader br = new BufferedReader(fr);
        jsonStr = br.readLine();
        br.close();
        fr.close();     //关闭文件流
    }catch(IOException e)
    {
        System.out.println("指定文件不存在");//处理异常
    }

    Map14bd1badcdee783757181db757c9943f map = new HashMap14bd1badcdee783757181db757c9943f();map = JSONObject.fromObject(jsonStr);return "Hash Collision ~";
}

In Java, we do the test by reading files. Java’s Hash algorithm is slightly different from PHP and JavaScript, but they are similar. We also constructed 60,000 Rows of simple data. In the Spring boot framework, the browser initiates an access, and the result is returned after 26 seconds, during which the CPU is full.

4. Other languages ​​are still under study...

HashTable is a very common data structure. There is a special class on data structures and algorithms to talk about it, so Hash Collision is ubiquitous. Yes, the implementation of each language only has slight differences in hashing algorithm and table storage.

In order to verify that Java's Hash collision attack is also effective, I read articles related to Java HashTable throughout the Dragon Boat Festival holiday. After hard work, I finally successfully generated the attack data. The process is not simple, and it also verifies an idea - all high-level things are finally decomposed into basic data structure knowledge.

How to attack

A few years ago, the PHP version was still 5.2. We could put all the Hash Keys in the Body of the POST request, such as:

Post Data: k1=0&k2=0&k3=0...k999998=0&k999999=0

After the server gets the data, it will store all parameters in the Hash Table ($_POST), the attack can be easily implemented in this way. But now this method does not work, because we can easily limit the number and size of HTTP request parameters at the Nginx layer and PHP layer. PHP only allows 1000 parameters by default, which has no impact on the server at all.

Now is 2017, json format and RESTful style interface have become very popular. While bringing us convenient coding, it also provides a new way for Hash Collision Dos. Now many RESTful style interfaces are as follows:

Data: {"action":"create-account","data":""}

As shown in the above interface, we directly put the attack data into the data parameter. After receiving the data, the server will definitely do jsonDecode(), which easily achieves the purpose of the attack.

How to defend

To defend against Hash Collision Dos attacks, there are already many mature solutions in the industry, but they all recommend changing the language or rewriting the HashTable. Here we only talk about the current json format parsing issues. First, we need to add permission verification to reject illegal users as much as possible before jsonDecode(). Secondly, perform data size and parameter whitelist verification before jsonDecode(). If the cost of transformation and maintenance of old projects is high, it is recommended to rewrite the jsonDecode() method yourself

The above is the detailed content of An advanced DoS attack-Hash collision attack. For more information, please follow other related articles on the PHP Chinese website!