整合營(yíng)銷(xiāo)服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢(xún)熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢(xún)熱線：
近哈希表碰撞攻擊（Hashtable collisions as DOS attack）的話(huà)題不斷被提起，各種語(yǔ)言紛紛中招。本文結(jié)合PHP內(nèi)核源碼，聊一聊這種攻擊的原理及實(shí)現(xiàn)。
哈希表是一種查找效率極高的數(shù)據(jù)結(jié)構(gòu)，很多語(yǔ)言都在內(nèi)部實(shí)現(xiàn)了哈希表。PHP中的哈希表是一種極為重要的數(shù)據(jù)結(jié)構(gòu)，不但用于表示Array數(shù)據(jù)類(lèi)型，還在Zend虛擬機(jī)內(nèi)部用于存儲(chǔ)上下文環(huán)境信息（執(zhí)行上下文的變量及函數(shù)均使用哈希表結(jié)構(gòu)存儲(chǔ)）。
理想情況下哈希表插入和查找操作的時(shí)間復(fù)雜度均為O(1)，任何一個(gè)數(shù)據(jù)項(xiàng)可以在一個(gè)與哈希表長(zhǎng)度無(wú)關(guān)的時(shí)間內(nèi)計(jì)算出一個(gè)哈希值（key），然后在常量時(shí)間內(nèi)定位到一個(gè)桶（術(shù)語(yǔ)bucket，表示哈希表中的一個(gè)位置）。當(dāng)然這是理想情況下，因?yàn)槿魏喂１淼拈L(zhǎng)度都是有限的，所以一定存在不同的數(shù)據(jù)項(xiàng)具有相同哈希值的情況，此時(shí)不同數(shù)據(jù)項(xiàng)被定為到同一個(gè)桶，稱(chēng)為碰撞（collision）。哈希表的實(shí)現(xiàn)需要解決碰撞問(wèn)題，碰撞解決大體有兩種思路，第一種是根據(jù)某種原則將被碰撞數(shù)據(jù)定為到其它桶，例如線性探測(cè)——如果數(shù)據(jù)在插入時(shí)發(fā)生了碰撞，則順序查找這個(gè)桶后面的桶，將其放入第一個(gè)沒(méi)有被使用的桶；第二種策略是每個(gè)桶不是一個(gè)只能容納單個(gè)數(shù)據(jù)項(xiàng)的位置，而是一個(gè)可容納多個(gè)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（例如鏈表或紅黑樹(shù)），所有碰撞的數(shù)據(jù)以某種數(shù)據(jù)結(jié)構(gòu)的形式組織起來(lái)。
不論使用了哪種碰撞解決策略，都導(dǎo)致插入和查找操作的時(shí)間復(fù)雜度不再是O(1)。以查找為例，不能通過(guò)key定位到桶就結(jié)束，必須還要比較原始key（即未做哈希之前的key）是否相等，如果不相等，則要使用與插入相同的算法繼續(xù)查找，直到找到匹配的值或確認(rèn)數(shù)據(jù)不在哈希表中。
PHP是使用單鏈表存儲(chǔ)碰撞的數(shù)據(jù)，因此實(shí)際上PHP哈希表的平均查找復(fù)雜度為O(L)，其中L為桶鏈表的平均長(zhǎng)度；而最壞復(fù)雜度為O(N)，此時(shí)所有數(shù)據(jù)全部碰撞，哈希表退化成單鏈表。下圖PHP中正常哈希表和退化哈希表的示意圖。
哈希表碰撞攻擊就是通過(guò)精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)，因此會(huì)消耗大量CPU資源，導(dǎo)致系統(tǒng)無(wú)法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊（DoS）的目的。
可以看到，進(jìn)行哈希碰撞攻擊的前提是哈希算法特別容易找出碰撞，如果是MD5或者SHA1那基本就沒(méi)戲了，幸運(yùn)的是（也可以說(shuō)不幸的是）大多數(shù)編程語(yǔ)言使用的哈希算法都十分簡(jiǎn)單（這是為了效率考慮），因此可以不費(fèi)吹灰之力之力構(gòu)造出攻擊數(shù)據(jù)。下一節(jié)將通過(guò)分析Zend相關(guān)內(nèi)核代碼，找出攻擊哈希表碰撞攻擊PHP的方法。
數(shù)據(jù)結(jié)構(gòu)
PHP中使用一個(gè)叫Backet的結(jié)構(gòu)體表示桶，同一哈希值的所有桶被組織為一個(gè)單鏈表。哈希表使用HashTable結(jié)構(gòu)體表示。相關(guān)源碼在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;
字段名很清楚的表明其用途，因此不做過(guò)多解釋。重點(diǎn)明確下面幾個(gè)字段：Bucket中的“h”用于存儲(chǔ)原始key；HashTable中的nTableMask是一個(gè)掩碼，一般被設(shè)為nTableSize - 1，與哈希算法有密切關(guān)系，后面討論哈希算法時(shí)會(huì)詳述；arBuckets指向一個(gè)指針數(shù)組，其中每個(gè)元素是一個(gè)指向Bucket鏈表的頭指針。
哈希算法
PHP哈希表最小容量是8（2^3），最大容量是0x80000000（2^31），并向2的整數(shù)次冪圓整（即長(zhǎng)度會(huì)自動(dòng)擴(kuò)展為2的整數(shù)次冪，如13個(gè)元素的哈希表長(zhǎng)度為16；100個(gè)元素的哈希表長(zhǎng)度為128）。nTableMask被初始化為哈希表長(zhǎng)度（圓整后）減1。具體代碼在zend/Zend_hash.c的_zend_hash_init函數(shù)中，這里截取與本文相關(guān)的部分并加上少量注釋。
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);
//長(zhǎng)度向2的整數(shù)次冪圓整
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的整數(shù)次冪取圓整方法非常巧妙，可以背下來(lái)在需要的時(shí)候使用。
Zend HashTable的哈希算法異常簡(jiǎn)單：
hash(key)=key & nTableMask
即簡(jiǎn)單將數(shù)據(jù)的原始key與HashTable的nTableMask進(jìn)行按位與即可。
如果原始key為字符串，則首先使用Times33算法將字符串轉(zhuǎn)為整形再與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用于查找整數(shù)key的情況，zend_hash_find用于查找字符串key。邏輯基本一致，只是字符串key會(huì)通過(guò)zend_inline_hash_func轉(zhuǎn)為整數(shù)key，zend_inline_hash_func封裝了times33算法，具體代碼就不貼出了。
基本攻擊
知道了PHP內(nèi)部哈希表的算法，就可以利用其原理構(gòu)造用于攻擊的數(shù)據(jù)。一種最簡(jiǎn)單的方法是利用掩碼規(guī)律制造碰撞。上文提到Zend HashTable的長(zhǎng)度nTableSize會(huì)被圓整為2的整數(shù)次冪，假設(shè)我們構(gòu)造一個(gè)2^16的哈希表，則nTableSize的二進(jìn)制表示為：1 0000 0000 0000 0000，而nTableMask = nTableSize – 1為：0 1111 1111 1111 1111。接下來(lái)，可以以0為初始值，以2^16為步長(zhǎng)，制造足夠多的數(shù)據(jù)，可以得到如下推測(cè)：
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
……
概況來(lái)說(shuō)只要保證后16位均為0，則與掩碼位于后得到的哈希值全部碰撞在位置0。
下面是利用這個(gè)原理寫(xiě)的一段攻擊代碼：
<?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內(nèi)存）上用了近88秒才完成，并且在此期間CPU資源幾乎被用盡：
而普通的同樣大小的哈希表插入僅用時(shí)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個(gè)元素的時(shí)間在O(N)水平，而第一段攻擊代碼則需O(N^2)的時(shí)間去插入N個(gè)元素。
POST攻擊
當(dāng)然，一般情況下很難遇到攻擊者可以直接修改PHP代碼的情況，但是攻擊者仍可以通過(guò)一些方法間接構(gòu)造哈希表來(lái)進(jìn)行攻擊。例如PHP會(huì)將接收到的HTTP POST請(qǐng)求中的數(shù)據(jù)構(gòu)造為$_POST，而這是一個(gè)Array，內(nèi)部就是通過(guò)Zend HashTable表示，因此攻擊者只要構(gòu)造一個(gè)含有大量碰撞key的post請(qǐng)求，就可以達(dá)到攻擊的目的。具體做法不再演示。
POST攻擊的防護(hù)
針對(duì)POST方式的哈希碰撞攻擊，目前PHP的防護(hù)措施是控制POST數(shù)據(jù)的數(shù)量。在>=PHP5.3.9的版本中增加了一個(gè)配置項(xiàng)max_input_vars，用于標(biāo)識(shí)一次http請(qǐng)求最大接收的參數(shù)個(gè)數(shù)，默認(rèn)為1000。因此PHP5.3.x的用戶(hù)可以通過(guò)升級(jí)至5.3.9來(lái)避免哈希碰撞攻擊。5.2.x的用戶(hù)可以使用這個(gè)patch：http://www.laruence.com/2011/12/30/2440.html。
另外的防護(hù)方法是在Web服務(wù)器層面進(jìn)行處理，例如限制http請(qǐng)求body的大小和參數(shù)的數(shù)量等，這個(gè)是現(xiàn)在用的最多的臨時(shí)處理方案。具體做法與不同Web服務(wù)器相關(guān)，不再詳述。
其它防護(hù)
上面的防護(hù)方法只是限制POST數(shù)據(jù)的數(shù)量，而不能徹底解決這個(gè)問(wèn)題。例如，如果某個(gè)POST字段是一個(gè)json數(shù)據(jù)類(lèi)型，會(huì)被PHP json_decode，那么只要構(gòu)造一個(gè)超大的json攻擊數(shù)據(jù)照樣可以達(dá)到攻擊目的。理論上，只要PHP代碼中某處構(gòu)造Array的數(shù)據(jù)依賴(lài)于外部輸入，則都可能造成這個(gè)問(wèn)題，因此徹底的解決方案要從Zend底層HashTable的實(shí)現(xiàn)動(dòng)手。一般來(lái)說(shuō)有兩種方式，一是限制每個(gè)桶鏈表的最長(zhǎng)長(zhǎng)度；二是使用其它數(shù)據(jù)結(jié)構(gòu)如紅黑樹(shù)取代鏈表組織碰撞哈希（并不解決哈希碰撞，只是減輕攻擊影響，將N個(gè)數(shù)據(jù)的操作時(shí)間從O(N^2)降至O(NlogN)，代價(jià)是普通情況下接近O(1)的操作均變?yōu)镺(logN)）。
目前使用最多的仍然是POST數(shù)據(jù)攻擊，因此建議生產(chǎn)環(huán)境的PHP均進(jìn)行升級(jí)或打補(bǔ)丁。至于從數(shù)據(jù)結(jié)構(gòu)層面修復(fù)這個(gè)問(wèn)題，目前還沒(méi)有任何方面的消息。
[1] Supercolliding a PHP array
[2] PHP5.2.*防止Hash沖突拒絕服務(wù)攻擊的Patch
[3] 通過(guò)構(gòu)造Hash沖突實(shí)現(xiàn)各種語(yǔ)言的拒絕服務(wù)攻擊
[4] PHP數(shù)組的Hash沖突實(shí)例
[5] PHP 5.4.0 RC4 released
AddThis Sharing ButtonsShare to WeChat
大家久等了，今天又是干貨 ，昨天發(fā)了一個(gè)前端css寫(xiě)的QQ企鵝后，很多人私信表示感謝，說(shuō)我寫(xiě)的好，有創(chuàng)意，很有意思，今天呢，我要給大家?guī)?lái)一個(gè)非常經(jīng)典的游戲，貪吃蛇，javascript學(xué)習(xí)的小伙伴們有福利了，好好練習(xí)吧，你們都可以的。
貪吃蛇大家都不陌生吧~，哈哈，賣(mài)個(gè)萌。
因?yàn)闆](méi)有圖片素材，所以只能用簡(jiǎn)單的樣式代替了，不要嫌棄呀~
思路
讓我們的小蛇動(dòng)起來(lái)
隨機(jī)生成食物
.每吃掉一個(gè)食物，蛇的身體會(huì)變長(zhǎng)，食物會(huì)重新?lián)Q位置
注：
藍(lán)色的小方塊代表食物
紅色的小方塊代表小蛇
綠色的小方塊代表吃掉怪物后增長(zhǎng)的身體
獲取元素節(jié)點(diǎn)、設(shè)置全局變量；
通過(guò)按鍵盤(pán)的上下左右鍵，控制小蛇的移動(dòng)方向，并記錄小蛇走過(guò)的位置。
我們通過(guò)什么來(lái)獲取我們按下的是哪個(gè)鍵？？
我們當(dāng)然通過(guò)ASCII碼值；
信息在計(jì)算機(jī)上是用二進(jìn)制表示的，這種表示法讓人理解就很困難。因此計(jì)算機(jī)上都配有輸入和輸出設(shè)備，這些設(shè)備的主要目的就是，以一種人類(lèi)可閱讀的形式將信息在這些設(shè)備上顯示出來(lái)供人閱讀理解。為保證人類(lèi)和設(shè)備，設(shè)備和計(jì)算機(jī)之間能進(jìn)行正確的信息交換，人們編制的統(tǒng)一的信息交換代碼，這就是ASCII碼表，它的全稱(chēng)是“美國(guó)信息交換標(biāo)準(zhǔn)代碼”
左-------》對(duì)應(yīng)的ASCII碼值是 37；
上-------》對(duì)應(yīng)的ASCII碼值是 38；
右-------》對(duì)應(yīng)的ASCII碼值是 39；
下-------》對(duì)應(yīng)的ASCII碼值是 40；
這里筆者覺(jué)得語(yǔ)言的描述太空洞，還是弄幾張圖吧，圖是筆者手繪的，不要嫌丑，畫(huà)的是沒(méi)有碰撞的情況，那取反，就說(shuō)明碰撞到了
把食物的隨機(jī)出現(xiàn)封裝在一個(gè)函數(shù)里，那么我們后續(xù)需要的時(shí)候可以直接調(diào)用。
利用隨機(jī)數(shù)來(lái)讓食物的位置隨機(jī)出現(xiàn)。
碰撞檢測(cè)原理：
蛇在實(shí)物的左邊、右邊、上邊、下邊的時(shí)候，說(shuō)明沒(méi)有發(fā)生碰撞，那么我們?nèi)》矗驼f(shuō)明發(fā)生碰撞
每吃掉一個(gè)食物，小蛇的長(zhǎng)度發(fā)生變化
好了，現(xiàn)在我們的游戲可以玩了
學(xué)習(xí)javascript也是有門(mén)檻的，就是你的html和css至少還比較熟練，您不能連html這東東是干啥的都不知道就開(kāi)始學(xué)javascript了，學(xué)乘除前，學(xué)好加減法總是有益無(wú)害的。
再說(shuō)二點(diǎn)忠告：
不要急著看一些復(fù)雜的javascript網(wǎng)頁(yè)特效的代碼，這樣除了打擊你的自信心，什么也學(xué)不到
看網(wǎng)上什么幾天精通javascript的，直接跳過(guò)吧，沒(méi)戲
javascript完整代碼，要代碼的可以加我的群：594959296，我都上傳到群文件里了
知不覺(jué)玩頭條已經(jīng)有一個(gè)月了，分享了很多好玩的和好用的給頭條的伙伴們，期間也結(jié)識(shí)了很多朋友，大神也有很多，有給我提建議的，有要拜師的，有來(lái)讓我給他看案例的，也才知道我們大前端人才濟(jì)濟(jì)啊，今天就給大家做一個(gè)非常經(jīng)典的游戲吧，超級(jí)瑪麗，想不到吧，今天百度一下才知道超級(jí)瑪麗是1985年的游戲，不知不覺(jué)已經(jīng)有32年了，這里就不暴露年紀(jì)了，反正比我年紀(jì)大，不多說(shuō)了，直接開(kāi)始吧。
這里還是要推薦下我自己建的前端學(xué)習(xí)群：204436223，不說(shuō)其他的，能進(jìn)我群的沒(méi)兩把刷子怎么可以呢是吧，當(dāng)然小白我也非常歡迎，都是從零開(kāi)始的嘛，多虛心問(wèn)問(wèn)題就行了，不定期分享干貨。想學(xué)到東西的都可以來(lái)，歡迎初學(xué)和進(jìn)階中的小伙伴
游戲?qū)崿F(xiàn)功能：通過(guò) A D 鍵來(lái)控制角色左右移動(dòng)，K鍵跳，吃到子彈時(shí)使用J鍵射擊，按H鍵開(kāi)始游戲。游戲還是以背景運(yùn)動(dòng)的方式來(lái)實(shí)現(xiàn)人物向前跑的效果。其中主要運(yùn)用了碰撞檢測(cè)、拋物線運(yùn)動(dòng)等算法，并對(duì)大量的數(shù)據(jù)進(jìn)行了分組處理。是否真實(shí)還原了游戲，由你來(lái)體驗(yàn)并給出答案。 當(dāng)然，游戲中有些地方在操作控制上稍微有些不足，有待進(jìn)一步完善。目前只有一關(guān)，更多關(guān)卡正在碼代碼中...
游戲截圖：
游戲javascript源碼：
其實(shí)思路都差不多，關(guān)鍵是思路，代碼其實(shí)都很容易的，當(dāng)然初學(xué)者還是要先把javascript寫(xiě)熟練，孰能 生巧吧，只能這么說(shuō)，對(duì)于有了幾年經(jīng)驗(yàn)的看我這篇文章就和兒戲一樣，對(duì)小白來(lái)說(shuō)，絕對(duì)大神啊，所以，奮斗吧大家，奮斗吧初學(xué)者。
今天的這個(gè)案例就寫(xiě)完了，希望大家能夠?qū)W習(xí)到東西把這個(gè)游戲做出來(lái)，源碼和素材下面第三條建議會(huì)告訴大家。
心靈雞湯來(lái)一波：
學(xué)習(xí)javascript也是有難度的，前提是你的html和css學(xué)的應(yīng)該要很好，您不能連html這東東是干啥的都不知道就開(kāi)始學(xué)javascript了，有很多零基礎(chǔ)的跑來(lái)問(wèn)我，怎么寫(xiě)游戲，我就呵呵一句，先把基礎(chǔ)布局學(xué)好吧。
再說(shuō)幾點(diǎn)建議：
不要急著看一些復(fù)雜的javascript網(wǎng)頁(yè)特效的代碼，這樣除了打擊你的自信心，就是打擊你的自信心。
看網(wǎng)上什么幾天精通javascript的，不要信！費(fèi)時(shí)費(fèi)力不討好！
這個(gè)案例就算做完了，想要完整代碼自己練習(xí)的小伙伴進(jìn)我的群自助領(lǐng)取，已經(jīng)上傳到群文件里了，群號(hào)：204436223，歡迎學(xué)習(xí)交流的小伙伴過(guò)來(lái)一起學(xué)習(xí)交流。
*請(qǐng)認(rèn)真填寫(xiě)需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
