位置: 编程技术 - 正文

PHP内核探索:哈希表碰撞攻击原理(深入理解php内核)

编辑:rootadmin

推荐整理分享PHP内核探索:哈希表碰撞攻击原理(深入理解php内核),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:php内核源码,php 核心,深入理解php内核,php 核心,深入理解php内核,php7内核,php内核剖析,php内核剖析,内容如对您有帮助,希望把文章链接给更多的朋友!

下面通过图文并茂的方式给大家展示PHP内核探索:哈希表碰撞攻击原理。

最近哈希表碰撞攻击(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中正常哈希表和退化哈希表的示意图。

Notice: Undefined index: CMSdown in /data/webroot/gcms/lib/Api/Open/Article.php on line img////_d3fede.jpg" alt="查看图片" />

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

可以看到,进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞,如果是MD5或者SHA1那基本就没戏了,幸运的是(也可以说不幸的是)大多数编程语言使用的哈希算法都十分简单(这是为了效率考虑),因此可以不费吹灰之力之力构造出攻击数据。下一节将通过分析Zend相关内核代码,找出攻击哈希表碰撞攻击PHP的方法。Zend哈希表的内部实现 数据结构 PHP中使用一个叫Backet的结构体表示桶,同一哈希值的所有桶被组织为一个单链表。哈希表使用HashTable结构体表示。相关源码在zend/Zend_hash.h下:

字段名很清楚的表明其用途,因此不做过多解释。重点明确下面几个字段:Bucket中的“h”用于存储原始key;HashTable中的nTableMask是一个掩码,一般被设为nTableSize - 1,与哈希算法有密切关系,后面讨论哈希算法时会详述;arBuckets指向一个指针数组,其中每个元素是一个指向Bucket链表的头指针。 哈希算法 PHP哈希表最小容量是8(2^3),最大容量是0×(2^),并向2的整数次幂圆整(即长度会自动扩展为2的整数次幂,如个元素的哈希表长度为;个元素的哈希表长度为)。nTableMask被初始化为哈希表长度(圆整后)减1。具体代码在zend/Zend_hash.c的_zend_hash_init函数中,这里截取与本文相关的部分并加上少量注释。

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

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

即简单将数据的原始key与HashTable的nTableMask进行按位与即可。

如果原始key为字符串,则首先使用 Times 算法将字符串转为整形再与nTableMask按位与。

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

其中zend_hash_index_find用于查找整数key的情况,zend_hash_find用于查找字符串key。逻辑基本一致,只是字符串key会通过zend_inline_hash_func转为整数key,zend_inline_hash_func封装了times算法,具体代码就不贴出了。 攻击 基本攻击 知道了PHP内部哈希表的算法,就可以利用其原理构造用于攻击的数据。一种最简单的方法是利用掩码规律制造碰撞。上文提到Zend HashTable的长度nTableSize会被圆整为2的整数次幂,假设我们构造一个2^的哈希表,则nTableSize的二进制表示为:1 ,而nTableMask = nTableSize - 1为:0 。接下来,可以以0为初始值,以2^为步长,制造足够多的数据,可以得到如下推测:

& 0 = 0

PHP内核探索:哈希表碰撞攻击原理(深入理解php内核)

& 0 = 0

& 0 = 0

& 0 = 0

& 0 = 0

……

概况来说只要保证后位均为0,则与掩码位于后得到的哈希值全部碰撞在位置0。

下面是利用这个原理写的一段攻击代码:

这段代码在我的VPS上(单CPU,M内存)上用了近秒才完成,并且在此期间CPU资源几乎被用尽:

Notice: Undefined index: CMSdown in /data/webroot/gcms/lib/Api/Open/Article.php on line img////_d3fed.jpg" alt="查看图片" />

Notice: Undefined index: CMSdown in /data/webroot/gcms/lib/Api/Open/Article.php on line img////_d3fedb.jpg" alt="查看图片" />

而普通的同样大小的哈希表插入仅用时0.秒:

Notice: Undefined index: CMSdown in /data/webroot/gcms/lib/Api/Open/Article.php on line img////_d3fed6d0dbf.jpg" alt="查看图片" />

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

POST攻击

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

防护 POST攻击的防护

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

另外的防护方法是在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均进行升级或打补丁。至于从数据结构层面修复这个问题,目前还没有任何方面的消息。

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

如何使用纯PHP实现定时器任务(Timer) 定时器任务,在WEB应用比较常见,如何使用PHP实现定时器任务,大致有两种方案:1)使用Crontab命令,写一个shell脚本,在脚本中调用PHP文件,然后定期执

