php哈希沖突攻擊解析

一段攻擊代碼

<?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, ' 個(gè)惡意的元素需要 ', $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, ' 個(gè)普通元素需要 ', $endTime - $startTime, ' 秒', "\n";

插入結(jié)果

php5(5.2)

插入 65536 個(gè)惡意的元素需要 79.778307914734 秒
插入 65536 個(gè)普通元素需要 0.028948068618774 秒

php7

插入 65536 個(gè)惡意的元素需要 9.2177460193634 秒
插入 65536 個(gè)普通元素需要 0.004227876663208 秒

php 數(shù)組的實(shí)現(xiàn)

php 中的數(shù)組是 php 中非常好用的一個(gè)數(shù)據(jù)結(jié)構(gòu)，有了這個(gè)數(shù)據(jù)結(jié)構(gòu)的加持 php 的開發(fā)效率才能如此之高。
但是我們知道世界上并沒有完美的事物，php 的數(shù)組雖然給我們帶來的簡(jiǎn)單易用的一些特性，但是也會(huì)給我們帶來一些隱患。
哈希表是我們非常常見的一個(gè)數(shù)據(jù)結(jié)構(gòu)，php 的數(shù)組就是通過哈希表來實(shí)現(xiàn)的。
php 的哈希表解決沖突采用的是拉鏈法，沖突的元素通過加入相應(yīng)hash槽的鏈表來解決。

php 經(jīng)歷了很多的版本，我們常用熟悉的版本有5.3、5.6、7.0 這幾個(gè)版本。
其中 php5 版本的 hashtable 的實(shí)現(xiàn)與 php7 的有所不同。

php5

//hashTable的數(shù)據(jù)結(jié)構(gòu)
typedef struct _hashtable {
    uint nTableSize;// hashtable 的大小
    uint nTableMask;//這個(gè)和 ntableSize 是對(duì)應(yīng)的關(guān)系，為 nTableSize 的負(fù)數(shù)
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;   /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets; // 指向第一個(gè)桶鏈表
    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長(zhǎng)度
   void *pData;        //指向bucket中保存的數(shù)據(jù)的指針
   void *pDataPtr;    //指針數(shù)據(jù)
   struct bucket *pListNext;    //指向hashtable桶列中下一個(gè)元素
   struct bucket *pListLast;    //指向hashtable桶列前一個(gè)元素
   struct bucket *pNext;        //指向具有同一個(gè)hash index的桶列的后一個(gè)元素
   struct bucket *pLast;        //指向具有同一個(gè)hash index的桶列的前一個(gè)元素
   const char *arKey;        //必須是最后一個(gè)成員，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)前桶的第一個(gè)數(shù)據(jù)
    uint32_t          nNumUsed;   //已用的Bucket的數(shù)量（包含的是那些被刪除的或者是無效的bucket）
    uint32_t          nNumOfElements;//有效的bucket的數(shù)量
    uint32_t          nTableSize;//可以容納的bucket的數(shù)量
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;//用來自動(dòng)確定php數(shù)組的索引
    dtor_func_t       pDestructor;//自動(dòng)清理無用bucket的函數(shù)
};

php7 的 Bucket 實(shí)現(xiàn)就簡(jiǎ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;

這個(gè)是 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]    |
 *                 +=============================+
 */
bucket1.png

內(nèi)部沖突的解決

那么 php 的內(nèi)部沖突 php 是怎么解決的那？
首先涉及到的一個(gè)常量是 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; //這里對(duì) 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 是無符號(hào)的int類型，吧 -2 轉(zhuǎn)換成無符號(hào)就是將-2原碼區(qū)反加一

php 添加數(shù)據(jù)到hashTable的代碼
主要關(guān)注的變量 nIndex h u2.next

  • nIndex:哈希槽
  • h:當(dāng)前的數(shù)組的key
  • u2.next:沖突鏈表前一個(gè)bucket的位置記錄（Bucket是順序插入的，php7性能提高就是因?yàn)樽隽薶ashTable的數(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;  //這里就是計(jì)算的方法  nTableMask初始值11111111111111111111111111111000
    Z_NEXT(p->val) = HT_HASH(ht, nIndex); // 這里將上一個(gè)bucket的u2.next的值放到下一個(gè)Bucket的u2.next
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

    return &p->val;
...

我們知道了hash的計(jì)算方式了，就可以分析上面的攻擊代碼了。
我們?nèi)〕鰜韼讉€(gè)數(shù)據(jù)進(jìn)行調(diào)試測(cè)試，新建一個(gè) php 文件使用php -f 運(yùn)行文件

