PHP 数组的哈希碰撞攻击

lidongyoo 的个人博客 / 11 / 12 / 创建于 3年前 / 更新于 3年前

1、攻击测试

先拿 Laravel 试试~~ 我拉了一个最新版本 v8.5.15

HashTable 之对 PHP数组的go

HashTable 之对 PHP数组的go
可以看到这个请求竟然花了27秒！
再来试试传入正常的数据是怎样的：

HashTable 之对 PHP数组的go

HashTable 之对 PHP数组的go
只用了200毫秒，可以得出结论这个攻击在 Laravel 里是奏效的~ 当然也不能怪 Laravel，这个锅 PHP 背，为什么呢？(如果服务器突然 CPU 飙升站长大人不要打我)

2、HashTable

之前一直知道 PHP 的数组其实就是 HashTable，但没有深入去研究，直到昨天看见鸟哥的一篇文章 PHP数组的Hash冲突实例拿里面的代码去跑了跑竟然在今天依然有效~ 我当时也是懵的。。我的本地 PHP版本：

HashTable 之对 PHP数组的go

攻击原理（简单介绍）

更详细的介绍可以看看这篇帖子：什么是哈希洪水攻击（Hash-Flooding Attack）？
首先任何 Hash Function 都会有哈希冲突的问题，所以一般解决冲突的办法有以下三种

开放寻址方法
拉链法(到达一定的长度之后可以转换为红黑树提高性能，Java 目前就是这样做的，PHP 目前并没有)
重哈希法

PHP 采用的就是【拉链法】，将冲突的 Bucket 串成链表，在取数据时通过散列函数定位到对应的 Bucket 链表然后遍历链表，逐个对比 Key 值直到找出目标元素。
而这段代码就是将 PHP 的 HashTable 退化成了链表，使每次插入的平均时间度变成了 O(n)
那为什么上面那段代码会奏效呢？引用自 PHP数组的Hash冲突实例：

这样在每次插入的时候PHP都需要遍历一遍这个链表, 大家可以想象, 第一次插入, 需要遍历0个元素, 第二次是1个, 第三次是3个, 第65536个是65535个, 那么总共就需要65534*65535/2=2147385345次遍历….
在PHP中，如果键值是数字，那么Hash的时候就是数字本身, 一般的时候都是 index & tableMask，而tableMask是用来保证数字索引不会超出数组可容纳的元素个数值, 也就是数组个数-1。
PHP的Hashtable的大小都是2的指数，比如如果你存入10个元素的数组，那么数组实际大小是16，如果存入20个，则实际大小为32，而63个话，实际大小为64。当你的存入的元素个数大于了数组目前的最多元素个数的时候，PHP会对这个数组进行扩容，并且从新Hash。
现在，我们假设要存入64个元素(中间可能会经过扩容，但是我们只需要知道，最后的数组大小是64，并且对应的tableMask为63:0111111)，那么如果第一次我们存入的元素的键值为0，则hash后的值为0，第二次我们存入64，hash(1000000 & 0111111)的值也为0，第三次我们用128，第四次用192… 就可以使得底层的 PHP 数组把所有的元素都 Hash 到0号 bucket 上, 从而使得 Hash 表退化成链表了.
当然, 如果键值是字符串的话, 就稍微比较麻烦一些了, 但是 PHP 的 Hash 算法是开源的, 已知的, 所以有心人也可以做到…

怎么避免

PHP 在5.4版本加入了一个配置参数：max_input_vars，作用为:
加入随机 salt（目前来看PHP并没有加入？有大佬解一下惑吗~）
为此我特意用 PHP 仿写了一个数组结构,里面有加入 salt 元素，感兴趣的朋友可以看看： PHP-HashTable
具体原理还是这篇第一个高赞回答：www.zhihu.com/question/286529973

3、为什么 Laravel 会中招

在上面可以看到 max_input_vars 似乎只对 $_GET $_POST $_COOKIE 这三个超全局变量生效。
在今天前后端分离的开发模式下大部分传输类型头都采用 Content-Type : Application/Json 来进行数据的传输，而 $_POST 只能获取 Content-Type 为 application/x-www-form-urlencoded 或者 multipart/form-data 的数据 php://input vs $_POST，这个时候想要获取 POST 数据你必须使用 file_get_contents(“php://input”) 来获取原始数据，获取原始数据之后再使用 json_decode($data, true) 转换为数组，只要经过这步就已经中招了~~
而 Laravel 为了让大家开箱即用对于任何类型数据都已经预先处理过了，而正是这些预先处理使得 Laravel 会被 100% 命中，下面看看 Laravel 对于 Content-Type: Application/Json 的请求处理

最后

目前来看并不是只有 Laravel 有这样的问题，只要用了 PHP 就可能有这个风险~~
最后看下我测自己服务器的情况

PHP 数组的哈希碰撞攻击

可以发现只需极少的成本就能打垮服务器~

本作品采用《CC 协议》，转载必须注明作者和本文链接

附言 1 · 3年前

各位请务必别拿这段代码去恶意攻击~

本帖由系统于 3年前自动加精

let size= Math.pow(2, 16) let data = {} let maxKey = (size- 1) * size for (let key = 0; key <= maxKey; key += size){ data[key] = key; } for (let i = 0; i < 50; i++){ let xhr = new XMLHttpRequest() xhr.open("POST", "/") xhr.setRequestHeader("Content-Type", "application/json;charset=UTF-8") xhr.send(JSON.stringify(data)) }