如何把php5.3版本升级到php5.4或者php5.5 今天我们这篇php的技术文章主要为各位朋友们介绍如何使用yum进行安装php的5.4或者5.5版本。当然我们使用centos6.5作为我们的测试机器。其实非常简单,

详解Grunt插件之LiveReload实现页面自动刷新(两种方案) 方案一:grunt-livereload+ChromePlug-in优点:安装、配置简单方便。缺点:需要配合指定的浏览器插件(Firefox也有相关插件,IE么你懂的)。1.需要安装2个插

标签: 深入理解php内核

本文链接地址:https://www.jiuchutong.com/biancheng/284466.html 转载请保留说明!

上一篇:php数字运算验证码的实现代码(php制作数字验证码)

下一篇:如何使用纯PHP实现定时器任务(Timer)(php做)

  • 个税系统里的收入包括什么
  • 会计科目长期待摊费用跟累计折旧分别是什么意思
  • 增值税申报表第25行怎么填
  • 低值易耗品包括哪些东西和产品
  • 印花税计税基数不包括哪些
  • 技术服务费属于哪个商品编码
  • 出售已使用固定资产增值税申报表
  • 票据利息科目怎么设置
  • 建筑企业劳保计入哪个科目?
  • 地质灾害评估费收费标准
  • 在建工程预付款项记入什么会计科目
  • 代理手续费税收分类编码
  • 七月一号出台的什么政策
  • 销售营改增之后取得的固定资产
  • 小微企业免征增值税报表填写
  • 企业清算企业所得税税率
  • 发票超过标准可以报销吗
  • 税控服务系统
  • 进项税期末有余额吗
  • 制造企业材料返回流程图
  • 分公司用总公司盖章说明
  • 公转私限额多久自动解冻
  • 免税单位无租使用房产怎么缴纳房产税
  • 对公账户是否有银行卡号
  • 电脑管家浏览器保护怎么取消
  • 社保费税前扣还是税后扣
  • thinkphp框架介绍
  • 建筑工程团体意外险
  • rteng7.exe - rteng7是什么进程 有什么用
  • Http请求-hutool工具类的使用
  • 贵的u盘和便宜的有什么区别
  • 处理固定资产时的账务处理
  • 外贸企业出口退税流程(详细步骤)
  • 日落时有什么变化
  • php中获取当前时间
  • php 替换
  • 这年头不好混图片
  • 在vue3项目中使用vue2
  • python处理mysql如何拿到表头
  • 劳动仲裁支付的赔偿金怎么入账
  • 增值税在纳税申报表中怎么得出
  • 企业收入总额的计算公式
  • 个体户开普票有没有完税证明
  • php swoole 协程
  • 怎么算长期合同
  • centos7.0安装
  • 收到保险赔款入什么科目
  • 人工安装费是几个点税税率
  • 占地面积法如何分摊土地成本
  • 销售折扣单独开发票
  • mongodb查询操作
  • 资本公积可以转增资本因此称之为准资本
  • 发行股票的好处和坏处
  • 股权收购协议书实际案例
  • 小规模减免税款会计分录
  • 预付工程款会计分录
  • 经营性应收项目和经营性应付项目
  • u盘安装win8.1系统教程
  • windows电脑加速
  • ubuntu fsl
  • 磁盘清理win10
  • Mac系统中使用QuickTime Player实现屏幕录像图文教程
  • win10专业版怎么安装
  • WindowsPE与WindowsRE有什么区别
  • win8.1快捷键
  • executor进程
  • win8系统出现闪屏
  • javaScript基础语法数据类型
  • unityz
  • javascript零基础
  • shell命令tee
  • time(0)函数
  • css中有序列表
  • 去掉字符串中的某个值
  • 契税减免优惠政策2023年最新
  • 电子税务局在手机上能登录吗
  • 成都税务局发票查询
  • 深圳市国家税务局电子税务局
  • 进项税销项税抵扣公式
  • 税务实名认证如何操作
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设