php中的哈希碰撞以及防御

周国辉发布于2019-06-27 15:26 / 3190人阅读

php中的哈希表

php中的变量是以符号表的方式进行存储的，实际上也是个HashTable，哈希表是通过特定的哈希算法将索引转换成特定的index然后映射到对应的槽中，然后采用拉链法，在一个槽中使用链表将数据进行存储，链表的时间复杂度为O(n)。

php中的hashtable的结构定义在Zend/zend_hash.h文件中：

//保存数据的单链表结构
typedef struct bucket {
   ulong h;                  /* Used for numeric indexing */
   uint nKeyLength;        //key长度
   void *pData;        //指向bucket中保存的数据的指针
   void *pDataPtr;    //指针数据
   struct bucket *pListNext;    //指向hashtable桶列中下一个元素
   struct bucket *pListLast;    //指向hashtable桶列前一个元素
   struct bucket *pNext;        //指向具有同一个hash index的桶列的后一个元素
   struct bucket *pLast;        //指向具有同一个hash index的桶列的前一个元素
   const char *arKey;        //必须是最后一个成员，key的名称
} Bucket;

每个数据元素bucket有一个键名key，它在整个hashtable中是唯一的，不能重复；根据键名可以唯一确定hashtable中的数据元素
在php的数组中，键的值可以是整型或字符串，在这里也只有这两种形式：

如果key为字符串的话：字符串arKey作为键名，该字符串的长度为nKeyLength，h字段保存arKey对应的hash值

索引方式：这时nKeyLength为0，索引值存储在h上，也就是数据元素的键名

bucket是保存在hashtable上的一个双向链表，其向前和向后的元素分别用pLast和pNext来表示。新插入的Becket放在该桶的最前面
在Bucket中，实际上数据是保存在pData指针指向的内存块中的，通常这个内存块是系统额外分配的。但是存在例外，当Bucket保存的数据是一个指针的时候，Hashtable不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pDataPtr中，然后再将pData指向本结构成员的地址

hashtable中所有的bucket通过pListNext，pListLast构成了一个双向链表。最新插入的Bucket放在双向链表的最后面

//hashtable结构体
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;

hash表的主要保存的数据包括两部分：哈希表中存储的数据的个数；保存数据的容器
在HashTable结构中，nTableSize指定了HashTable的大小，同时也限定了哈希表中能保存的Bucket的数量，该数值越大，系统为HashTable分配的内存就越多。为了提高计算效率，系统自动会将nTableSize调整到最小一个不小于nTableSize的2的整数次方，这个其实不太懂
arBuckets是HashTable的关键，HashTable会自动向系统申请一块内存，并将其地址赋值给arBuckets，该内存大小正好容纳nTableSize指针。我们可以将arBuckets看作一个大小为nTableSize的数组，每个数组元素都是一个指针，用于指向存放数据的Buckets。在初始化的时候每个指针都为null

nTableMask的值永远是nTableSize - 1，引入这个字段的主要目的是为了提高计算效率，为了快速计算Buckets键名在arBuckets数组中的索引

nNumberOfElements记录了HastTable当前保存的数据元素的个数。当nNumberOfElements大于nTableSize的时候，HashTable就自动扩展为原来的两倍大小

nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets索引

pListHead,pListTail分别表示Buckets双向链表的第一个和最后一个元素，这些元素通常是根据插入的顺序排列的。也可以根据对应的排序函数对其进行重新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置，它是一个指针，指向当前遍历到的Bucket，初始值是pListHead

pDestroyctor是一个函数指针，在HashTable的增加，修改，删除Bucket时自动调用，用于处理相关数据的清理工作

persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。具体请参考PHP的内存管理。

php中为了使用的哈希算法是DJBX33A

哈希碰撞

php中是使用单链表去存储碰撞的数据的，所以实际上php在哈希表上的平均查找复杂度为O(L)，其中L为桶链表的平均长度；而最坏的时间复杂度为O(N)，此时所以存储到hashtable上的数据全部发生碰撞，哈希表退化成为单链表。