<?php namespace App\Http; use Illuminate\Http\Request as HttpRequest; use Illuminate\Support\Str; use Symfony\Component\HttpFoundation\ParameterBag; class Request extends HttpRequest { // 根据实际情况调整长度 const JSON_MAX_LENGTH = 65535; public function json($key = null, $default = null) { if (! isset($this->json)) { $content = $this->getContent(); $parameters = Str::length($content) > static::JSON_MAX_LENGTH ? [] : (array) json_decode($content, true); $this->json = new ParameterBag($parameters); } if (is_null($key)) { return $this->json; } return data_get($this->json->all(), $key, $default); } }

讨论数量: 12

Tacks

课程读者 495 声望

那么如何预防这种请求呢，PHP7以下的版本

3年前评论

lidongyoo （楼主）

显然这题我不会~~但不管 PHP7 还是其他版本都会有这个问题

michonnehsu

去学c 然后把它学透，最后加入PHP内核开发组（狗头）

wavebossy6666

顶上去，同求解决方案

@wavebossy6666 似乎完美的解决方案只能从 PHP 内核方面来着手，就像我上面说的加入随机元素

@lidongyoo 攻击方式简单粗暴，别的语言已经默认是有随机元素在里面，php不加就像光着屁股在走路了...

ZhanghuiMing

换成TreeMap gitee.com/mingzhanghui/map

sreio

课程读者 144 声望 / sreio @ Great and Unusual Technologies Ltd.

有没有大佬来讨论一下这个问题，坐等 :grin:

seth-shi

830 声望

搜了一下, 鸟哥貌似提过这个问题:+1: www.laruence.com/2011/12/30/2435.h...

预防就是直接 strlen 的数据大小即可. 或者在 php.ini 设置最大的 POST 数据

strlen 确实可以避免小数据传输情况下的攻击，但在 Laravel 中并没有做处理；
Laravel 中使用 php://input 来获取 json 数据，而 php://input 不受任何 php.ini 配置影响

@seth-shi json_decode($this->getContent(), true) 我在文章里有截图~

seth-shi （作者）

@lidongyoo 看到了，那就在 index.php 处理

@lidongyoo 自定义一个中间件处理

@seth-shi Laravel 还没运行至中间件阶段就已经处理了，所以只能改源码了~~[摊手]

@lidongyoo 你截图的代码只是获取内容，并没有解析 json ，应该可以处理的。即使中间件不可以处理，那在 index.php 也可以处理

Diudiuuuu

楼主说的对Laravel 中使用 php://input 来获取 json 数据，而 php://input 不受任何 php.ini 配置影响

亲测修改max_input_time 参数,laravel框架还是超时,除非在index.php前控制接收流式字符串长度.不过这个限制很不现实

@Yoooooo 看我说的, 直接在 index.php 入口文件获取到 json 的内容, 然后判断

课程读者 86 声望

就突然，想要那一段js代码自己试一下，麻烦发一下呗

不是吧带哥这么懒的吗，图片里不是有的呀

wavebossy6666 （作者）

@lidongyoo 如文章所描述，cpu直接满

Neymar

课程读者 63 声望

playmaker

试玩一下直接飙升去掉就消失了？

啊这,我手动都打完了,在这

Latent

Laravel 8.x 译者 524 声望

我用自己服务器也测试了一下直接跑完了...这

不用怀疑 100% 命中~~

Latent （作者）

@lidongyoo 用nginx做个请求数据大小限制应该就可以解决吧

@Latent 其实也不能完全解决，你限制了我传少一点数据就好了，最主要是能让你碰撞就行了~~但这至少不会让循环次数那么离谱

直接就吓坏了

小李世界

Laravel 8.x 译者 2.0k 声望 / Doge 先锋 @ dogeow.com

我的后面是 413，没有这个问题

那应该是请求还没到 Laravel 就被 block 了

小李世界（作者）

@lidongyoo 嗯，413 是 body 太大

爱学习的胖鼠

我本地一开始是413，数据量稍微少一点就能过nginx，cpu一下子就飙升了

@万能付博嗯，确实是会飙升的，我也是，所以我限制频率60次一分钟，当然管理员的另外配置。

wdnmd

课程读者 66 声望

如果使用node做中间，请求先到node那，然后在到php，用node进行一个过滤的话，应该可以解决

可以但没必要，用 HTTP 服务器限制一下更简单但这都是偏路子

wdnmd （作者）

@lidongyoo 是

Vanry

115 声望

可以改写 Request 类中的 json 方法，限制传入 json 的长度，将超过设定长度的数据丢弃。

创建 Request 类

将 public/index.php 中的

use Illuminate\Http\Request;

替换为

use App\Http\Request;

这个只能大概率限制,如果碰见有富文本框功能,数据库设置字段类型text类型,定义JSON_MAX_LENGTH =65535长度就需要有待商榷了

Vanry （作者）

@Yoooooo 这个只对 json 类型的请求进行处理，不影响表单请求，可以根据业务需求调整长度。

见习助教 85 声望

尝试了一下,针对laravel框架是没有办法解决这个问题

gyp719

课程读者 272 声望

这种攻击厉害了

码龍

课程读者 17 声望

php的基于workerman的webman框架测试没有

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

PHP 数组的哈希碰撞攻击

1、攻击测试

2、HashTable

攻击原理（简单介绍）

怎么避免

3、为什么 Laravel 会中招

最后

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

PHP 数组的哈希碰撞攻击

1、攻击测试

2、HashTable

攻击原理（简单介绍）

怎么避免

3、为什么 Laravel 会中招

最后

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录