近哈希表碰撞攻擊（Hashtable collisions as DOS attack）的話題不斷被提起，各種語言紛紛中招。本文結合PHP內核源碼，聊一聊這種攻擊的原理及實現。

哈希表碰撞攻擊的基本原理

哈希表是一種查找效率極高的數據結構，很多語言都在內部實現了哈希表。PHP中的哈希表是一種極為重要的數據結構，不但用于表示Array數據類型，還在Zend虛擬機內部用于存儲上下文環境信息（執行上下文的變量及函數均使用哈希表結構存儲）。

理想情況下哈希表插入和查找操作的時間復雜度均為O(1)，任何一個數據項可以在一個與哈希表長度無關的時間內計算出一個哈希值（key），然后在常量時間內定位到一個桶（術語bucket，表示哈希表中的一個位置）。當然這是理想情況下，因為任何哈希表的長度都是有限的，所以一定存在不同的數據項具有相同哈希值的情況，此時不同數據項被定為到同一個桶，稱為碰撞（collision）。哈希表的實現需要解決碰撞問題，碰撞解決大體有兩種思路，第一種是根據某種原則將被碰撞數據定為到其它桶，例如線性探測——如果數據在插入時發生了碰撞，則順序查找這個桶后面的桶，將其放入第一個沒有被使用的桶；第二種策略是每個桶不是一個只能容納單個數據項的位置，而是一個可容納多個數據的數據結構（例如鏈表或紅黑樹），所有碰撞的數據以某種數據結構的形式組織起來。

不論使用了哪種碰撞解決策略，都導致插入和查找操作的時間復雜度不再是O(1)。以查找為例，不能通過key定位到桶就結束，必須還要比較原始key（即未做哈希之前的key）是否相等，如果不相等，則要使用與插入相同的算法繼續查找，直到找到匹配的值或確認數據不在哈希表中。

PHP是使用單鏈表存儲碰撞的數據，因此實際上PHP哈希表的平均查找復雜度為O(L)，其中L為桶鏈表的平均長度；而最壞復雜度為O(N)，此時所有數據全部碰撞，哈希表退化成單鏈表。下圖PHP中正常哈希表和退化哈希表的示意圖。

哈希表碰撞攻擊就是通過精心構造數據，使得所有數據全部碰撞，人為將哈希表變成一個退化的單鏈表，此時哈希表各種操作的時間均提升了一個數量級，因此會消耗大量CPU資源，導致系統無法快速響應請求，從而達到拒絕服務攻擊（DoS）的目的。

可以看到，進行哈希碰撞攻擊的前提是哈希算法特別容易找出碰撞，如果是MD5或者SHA1那基本就沒戲了，幸運的是（也可以說不幸的是）大多數編程語言使用的哈希算法都十分簡單（這是為了效率考慮），因此可以不費吹灰之力之力構造出攻擊數據。下一節將通過分析Zend相關內核代碼，找出攻擊哈希表碰撞攻擊PHP的方法。

Zend哈希表的內部實現

數據結構

PHP中使用一個叫Backet的結構體表示桶，同一哈希值的所有桶被組織為一個單鏈表。哈希表使用HashTable結構體表示。相關源碼在zend/Zend_hash.h下：

typedef struct bucket {

ulong h; /* Used for numeric indexing */

uint nKeyLength;

void *pData;

void *pDataPtr;

struct bucket *pListNext;

struct bucket *pListLast;

struct bucket *pNext;

struct bucket *pLast;

char arKey[1]; /* Must be last element */

} Bucket;

typedef struct _hashtable {

uint nTableSize;

uint nTableMask;

uint nNumOfElements;

ulong nNextFreeElement;

Bucket *pInternalPointer; /* Used for element traversal */

Bucket *pListHead;

Bucket *pListTail;

Bucket **arBuckets;

dtor_func_t pDestructor;

zend_bool persistent;

unsigned char nApplyCount;

zend_bool bApplyProtection;

#if ZEND_DEBUG

int inconsistent;

#endif

} HashTable;

