不论应用了哪种碰撞解决定计划略，都导致插入和查找操作的时光复杂度不再是O(1)。以查找为例，不克不及经由过程key定位到桶就停止，必须还要比较原始key(即未做哈希之前的key)是否相等，如不雅不相等，则要应用与插入雷同的算法持续查找，直到找到匹配的值或确认数据不在哈希表中。

PHP是应用单链表存储碰撞的数据，是以实际上PHP哈希表的平均查找复杂度为O(L)，个中L为桶链表的平均长度;而最坏复杂度为O(N)，此时所稀有据全部碰撞，哈希表退化成单链表。下图PHP中正常哈希表和退化哈希表的示意图。

哈希表碰撞进击就是经由过程精心构造数据，使得所稀有据全部碰撞，工资将哈希表变成一个退化的单链表，此时哈希表各类操作的时光均晋升了一个数量级，是以会消费大年夜量CPU资本，导致体系无法快速响应请求，大年夜而达到拒绝办事进击(DoS)的目标。

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;  

哈希算法

PHP哈希表最小容量是8(2^3)，最安闲量是0×80000000(2^31)，并向2的┞符数次幂圆整(即长度会主动扩大为2的┞符数次幂，如13个元素的哈希表长度为16;100个元素的哈希表长度为128)。nTableMask被初始化为哈希表长度(圆整后)减1。具体代码在zend/Zend_hash.c的_zend_hash_init函数中，这里朝长进步与本文相干的部分并加上少量注释。

可以看到，进行哈希碰撞进击的前提是哈希算法特别轻易找出碰撞，如不雅是MD5或者SHA1那根本就没戏了，荣幸的是(也可以说不幸的是)大年夜多半编程说话应用的哈希算法都十分简单(这是为了效力推敲)，是以可以不费吹灰之力之力构造出进击数据。下一节精晓过分析Zend相干内核代码，找出进击哈希表碰撞进击PHP的办法。

值得一提的是PHP向2的┞符数次幂取圆整办法异常奇妙，可以背下来在须要的时刻应用。

Zend HashTable的哈希算法异常简单：

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) 	
			
 2/4   首页 上一页 1 2 3 4 下一页 尾页
	
			

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


本文标题：PHP哈希表碰撞攻击原理
地址：http://www.17bianji.com/lsqh/35521.html
 1/2    1