PHP内核探索:哈希表的冲突攻击原理

在这里，我们将向您展示PHP内核如何探索：散列表与图片和文本的碰撞攻击原理。

最近，Hashtable碰撞作为DOS攻击的话题不断被提出，各种语言都被吸引。本文从PHP内核的源代码出发，讨论了这种攻击的原理和实现。

哈希表冲突攻击的基本原理

哈希表是一种搜索效率高的数据结构，许多语言都在内部实现了它。PHP中的哈希表是一种极其重要的数据结构，它不仅用于表示Array数据类型，还用于存储Zend虚拟机中的上下文信息(执行上下文的变量和函数都是通过哈希表结构存储的)。

理想情况下，哈希表插入和查找操作的时间复杂度为O(1)。任何数据项都可以在独立于哈希表长度的时间内计算哈希值(键)，然后在恒定时间内定位桶。当然，这是一个理想的情况，因为任何哈希表的长度都是有限的，所以必然会有不同的数据项具有相同的哈希值，然后确定不同的数据项在同一个桶中的情况，这就是所谓的碰撞。哈希表的实现需要解决冲突问题。解决碰撞问题有两种方法。第一种方法是根据某种原理将碰撞的数据确定给其他桶。比如线性检测——，如果数据在插入时发生碰撞，则依次搜索这个桶后面的桶，放入第一个未使用的桶；第二种策略是每个桶不是一个只能容纳单个数据项的位置，而是一个可以容纳多个数据项的数据结构(如链表或红黑树)，所有冲突的数据都组织在某个数据结构中。

无论使用哪种冲突解决策略，插入和搜索操作的时间复杂度都不再是O(1)。以搜索为例，如果不能按关键字定位桶，还必须比较原始关键字(即哈希前的关键字)是否相等。如果不相等，您应该使用与insert相同的算法继续搜索，直到找到匹配的值或确认数据不在哈希表中。

PHP使用单链表存储碰撞数据，所以实际上PHP哈希表的平均搜索复杂度为O(L)，其中L是桶链表的平均长度；最差的复杂度是O(N)，当所有数据发生冲突时，哈希表退化为一个链表。下图显示了PHP中的正常哈希表和降级哈希表。

哈希表冲突攻击是通过精心构造数据，使所有数据发生冲突，人为地将哈希表变成降级的单链表。此时哈希表的操作时间增加一个数量级，会消耗大量的CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击(DoS)的目的。

可以看出，哈希碰撞攻击的前提是哈希算法特别容易发现碰撞，如果是MD5或者SHA1，基本上是不可能的。幸运的是(或者不幸的是)，大多数编程语言使用的哈希算法非常简单(为了效率)，因此可以毫不费力地构造攻击数据。在下一节中，我们将通过分析Zend相关的内核代码，找出攻击哈希表冲突和攻击PHP的方法。Zend Hash Table PHP的内部实现数据结构使用了一种叫做Backet的结构来表示桶，所有哈希值相同的桶都被组织成一个链表。哈希表由哈希表结构表示。相关源代码在zend/Zend_hash.h下：