字段名很清楚的表明其用途，因此不做過多解釋。重點明確下面幾個字段：Bucket中的“h”用于存儲原始key；HashTable中的nTableMask是一個掩碼，一般被設為nTableSize - 1，與哈希算法有密切關系，后面討論哈希算法時會詳述；arBuckets指向一個指針數組，其中每個元素是一個指向Bucket鏈表的頭指針。

哈希算法

PHP哈希表最小容量是8（2^3），最大容量是0x80000000（2^31），并向2的整數次冪圓整（即長度會自動擴展為2的整數次冪，如13個元素的哈希表長度為16；100個元素的哈希表長度為128）。nTableMask被初始化為哈希表長度（圓整后）減1。具體代碼在zend/Zend_hash.c的_zend_hash_init函數中，這里截取與本文相關的部分并加上少量注釋。

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)

{

uint i = 3;

Bucket **tmp;

SET_INCONSISTENT(HT_OK);

//長度向2的整數次冪圓整

if (nSize >= 0x80000000) {

/* prevent overflow */

ht->nTableSize = 0x80000000;

} else {

while ((1U << i) < nSize) {

i++;

}

ht->nTableSize = 1 << i;

}

ht->nTableMask = ht->nTableSize - 1;

/*此處省略若干代碼…*/

return SUCCESS;

}

值得一提的是PHP向2的整數次冪取圓整方法非常巧妙，可以背下來在需要的時候使用。

Zend HashTable的哈希算法異常簡單：

hash(key)=key & nTableMask

即簡單將數據的原始key與HashTable的nTableMask進行按位與即可。

如果原始key為字符串，則首先使用Times33算法將字符串轉為整形再與nTableMask按位與。

hash(strkey)=time33(strkey) & nTableMask

下面是Zend源碼中查找哈希表的代碼：

ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)

{

uint nIndex;

Bucket *p;

IS_CONSISTENT(ht);

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

while (p != NULL) {

if ((p->h == h) && (p->nKeyLength == 0)) {

*pData = p->pData;

return SUCCESS;

}

p = p->pNext;

}

return FAILURE;

}

ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)

{

ulong h;

uint nIndex;

Bucket *p;

IS_CONSISTENT(ht);

h = zend_inline_hash_func(arKey, nKeyLength);

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

while (p != NULL) {

if ((p->h == h) && (p->nKeyLength == nKeyLength)) {

if (!memcmp(p->arKey, arKey, nKeyLength)) {

*pData = p->pData;

return SUCCESS;

}

}

p = p->pNext;

}

return FAILURE;

}

其中zend_hash_index_find用于查找整數key的情況，zend_hash_find用于查找字符串key。邏輯基本一致，只是字符串key會通過zend_inline_hash_func轉為整數key，zend_inline_hash_func封裝了times33算法，具體代碼就不貼出了。

攻擊

基本攻擊

知道了PHP內部哈希表的算法，就可以利用其原理構造用于攻擊的數據。一種最簡單的方法是利用掩碼規律制造碰撞。上文提到Zend HashTable的長度nTableSize會被圓整為2的整數次冪，假設我們構造一個2^16的哈希表，則nTableSize的二進制表示為：1 0000 0000 0000 0000，而nTableMask = nTableSize – 1為：0 1111 1111 1111 1111。接下來，可以以0為初始值，以2^16為步長，制造足夠多的數據，可以得到如下推測：

0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

……

概況來說只要保證后16位均為0，則與掩碼位于后得到的哈希值全部碰撞在位置0。

下面是利用這個原理寫的一段攻擊代碼：

<?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 $endTime - $startTime, ' seconds', "\n";

這段代碼在我的VPS上（單CPU，512M內存）上用了近88秒才完成，并且在此期間CPU資源幾乎被用盡：

而普通的同樣大小的哈希表插入僅用時0.036秒：

<?php

$size = pow(2, 16);

$startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $size; $key += 1) {

$array[$key] = 0;

}

$endTime = microtime(true);

echo $endTime - $startTime, ' seconds', "\n";

可以證明第二段代碼插入N個元素的時間在O(N)水平，而第一段攻擊代碼則需O(N^2)的時間去插入N個元素。

POST攻擊

