青年|没想到 Hash 冲突还能这么玩，你的服务中招了吗？ |中年|中招|

本文插图

图源：石头
背景其实这个问题我之前也看到过，刚好在前几天，洪教授在某个群里分享的一个《一些有意思的攻击手段.pdf》，我觉得这个话题应该还是有不少人不清楚的，今天我就准备来“实战”一把，还请各位看官轻拍。
洪强宁（洪教授），爱因互动创始人兼 CTO ，曾任豆瓣首席架构师，为中国 Python 用户组（CPUG）的创立者之一。

本文插图

Hash 冲突啥叫 Hash 冲突？我们从 Hash 表（或者散列表）讲起，我们知道在一个 hash 表的查找一个元素，期望的时间复杂度为 O(1) ，怎么做到的呢？其实就是 hash 函数在起作用。
初略来讲， hash 表内部实际存储还是跟数组类似，用连续的内存空间存储元素，只要通过某种方法将将要存储的元素映射为数组的下标，即可像数组一样通过下标去读取对应的元素，这也是为什么能做到 O(1) 的原因。

本文插图

Hash 示例
以上图为例，假设是我设计的一个 hash 函数，恰好满足如下条件：

hash("hello")=0：字符串 "hello" 就存储数组下标为 0 的地方；
hash("world")=2："world" 存储数组下标为 2 的地方；

hash("tangleithu")=5："tangleithu" 存储数组下标为 5 的地方；

本文插图

目前来看一切好像很完美，但这终归是假设，我不能假设这个 hash 都很完美的将不同的字符串都映射到了不同的下标处。
另外来了个字符串， hash("石头") = 2 ，怎么办？这就是所谓的 “Hash 冲突” ，最常见 Hash 冲突的解决方案其实就是“开链”法，其实还有比如线性试探、平方试探等等。
类似讲解 HashMap 的文章满大街都是，一搜一大把，本文就不详述了。为了方便读者理解，就简单来个例子。

本文插图

Hash冲突开链法
开链法如上图所示，我们存储元素的时候，存储形式为一个链表，当冲突的时候，就在链表末尾直接添加冲突的元素。上图示例恰好运气比较差，字符串 shitou ， stone 算出来的下标都为 2 。
这样一来，问题大了。原本我们期望 O(1) 的时间复杂度查找元素，现在变成在链表中线性查找了，而如果这个时候插入N个数据，最坏的情况下的时间复杂度就是
了。（这里就不讨论链表转树的情形）

本文插图

坏人可乘机而入

这就又给坏人留下了想象空间。只要坏人精心设计一组要放进 hash 表的字符串，且让这些字符串的 hashcode 都一样，这就会导致 hash 冲突，结果会导致 cpu 要花费大量的时间来处理 hash 冲突，造成 DoS（Denial of Service）攻击。
而用 hash 表存储的情形太常见了。在 Web 服务中，一般表单的处理都是用 hash 表来保存的（后端往往要知道通过某个具体的参数 key 获取对应的参数 value）。
实战本文石头哥将以 Java SpringBoot 为例，尝试进行一次攻击。
不过别以为这种 “Hash 冲突 DoS” 以为只有 Java 才有哦，什么 Python ， Apache Tomcat/Jetty ， PHP 之类都会有这个问题的。其实早在 2011 年年末的时候就被大量爆出了，有的框架陆陆续续有一些改进和修复。详细情况可以看这篇文章：oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision[1] 。