• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号
登陆 注册

PHP内核探索：哈希碰撞攻击是什么？

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

最近哈希表碰撞攻击（Hashtable collisions as DOS attack）的话题不断被提起，各种语言纷纷中招。本文结合PHP内核源码，聊一聊这种攻击的原理及实现。

哈希表碰撞攻击的基本原理

哈希表是一种查找效率极高的数据结构，很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构，不但用于表示Array数据类型，还在Zend虚拟机内部用于存储上下文环境信息（执行上下文的变量及函数均使用哈希表结构存储）。

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

不论使用了哪种碰撞解决策略，都导致插入和查找操作的时间复杂度不再是O(1)。以查找为例，不能通过key定位到桶就结束，必须还要比较原始key（即未做哈希之前的key）是否相等，如果不相等，则要使用与插入相同的算法继续查找，直到找到匹配的值或确认数据不在哈希表中。

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

哈希表碰撞攻击就是通过精心构造数据，使得所有数据全部碰撞，人为将哈希表变成一个退化的单链表，此时哈希表各种操作的时间均提升了一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（DoS）的目的。

可以看到，进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞，如果是MD5或者SHA1那基本就没戏了，幸运的是（也可以说不幸的是）大多数编程语言使用的哈希算法都十分简单（这是为了效率考虑），因此可以不费吹灰之力之力构造出攻击数据。下一节将通过分析Zend相关内核代码，找出攻击哈希表碰撞攻击PHP的方法。

Zend哈希表的内部实现

PHP中使用一个叫Backet的结构体表示桶，同一哈希值的所有桶被组织为一个单链表。哈希表使用HashTable结构体表示。相关源码在zend/Zend_hash.h下：

view source
 
print?
01 typedef struct bucket {
02     ulong h;                        /* Used for numeric indexing */
03     uint nKeyLength;
04     void *pData;
05     void *pDataPtr;
06     struct bucket *pListNext;
07     struct bucket *pListLast;
08     struct bucket *pNext;
09     struct bucket *pLast;
10     char arKey[1]; /* Must be last element */
11 } Bucket;
12    
13 typedef struct _hashtable {
14     uint nTableSize;
15     uint nTableMask;
16     uint nNumOfElements;
17     ulong nNextFreeElement;
18     Bucket *pInternalPointer;   /* Used for element traversal */
19     Bucket *pListHead;
20     Bucket *pListTail;
21     Bucket **arBuckets;
22     dtor_func_t pDestructor;
23     zend_bool persistent;
24     unsigned char nApplyCount;
25     zend_bool bApplyProtection;
26 #if ZEND_DEBUG
27     int inconsistent;
28 #endif
29 } HashTable;

字段名很清楚的表明其用途，因此不做过多解释。重点明确下面几个字段：Bucket中的“h”用于存储原始key；HashTable中的nTableMask是一个掩码，一般被设为nTableSize – 1，与哈希算法有密切关系，后面讨论哈希算法时会详述；arBuckets指向一个指针数组，其中每个元素是一个指向Bucket链表的头指针。

哈希算法：PHP哈希表最小容量是8（2^3），最大容量是0×80000000（2^31），并向2的整数次幂圆整（即长度会自动扩展为2的整数次幂，如13个元素的哈希表长度为16；100个元素的哈希表长度为128）。nTableMask被初始化为哈希表长度（圆整后）减1。具体代码在zend/Zend_hash.c的_zend_hash_init函数中，这里截取与本文相关的部分并加上少量注释。

view source
 
print?
01 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)
02 {
03     uint i = 3;
04     Bucket **tmp;
05    
06     SET_INCONSISTENT(HT_OK);
07    
08     //长度向2的整数次幂圆整
09     if (nSize >= 0x80000000) {
10         /* prevent overflow */
11         ht->nTableSize = 0x80000000;
12     } else {
13         while ((1U << i) < nSize) {
14             i++;
15         }
16         ht->nTableSize = 1 << i;
17     }
18    
19     ht->nTableMask = ht->nTableSize - 1;
20    
21     /*此处省略若干代码…*/
22    
23     return SUCCESS;
24 }

值得一提的是PHP向2的整数次幂取圆整方法非常巧妙，可以背下来在需要的时候使用。

Zend HashTable的哈希算法很简单：hash(key)=key&nTableMask

即简单将数据的原始key与HashTable的nTableMask进行按位与即可。如果原始key为字符串，则首先使用Times33算法将字符串转为整形再与nTableMask按位与：hash(strkey)=time33(strkey)&nTableMask

下面是Zend源码中查找哈希表的代码：

view source
 