當然，一般情況下很難遇到攻擊者可以直接修改PHP代碼的情況，但是攻擊者仍可以通過一些方法間接構造哈希表來進行攻擊。例如PHP會將接收到的HTTP POST請求中的數據構造為$_POST，而這是一個Array，內部就是通過Zend HashTable表示，因此攻擊者只要構造一個含有大量碰撞key的post請求，就可以達到攻擊的目的。具體做法不再演示。

防護

POST攻擊的防護

針對POST方式的哈希碰撞攻擊，目前PHP的防護措施是控制POST數據的數量。在>=PHP5.3.9的版本中增加了一個配置項max_input_vars，用于標識一次http請求最大接收的參數個數，默認為1000。因此PHP5.3.x的用戶可以通過升級至5.3.9來避免哈希碰撞攻擊。5.2.x的用戶可以使用這個patch：http://www.laruence.com/2011/12/30/2440.html。

另外的防護方法是在Web服務器層面進行處理，例如限制http請求body的大小和參數的數量等，這個是現在用的最多的臨時處理方案。具體做法與不同Web服務器相關，不再詳述。

其它防護

上面的防護方法只是限制POST數據的數量，而不能徹底解決這個問題。例如，如果某個POST字段是一個json數據類型，會被PHP json_decode，那么只要構造一個超大的json攻擊數據照樣可以達到攻擊目的。理論上，只要PHP代碼中某處構造Array的數據依賴于外部輸入，則都可能造成這個問題，因此徹底的解決方案要從Zend底層HashTable的實現動手。一般來說有兩種方式，一是限制每個桶鏈表的最長長度；二是使用其它數據結構如紅黑樹取代鏈表組織碰撞哈希（并不解決哈希碰撞，只是減輕攻擊影響，將N個數據的操作時間從O(N^2)降至O(NlogN)，代價是普通情況下接近O(1)的操作均變為O(logN)）。

目前使用最多的仍然是POST數據攻擊，因此建議生產環境的PHP均進行升級或打補丁。至于從數據結構層面修復這個問題，目前還沒有任何方面的消息。

參考

[1] Supercolliding a PHP array

[2] PHP5.2.*防止Hash沖突拒絕服務攻擊的Patch

[3] 通過構造Hash沖突實現各種語言的拒絕服務攻擊

[4] PHP數組的Hash沖突實例

[5] PHP 5.4.0 RC4 released

AddThis Sharing ButtonsShare to WeChat

大家久等了，今天又是干貨 ，昨天發了一個前端css寫的QQ企鵝后，很多人私信表示感謝，說我寫的好，有創意，很有意思，今天呢，我要給大家帶來一個非常經典的游戲，貪吃蛇，javascript學習的小伙伴們有福利了，好好練習吧，你們都可以的。

首先還是要推薦我的javascript學習QQ群：594959296，從我一個人到現在的948人都是我每篇文章每個案例來的小伙伴，都是前端黨，群里不定期分享干貨。想學到東西的都可以來，歡迎初學和進階中的小伙伴。

貪吃蛇大家都不陌生吧~，哈哈，賣個萌。

因為沒有圖片素材，所以只能用簡單的樣式代替了，不要嫌棄呀~

思路

1. 讓我們的小蛇動起來

2. 隨機生成食物

3. .每吃掉一個食物，蛇的身體會變長，食物會重新換位置

html界面

css樣式

注：

1. 藍色的小方塊代表食物

2. 紅色的小方塊代表小蛇

3. 綠色的小方塊代表吃掉怪物后增長的身體

準備工作

獲取元素節點、設置全局變量；

讓我們的小蛇動起來

通過按鍵盤的上下左右鍵，控制小蛇的移動方向，并記錄小蛇走過的位置。

我們通過什么來獲取我們按下的是哪個鍵？？

我們當然通過ASCII碼值；

信息在計算機上是用二進制表示的，這種表示法讓人理解就很困難。因此計算機上都配有輸入和輸出設備，這些設備的主要目的就是，以一種人類可閱讀的形式將信息在這些設備上顯示出來供人閱讀理解。為保證人類和設備，設備和計算機之間能進行正確的信息交換，人們編制的統一的信息交換代碼，這就是ASCII碼表，它的全稱是“美國信息交換標準代碼”

左-------》對應的ASCII碼值是 37；

上-------》對應的ASCII碼值是 38；

右-------》對應的ASCII碼值是 39；