typedef结构桶ulong h；/*用于数字索引*/uint nKeyLength；void * pdata void * pdata ptrstruck bucket * pListNextstruct bucket * plistlasstruct bucket * pNextstruct bucket * pLastchar ArKey[1]；/*必须是最后一个元素*/}桶；typedef struct _ hashtable { uint nTableSize；uint问题询问；uint nNumOfElementsulong nNextFreeElementBucket * pInternalPointer/*用于元素遍历*/Bucket * pli thead；桶* pListTail水桶* *阿不思；dtor _ func _ t pDestructorzend _ bool持久；无符号字符napplicountzend _ bool Bapplypprotection # ifZEND _ DEBUG int不一致；#endif}哈希表；字段名很清楚的表明其用途，因此不做过多解释。重点明确下面几个字段：铲斗中的“h”用于存储原始钥匙；散列表中的问题提问是一个掩码，一般被设为nTableSize - 1，与哈希算法有密切关系，后面讨论哈希算法时会详述；面包指向一个指针数组，其中每个元素是一个指向水桶链表的头指针。哈希算法服务器端编程语言(专业超文本预处理器的缩写)哈希表最小容量是8(2^3),最大容量是080000000(2^31),并向2的整数次幂圆整（即长度会自动扩展为2的整数次幂，如13个元素的哈希表长度为16;100个元素的哈希表长度为128)。问题提问被初始化为哈希表长度（圆整后)减1。具体代码在zend/Zend_hash.c的_ zend _哈希_init函数中，这里截取与本文相关的部分并加上少量注释。

ZEND _ API int _ ZEND _ hash _ init(HashTable * ht，uintnSize，hash_func_t pHashFunction，dtor_func_t pDestructor，zend_bool持久ZEND _ FILE _ LINE _ DC){ uinti=3；桶* * tmp设置_不一致（高温_正常);//长度向2的整数次幂圆整if(nSize=0x80000000) { /*防止溢出*/ht-nTableSize=0x 80000000；} else { while((1U I)NSize){ I；} ht-nTableSize=1i；} ht-nTambleAsk=ht-nTableSize-1；/*此处省略若干代码…*/返回成功；}值得一提的是服务器端编程语言(专业超文本预处理器的缩写)向2的整数次幂取圆整方法非常巧妙，可以背下来在需要的时候使用。

阿维斯陀经注解哈希表的哈希算法异常简单：

复制代码代码如下：哈希(键)=keynTableMask

即简单将数据的原始键与散列表的问题提问进行按位与即可。

如果原始键为字符串，则首先使用时间33算法将字符串转为整形再与问题提问按位与。

复制代码代码如下：哈希(strkey)=时间33(strkey)n问题询问

下面是阿维斯陀经注解源码中查找哈希表的代码：

ZEND _ API int ZEND _ hash _ index _ find(constHashTable * ht，ulong h，void * * pData){ uint nIndex；桶* p；IS _ CONFERENCE(ht)；nIndex=h ht-n问题提问；p=ht-AbOckets[nIndex]；while(p！=NULL){ if((p-h==h)(p-nKeyLength==0)){ * Pdata=p-Pdata；返回成功；} p=p-pNext；} return failure } ZEND _ API int ZEND _ hash _ find(constHashTable * ht，constchar *arKey，uint nKeyLength，void * * pData){ ulong h；uint nIndex桶* p；IS _ CONFERENCE(ht)；h=zend_inline_hash_func(arKey，nKeyLength)；nIndex=h ht-n问题提问；p=ht-AbOckets[nIndex]；while(p！=NULL){ if((p-h==h)(p-nKeyLength==nKeyLength)){ if(！memcmp(p-arKey，arKey，nKeyLength)){ * Pdata=p-Pdata；返回成功；} } p=p-pNext；} returnFAILURE}其中zend _哈希_索引_查找用于查找整数键的情况zend _哈希查找(_ d)用于查找字符串钥匙。逻辑基本一致，只是字符串键会通过zend_inline_hash_func转为整数键，zend_inline_hash_func封装了时间33算法，具体代码就不贴出了。攻击基本攻击知道了服务器端编程语言(专业超文本预处理器的缩写)内部哈希表的算法，就可以利用其原理构造用于攻击的数据。一种最简单的方法是利用掩码规律制造碰撞。上文提到阿维斯陀经注解哈希表的长度n放大会被圆整为2的整数次幂，假设我们构造一个2^16的哈希表，则n放大的二进制表示为：1 0000 0000 0000 0000,而n问题询问=n可用大小- 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(真)；$ array=array()；for($key=0，$ MaxKey=($ size-1)* $ size；$ key=$ maxKey$ key=$ size){ $ array[$ key]=0；} $ end time=micro time(true)；echo $endTime- $startTime，'秒'；这段代码在我的VPS(单CPU，512M内存)上花了将近88秒完成，在此期间CPU资源几乎耗尽：

而相同大小的普通哈希表只需要0.036秒就可以插入：

？php$size=pow(2，16)；$startTime=microtime(真)；$ array=array()；for($key=0，$ MaxKey=($ size-1)* $ size；$ key=$ size$ key=1){ $ array[$ key]=0；} $ end time=micro time(true)；echo $endTime- $startTime，'秒'；

可以证明第二个代码插入N个元素的时间在O(N)级，而第一个攻击代码插入N个元素需要O(N ^ 2)。

开机自检攻击

当然，一般情况下攻击者很难直接修改PHP代码，但攻击者仍然可以通过某些方式间接构造哈希表进行攻击。例如，PHP将把接收到的HTTP post请求中的数据构造为$_POST，它是一个Array，内部由Zend HashTable表示。因此，攻击者可以通过构造包含大量冲突密钥的POST请求来达到攻击的目的。具体做法不予示范。

防止开机自检攻击

目前PHP的保护措施是在POST模式下控制POST数据量，抵御哈希冲突攻击。在=PHP5.3.9的版本中，增加了一个配置项max_input_vars，用于标识http请求接收的最大参数个数，默认值为1000。因此，PHP5.3.x用户可以通过升级到5.3.9来避免哈希冲突攻击。5.2.x的用户可以使用这个补丁：http://www.laruence.com/2011/12/30/2440.html.

另一种保护方法是在Web服务器级进行处理，比如限制http请求体的大小和参数的数量，这是最常用的临时处理方案。具体的做法与不同的Web服务器有关，就不详细描述了。

其他保护

上述保护方法只是限制了POST数据量，并不能完全解决这个问题。比如一个POST字段是json数据类型，就会被PHP json_decode解码，所以只要构造出一个大的json攻击数据，攻击还是可以实现的。理论上，只要PHP代码中构造Array的数据依赖外部输入，就有可能造成这个问题，所以彻底的解决应该从Zend底层HashTable的实现开始。一般来说有两种方式，一种是限制每个桶链表的最长长度；二是用红黑树等其他数据结构代替链表来组织碰撞哈希(它没有解决哈希冲突，只是降低了攻击的影响，将N个数据的操作时间从O(N ^ 2)减少到O(NlogN)，代价是正常情况下所有接近O(1)的操作都变成O(logN)。

目前使用最多的攻击仍然是POST数据攻击，建议生产环境下的PHP应该升级或者打补丁。至于从数据结构层面修复这个问题，目前还没有消息。

以上就是本文的全部内容，希望大家喜欢。