print?
01 ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
02 {
03     uint nIndex;
04     Bucket *p;
05    
06     IS_CONSISTENT(ht);
07    
08     nIndex = h & ht->nTableMask;
09    
10     p = ht->arBuckets[nIndex];
11     while (p != NULL) {
12         if ((p->h == h) && (p->nKeyLength == 0)) {
13             *pData = p->pData;
14             return SUCCESS;
15         }
16         p = p->pNext;
17     }
18     return FAILURE;
19 }
20    
21 ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
22 {
23     ulong h;
24     uint nIndex;
25     Bucket *p;
26    
27     IS_CONSISTENT(ht);
28    
29     h = zend_inline_hash_func(arKey, nKeyLength);
30     nIndex = h & ht->nTableMask;
31    
32     p = ht->arBuckets[nIndex];
33     while (p != NULL) {
34         if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
35             if (!memcmp(p->arKey, arKey, nKeyLength)) {
36                 *pData = p->pData;
37                 return SUCCESS;
38             }
39         }
40         p = p->pNext;
41     }
42     return FAILURE;
43 }

其中zend_hash_index_find用于查找整数key的情况，zend_hash_find用于查找字符串key。逻辑基本一致，只是字符串key会通过zend_inline_hash_func转为整数key，zend_inline_hash_func封装了times33算法，具体代码就不贴出了。

攻击

知道了PHP内部哈希表的算法，就可以利用其原理构造用于攻击的数据。一种最简单的方法是利用掩码规律制造碰撞。上文提到Zend HashTable的长度nTableSize会被圆整为2的整数次幂，假设我们构造一个2^16的哈希表，则nTableSize的二进制表示为：1 0000 0000 0000 0000，而nTableMask = nTableSize – 1为：0 1111 1111 1111 1111。接下来，可以以0为初始值，以2^16为步长，制造足够多的数据，可以得到如下推测：

view source
 
print?
01 0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
02   
03 0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
04   
05 0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
06   
07 0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
08   
09 0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
10   
11 ……

概况来说只要保证后16位均为0，则与掩码位于后得到的哈希值全部碰撞在位置0。下面是利用这个原理写的一段攻击代码：

view source
 
print?
01 <?php
02 $size = pow(2, 16);
03 $startTime = microtime(true);
04    
05 $array = array();
06 for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
07     $array[$key] = 0;
08 }
09    
10 $endTime = microtime(true);
11 echo $endTime - $startTime, ' seconds', "\n";
12 ?>

这段代码在我的VPS上（单CPU，512M内存）上用了近88秒才完成，并且在此期间CPU资源几乎被用尽。

而普通的同样大小的哈希表插入仅用时0.036秒：

view source
 
print?
01 <?php
02 $size = pow(2, 16);
03 $startTime = microtime(true);
04    
05 $array = array();
06 for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $size; $key += 1) {
07     $array[$key] = 0;
08 }
09    
10 $endTime = microtime(true);
11 echo $endTime - $startTime, ' seconds', "\n";
12 ?>

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

当然，一般情况下很难遇到攻击者可以直接修改PHP代码的情况，但是攻击者仍可以通过一些方法间接构造哈希表来进行攻击。例如PHP会将接收到的HTTP POST请求中的数据构造为$_POST，而这是一个Array，内部就是通过Zend HashTable表示，因此攻击者只要构造一个含有大量碰撞key的post请求，就可以达到攻击的目的。具体做法不再演示。

防御

POST攻击的防护：针对POST方式的哈希碰撞攻击，目前PHP的防护措施是控制POST数据的数量。在>=PHP5.3.9的版本中增加了一个配置项max_input_vars，用于标识一次http请求最大接收的参数个数，默认为1000。因此PHP5.3.x的用户可以通过升级至5.3.9来避免哈希碰撞攻击。5.2.x的用户可以使用这个patch：http://www.laruence.com/2011/12/30/2440.html。

另外的防护方法是在Web服务器层面进行处理，例如限制http请求body的大小和参数的数量等，这个是现在用的最多的临时处理方案。具体做法与不同Web服务器相关，不再详述。

上面的防护方法只是限制POST数据的数量，而不能彻底解决这个问题。例如，如果某个POST字段是一个json数据类型，会被PHP json_decode，那么只要构造一个超大的json攻击数据照样可以达到攻击目的。理论上，只要PHP代码中某处构造Array的数据依赖于外部输入，则都可能造成这个问题，因此彻底的解决方案要从Zend底层HashTable的实现动手。一般来说有两种方式，一是限制每个桶链表的最长长度；二是使用其它数据结构如红黑树取代链表组织碰撞哈希（并不解决哈希碰撞，只是减轻攻击影响，将N个数据的操作时间从O(N^2)降至O(NlogN)，代价是普通情况下接近O(1)的操作均变为O(logN)）。

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

