PHP哈希表碰撞攻击原理

比来哈希表碰撞进击(Hashtable collisions as DOS attack)的话题赓续被提起，各类说话纷纷中招。本文结合PHP内核源码，聊一聊┞封种进击的道理及实现。

[3] 经由过程构造Hash冲突实现各类说话的拒绝办事进击

哈希表碰撞进击的基来源基本理

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; 
 
}

哈希表是一种查找效力极高的数据构造，很多说话都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据构造，不只用于表示Array数据类型，还在Zend虚拟机内部用于存储高低文情况信息(履行高低文的变量及函数均应用哈希表构造存储)。

字段名很清跋扈的注解其用处，是以不做过多解释。重点明白下面几个字段：Bucket中的“h”用于存储原始key;HashTable中的nTableMask是一个掩码，一般被设为nTableSize – 1，与哈希算法有密切关系，后面评论辩论哈希算法时会胪陈;arBuckets指向一个指针数组，个中每个元素是一个指向Bucket链表的头指针。

幻想情况下哈希表插入和查找操作的时光复杂度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的时光内计算出一个哈希值(key)，然后在常量时光内定位到一个桶(术语bucket，表示哈希表中的一个地位)。当然这是幻想情况下，因为任何哈希表的长度都是有限的，所以必定存在不合的数据项具有雷同哈希值的情况，此时不合数据项被定为到同一个桶，称为碰撞(collision)。哈希表的实现须要解决碰撞问题，碰撞解决大年夜体有两种思路，第一种是根据某种原则将被碰撞数据定为到其它桶，例如线性探测——如不雅数据在插入时产生了碰撞，则次序查找这个桶后面的桶，将其放入第一个没有被应用的桶;第二种策略是每个桶不是一个只能容纳单个数据项的地位，而是一个可容纳多个数据的数据构造(例如链表或红黑树)，所有碰撞的数据以某种数据构造的情势组织起来。

1/4 1 2 3 4 下一页尾页

　　推荐阅读

　　在服务器应用虚拟化中发现价值

一些IT专业人员可以看到大年夜办事器操作体系抽象应用法度榜样的潜力。如今，这项技巧方才起步。在办事器虚拟>>>详细阅读

本文标题：PHP哈希表碰撞攻击原理

地址：http://www.17bianji.com/lsqh/35521.html

1/2 1