下-------》對應的ASCII碼值是 40；

檢驗碰撞詳解

這里筆者覺得語言的描述太空洞，還是弄幾張圖吧，圖是筆者手繪的，不要嫌丑，畫的是沒有碰撞的情況，那取反，就說明碰撞到了

食物隨機出現

把食物的隨機出現封裝在一個函數里，那么我們后續需要的時候可以直接調用。

利用隨機數來讓食物的位置隨機出現。

創建定時器、檢驗碰撞

碰撞檢測原理：

蛇在實物的左邊、右邊、上邊、下邊的時候，說明沒有發生碰撞，那么我們取反，就說明發生碰撞

身體跟隨

每吃掉一個食物，小蛇的長度發生變化

好了，現在我們的游戲可以玩了

學習javascript也是有門檻的，就是你的html和css至少還比較熟練，您不能連html這東東是干啥的都不知道就開始學javascript了，學乘除前，學好加減法總是有益無害的。

再說二點忠告：

1. 不要急著看一些復雜的javascript網頁特效的代碼，這樣除了打擊你的自信心，什么也學不到

2. 看網上什么幾天精通javascript的，直接跳過吧，沒戲

javascript完整代碼，要代碼的可以加我的群：594959296，我都上傳到群文件里了

如果想看到更加系統的文章和學習方法經驗可以關注我的微信公眾號：‘web前端課程’關注后回復‘給我資料’可以領取一套完整的學習視頻

知不覺玩頭條已經有一個月了，分享了很多好玩的和好用的給頭條的伙伴們，期間也結識了很多朋友，大神也有很多，有給我提建議的，有要拜師的，有來讓我給他看案例的，也才知道我們大前端人才濟濟啊，今天就給大家做一個非常經典的游戲吧，超級瑪麗，想不到吧，今天百度一下才知道超級瑪麗是1985年的游戲，不知不覺已經有32年了，這里就不暴露年紀了，反正比我年紀大，不多說了，直接開始吧。

這里還是要推薦下我自己建的前端學習群：204436223，不說其他的，能進我群的沒兩把刷子怎么可以呢是吧，當然小白我也非常歡迎，都是從零開始的嘛，多虛心問問題就行了，不定期分享干貨。想學到東西的都可以來，歡迎初學和進階中的小伙伴

游戲實現功能：通過 A D 鍵來控制角色左右移動，K鍵跳，吃到子彈時使用J鍵射擊，按H鍵開始游戲。游戲還是以背景運動的方式來實現人物向前跑的效果。其中主要運用了碰撞檢測、拋物線運動等算法，并對大量的數據進行了分組處理。是否真實還原了游戲，由你來體驗并給出答案。 當然，游戲中有些地方在操作控制上稍微有些不足，有待進一步完善。目前只有一關，更多關卡正在碼代碼中...

游戲截圖：

游戲javascript源碼：

其實思路都差不多，關鍵是思路，代碼其實都很容易的，當然初學者還是要先把javascript寫熟練，孰能 生巧吧，只能這么說，對于有了幾年經驗的看我這篇文章就和兒戲一樣，對小白來說，絕對大神啊，所以，奮斗吧大家，奮斗吧初學者。

今天的這個案例就寫完了，希望大家能夠學習到東西把這個游戲做出來，源碼和素材下面第三條建議會告訴大家。

心靈雞湯來一波：

學習javascript也是有難度的，前提是你的html和css學的應該要很好，您不能連html這東東是干啥的都不知道就開始學javascript了，有很多零基礎的跑來問我，怎么寫游戲，我就呵呵一句，先把基礎布局學好吧。

再說幾點建議：

1. 不要急著看一些復雜的javascript網頁特效的代碼，這樣除了打擊你的自信心，就是打擊你的自信心。

2. 看網上什么幾天精通javascript的，不要信！費時費力不討好！

3. 這個案例就算做完了，想要完整代碼自己練習的小伙伴進我的群自助領取，已經上傳到群文件里了，群號：204436223，歡迎學習交流的小伙伴過來一起學習交流。

如果想看到更加系統的文章和學習方法經驗可以關注我的微信公眾號：‘web前端課程’關注后回復‘給我資料’可以領取一套完整的學習視頻