哈希表碰撞就是精心设计的数据使所有的数据发生碰撞。人为的将一个哈希表退化成为一个单链表，在哈希表上的各种操作的时间会提升一个数量级，大量消耗CPU，导致系统无法快速响应请求，从而达到拒绝服务(DDOS)的目的

一般情况下很难直接修改php的代码去制造哈希碰撞攻击，但是在表单参数$_POST是一个Array，内部就是通过Zend HashTable来实现的，攻击者只要构造一个含有大量碰撞的key的post请求，就可以达到ddos攻击的目的

哈希表碰撞的防御

以上说了通过http post请求中的表单数据进行攻击，防御的方式可以：

在php5.3以上的版本中，post参数的数量存在最大的限制max_input_vars => 1000

在web服务器层面进行处理，如通过限制请求body大小和参数的数量等，这个也是目前使用最多的解决方案

其实以上的两种解决方案并不能解决问题，因为只是单纯的在参数的数量上进行限制了，但是入股请求的数据中包含json数据，但其中的数据就是碰撞的array。理论上，只要php代码某处构造array的数据依赖于外部输入，则都可能造成这个问题，因此彻底的解决方案是更改Zend底层的HashTable实现

限制每个桶链表的最长长度

使用其他数据结构如红黑树取代链表组织碰撞哈希（并不解决哈希碰撞，只是减轻攻击影响，将N个数据的操作时间从O(N^2)降至O(NlogN)，代价是普通情况下接近O(1)的操作均变为O(logN)）

参考：

php内核探索：http://www.nowamagic.net/libr...

云服务器 GPU云服务器 php哈希碰撞哈希表碰撞攻击 java中的”哈希“ js中的6大数据类型以及应用

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22349.html

「构建安全的 PHP 应用」读书笔记

摘要：书名构建安全的应用作者美译者张庆龙以下记录这本安全小书的大致内容，对书中的知识点进行备忘。可以保证内容的安全性，使得只有最终传递到的具有有效证书的接收者才能得到这一内容。缺省安全及跨站攻击缺省安全我们应该为验书名：构建安全的 PHP 应用作者：(美) Ben Edmunds 译者：张庆龙以下记录这本 PHP Web 安全小书的大致内容，对书中的知识点进行备忘。不要相信任何用...

kviccn 2019-06-27 16:12 评论0 收藏0
系统的讲解 - PHP WEB 安全防御

摘要：支持自动识别密码哈希格式并通过字典破解密码哈希。支持枚举用户密码哈希权限角色数据库数据表和列。支持在数据库管理系统中搜索指定的数据库名表名或列名。水平越权用户未授权可以访问用户的数据。对于所有需要权限控制的位置，必须严格检验用户权限级别。常见漏洞 showImg(https://segmentfault.com/img/bVbst5x?w=918&h=921); 看到上图的漏洞是不是...

LinkedME2016 2019-07-01 12:46 评论0 收藏0
几分钟理解数据结构 - 哈希表及其优化

摘要：小概哈希容器也可以理解为是一种映射容器，采用哈希算法映射算法，散列算法，将不定长的数据压缩成定长的数据，这串定长值我们称为哈希值，并将不同的哈希值分组存起来，每一个分组我们认为是一个槽我们将不同的数据格式通过哈希算法，将其映射到不同的槽内，小概哈希容器也可以理解为是一种映射容器，采用哈希算法（映射算法，散列算法），将不定长的数据压缩成定长的数据，这串定长值我们称为哈希值，并将不同...

Dean 2019-08-15 11:06 评论0 收藏0
PHP 数组

摘要：以下为数组的基础结构，插入，查找和过程。再存放其，如果根据其下标计算取模得到的中已经有值，那么说明出现了哈希碰撞，这个时候把当前中的值取出来保存到当前，把保存的索引保存在当前，以此类推。以下为 PHP 数组的基础结构，插入，查找和 rehash 过程。基础结构： struct _zend_array { zend_refcounted_h gc; union { ...

tracy 2019-07-01 10:50 评论0 收藏0