$arr1 = [
    0 => '!',//4294967288
    65536 => '@',//4294967288
    131072 => '#',
    196608 => '$',
    262144 => '%',
];

下面的nIndex的變化

65536.png
196608.png
1311072.png
262144.png

我們可以看到nIndex幾次都沒有變化,這說明我們的Bucket都是放到同一個(gè)hash槽中，我們?cè)谕ㄟ^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}

}

為什么第一個(gè)是4294967295 因?yàn)檫@個(gè)是第一個(gè)引用的hash槽的位置

butcket2.png

為何會(huì)有攻擊效果

如果所有的元素都進(jìn)了同一個(gè)hash槽，那么我們的Hashtable查詢和插入的時(shí)間復(fù)雜度就會(huì)從 O(1) => O(n)
當(dāng)然 php7 有所改善，如果在php5中的插入方式會(huì)慢很多。

hash沖突

有效預(yù)防

  1. 在 php5.3 以上的版本中，post 參數(shù)的數(shù)量存在最大的限制 max_input_vars => 1000

  2. 在web服務(wù)器層面進(jìn)行處理，如通過限制請(qǐng)求 body 大小和參數(shù)的數(shù)量等，這個(gè)也是目前使用最多的解決方案

其實(shí)以上的兩種解決方案并不能解決問題，因?yàn)橹皇菃渭兊脑趨?shù)的數(shù)量上進(jìn)行限制了，但是入股請(qǐng)求的數(shù)據(jù)中包含 json 數(shù)據(jù)，但其中的數(shù)據(jù)就是碰撞的 array。理論上，只要 php 代碼某處構(gòu)造 array 的數(shù)據(jù)依賴于外部輸入，則都可能造成這個(gè)問題，因此徹底的解決方案是更改 Zend 底層的 HashTable 實(shí)現(xiàn)

  1. 限制每個(gè)桶鏈表的最長(zhǎng)長(zhǎng)度

  2. 使用其他數(shù)據(jù)結(jié)構(gòu)如紅黑樹取代鏈表組織碰撞哈希（并不解決哈希碰撞，只是減輕攻擊影響，將N個(gè)數(shù)據(jù)的操作時(shí)間從 O(N^2) 降至 O(NlogN) ，代價(jià)是普通情況下接近 O(1) 的操作均變?yōu)?O(logN)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 按圖索驥。PHP中使用最為頻繁的數(shù)據(jù)類型非字符串和數(shù)組莫屬，PHP比較容易上手也得益于非常靈活的數(shù)組類型。 在開始...
    拉風(fēng)的老衲閱讀 868評(píng)論 0贊 3
  • 一. PHP數(shù)組特點(diǎn)介紹 php數(shù)組可謂是php的核心，其key=>value的存儲(chǔ)結(jié)構(gòu)，讓我們處理數(shù)據(jù)可以...
    OamMot閱讀 5,294評(píng)論 1贊 20
  • 朋友圈分類 1.家人與親戚 2.同事 3.孩子老師、小朋友同學(xué)家長(zhǎng) 4.同學(xué) 5同頻的學(xué)習(xí)伙伴
    夸寶兒閱讀 177評(píng)論 0贊 0
  • 古鎮(zhèn)上有兩種聲音，一樣的寂寥：白天是算命鑼，夜里是梆子……覃某每次想起那些美妙的古鎮(zhèn)，青青石板路，悠悠古城垣。輕撫...
    旅行作家好嘢閱讀 3,303評(píng)論 39贊 92
  • -1- 美玲在廚房里忙得熱火朝天，鍋里燉得牛肉香氣四溢，炸好得金黃色的丸子整齊地?cái)[在帶花邊的瓷盤子里；她的額頭滲出...
    瑞雪嚨翔閱讀 833評(píng)論 8贊 8

友情鏈接更多精彩內(nèi)容