PHP 数组的哈希碰撞攻击

1、攻击测试

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

HashTable 之对 PHP数组的go

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

HashTable 之对 PHP数组的go

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

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,作用为:
    HashTable 之对 PHP数组的go
  • 加入随机 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 的请求处理

    • PHP 数组的哈希碰撞攻击

    • PHP 数组的哈希碰撞攻击

    • PHP 数组的哈希碰撞攻击

    • PHP 数组的哈希碰撞攻击

    • PHP 数组的哈希碰撞攻击
      PHP 数组的哈希碰撞攻击

最后

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

PHP 数组的哈希碰撞攻击

PHP 数组的哈希碰撞攻击

PHP 数组的哈希碰撞攻击

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

本作品采用《CC 协议》,转载必须注明作者和本文链接
附言 1  ·  2年前

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

本帖由系统于 2年前 自动加精
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 12

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

2年前 评论
lidongyoo (楼主) 2年前
michonnehsu 2年前
wavebossy6666 2年前
lidongyoo (楼主) 2年前
wavebossy6666 2年前
sreio

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

2年前 评论

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

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

2年前 评论
lidongyoo (楼主) 2年前
lidongyoo (楼主) 2年前
seth-shi (作者) 2年前
seth-shi (作者) 2年前
lidongyoo (楼主) 2年前
seth-shi (作者) 2年前
Diudiuuuu 2年前
Diudiuuuu 2年前
seth-shi (作者) 2年前

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

2年前 评论
lidongyoo (楼主) 2年前
wavebossy6666 (作者) 2年前
    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))
    }
2年前 评论
playmaker 2年前
Diudiuuuu 2年前

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

2年前 评论
lidongyoo (楼主) 2年前
Latent (作者) 2年前
lidongyoo (楼主) 2年前
wavebossy6666 2年前

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

2年前 评论
lidongyoo (楼主) 2年前
小李世界 (作者) 2年前
爱学习的胖鼠 2年前
小李世界 (作者) 2年前

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

2年前 评论
lidongyoo (楼主) 2年前
wdnmd (作者) 2年前

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

  1. 创建 Request 类
<?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);
    }
}
  1. 将 public/index.php 中的
use Illuminate\Http\Request;

替换为

use App\Http\Request;
2年前 评论
Diudiuuuu 2年前
Vanry (作者) 2年前

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

2年前 评论

php的 基于workermanwebman框架测试没有 :flushed:

2年前 评论

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