科技类公司网站设计,雍熙网站建设,合肥软件公司排名,建设电子商务网站所应用的技术一、哈希表碰撞攻击的基本原理
哈希表是一种查找效率极高的数据结构#xff0c;很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构#xff0c;不但用于表示Array数据类型#xff0c;还在Zend虚拟机内部用于存储上下文环境信息#xff08;执行上下文的…一、哈希表碰撞攻击的基本原理
哈希表是一种查找效率极高的数据结构很多语言都在内部实现了哈希表。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那基本就没戏了幸运的是也可以说不幸的是大多数编程语言使用的哈希算法都十分简单这是为了效率考虑因此可以不费吹灰之力之力构造出攻击数据。
二、如何防御 打补丁修改hash算法。 限制POST的参数个数限制POST的请求长度。 使用防火墙检测异常请求 增加权限验证最大可能的在jsonDecode()之前把非法用户拒绝 重写jsonDecode()方法
分享一个可以导致hash碰撞的json串https://raw.githubusercontent.com/laynefyc/php_thread_demo/master/javaHash.json
