PHP哈希表碰撞攻击原理

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

<?php 
 
 
$size = pow(2, 16); 
 
$startTime = microtime(true); 
 
$array = array(); 
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $size; $key += 1) { 
   $array[$key] = 0; 
} 
 
$endTime = microtime(true); 
 
echo $endTime - $startTime, ' seconds', "\n";

可以证实第二段代码插入N个元素的时光在O(N)程度，而第一段进击代码则需O(N^2)的时光去插入N个元素。

如不雅原始key为字符串，则起首应用Times33算法将字符串转为整形再与nTableMask按位与。

POST进击

当然，一般情况下很难碰到进击者可以直接修改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数据类型，会被PHPjson_decode，那么只要结垢荷琐超大年夜的json进击数据照样可以达到进击目标。理论上，只要PHP代码中某处构造Array的数据依附于外部输入，则都可能造成这个问题，是以彻底的解决筹划要大年夜Zend底层HashTable的实现着手。一般来说有两种方法，一是限制每个桶链表的最长长度;二是应用其它数据构造如红黑树代替链表组织碰撞哈希(并不解决哈希碰撞，只是减轻进击影响，将N个数据的操作时光大年夜O(N^2)降至O(NlogN)，价值是通俗情况下接近O(1)的操作均变为O(logN))。

今朝应用最多的仍然是POST数据进击，是以建议临盆情况的PHP均进行进级或打补丁。至于大年夜数据构造层面修复这个问题，今朝还没有任何方面的消息。

参考

[1] Supercolliding a PHP array

[2] PHP5.2.*防止Hash冲突拒绝办事进击的Patch

[4] PHP数组的Hash冲突实例

[5] PHP 5.4.0 RC4 released

【编辑推荐】

关于PHP的缺点机制总结
PHP协程实现过程详解
大年夜0开端构建一个属于你本身的PHP框架
PHP与Golang若何通信？
PHP底层的运行机制与原懂得析

【义务编辑：枯木 TEL：（010）68476606】

4/4 首页上一页 2 3 4

　　推荐阅读

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

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

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

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

1/2 1