延伸阅读

此文章所在专题列表如下：

  1. PHP内核探索：从SAPI接口开始
  2. PHP内核探索：一次请求的开始与结束
  3. PHP内核探索：一次请求生命周期
  4. PHP内核探索：单进程SAPI生命周期
  5. PHP内核探索：多进程/线程的SAPI生命周期
  6. PHP内核探索：Zend引擎
  7. PHP内核探索：再次探讨SAPI
  8. PHP内核探索：Apache模块介绍
  9. PHP内核探索：通过mod_php5支持PHP
  10. PHP内核探索：Apache运行与钩子函数
  11. PHP内核探索：嵌入式PHP
  12. PHP内核探索：PHP的FastCGI
  13. PHP内核探索：如何执行PHP脚本
  14. PHP内核探索：PHP脚本的执行细节
  15. PHP内核探索：操作码OpCode
  16. PHP内核探索：PHP里的opcode
  17. PHP内核探索：解释器的执行过程
  18. PHP内核探索：变量概述
  19. PHP内核探索：变量存储与类型
  20. PHP内核探索：PHP中的哈希表
  21. PHP内核探索：理解Zend里的哈希表
  22. PHP内核探索：PHP哈希算法设计
  23. PHP内核探索：翻译一篇HashTables文章
  24. PHP内核探索：哈希碰撞攻击是什么？
  25. PHP内核探索：常量的实现
  26. PHP内核探索：变量的存储
  27. PHP内核探索：变量的类型
  28. PHP内核探索：变量的值操作
  29. PHP内核探索：变量的创建
  30. PHP内核探索：预定义变量
  31. PHP内核探索：变量的检索
  32. PHP内核探索：变量的类型转换
  33. PHP内核探索：弱类型变量的实现
  34. PHP内核探索：静态变量的实现
  35. PHP内核探索：变量类型提示
  36. PHP内核探索：变量的生命周期
  37. PHP内核探索：变量赋值与销毁
  38. PHP内核探索：变量作用域
  39. PHP内核探索：诡异的变量名
  40. PHP内核探索：变量的value和type存储
  41. PHP内核探索：全局变量Global
  42. PHP内核探索：变量类型的转换
  43. PHP内核探索：内存管理开篇
  44. PHP内核探索：Zend内存管理器
  45. PHP内核探索：PHP的内存管理
  46. PHP内核探索：内存的申请与销毁
  47. PHP内核探索：引用计数与写时复制
  48. PHP内核探索：PHP5.3的垃圾回收机制
  49. PHP内核探索：内存管理中的cache
  50. PHP内核探索：写时复制COW机制
  51. PHP内核探索：数组与链表
  52. PHP内核探索：使用哈希表API
  53. PHP内核探索：数组操作
  54. PHP内核探索：数组源码分析
  55. PHP内核探索：函数的分类
  56. PHP内核探索：函数的内部结构
  57. PHP内核探索：函数结构转换
  58. PHP内核探索：定义函数的过程
  59. PHP内核探索：函数的参数
  60. PHP内核探索：zend_parse_parameters函数
  61. PHP内核探索：函数返回值
  62. PHP内核探索：形参return value
  63. PHP内核探索：函数调用与执行
  64. PHP内核探索：引用与函数执行
  65. PHP内核探索：匿名函数及闭包
  66. PHP内核探索：面向对象开篇
  67. PHP内核探索：类的结构和实现
  68. PHP内核探索：类的成员变量
  69. PHP内核探索：类的成员方法
  70. PHP内核探索：类的原型zend_class_entry
  71. PHP内核探索：类的定义
  72. PHP内核探索：访问控制
  73. PHP内核探索：继承，多态与抽象类
  74. PHP内核探索：魔术函数与延迟绑定
  75. PHP内核探索：保留类与特殊类
  76. PHP内核探索：对象
  77. PHP内核探索：创建对象实例
  78. PHP内核探索：对象属性读写
  79. PHP内核探索：命名空间
  80. PHP内核探索：定义接口
  81. PHP内核探索：继承与实现接口
  82. PHP内核探索：资源resource类型
  83. PHP内核探索：Zend虚拟机
  84. PHP内核探索：虚拟机的词法解析
  85. PHP内核探索：虚拟机的语法分析
  86. PHP内核探索：中间代码opcode的执行
  87. PHP内核探索：代码的加密与解密
  88. PHP内核探索：zend_execute的具体执行过程
  89. PHP内核探索：变量的引用与计数规则
  90. PHP内核探索：新垃圾回收机制说明

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
PHP后门一句话-汇总发布时间：2022-07-10
下一篇：
PHP程序的常见漏洞攻击分析发布时间：2022-07-10
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap