江苏龙网

  1. 首页 > 人文 > >

产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到


产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
图源：石头
背景其实这个问题我之前也看到过 ， 刚好在前几天 ， 洪教授在某个群里分享的一个《一些有意思的攻击手段.pdf》 ， 我觉得这个话题应该还是有不少人不清楚的 ， 今天我就准备来“实战”一把 ， 还请各位看官轻拍 。
洪强宁（洪教授） ， 爱因互动创始人兼CTO ， 曾任豆瓣首席架构师 ， 为中国Python用户组（CPUG）的创立者之一 。
产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
Hash冲突啥叫Hash冲突？我们从Hash表（或者散列表）讲起 ， 我们知道在一个hash表的查找一个元素 ， 期望的时间复杂度为O(1) ， 怎么做到的呢？其实就是hash函数在起作用 。
初略来讲 ， hash表内部实际存储还是跟数组类似 ， 用连续的内存空间存储元素 ， 只要通过某种方法将将要存储的元素映射为数组的下标 ， 即可像数组一样通过下标去读取对应的元素 ， 这也是为什么能做到O(1)的原因 。
产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
Hash示例
以上图为例 ， 假设是我设计的一个hash函数 ， 恰好满足如下条件：
hash("hello")=0：字符串"hello"就存储数组下标为0的地方；
hash("world")=2："world"存储数组下标为2的地方；
更多内容↓↓↓hash("tangleithu")=5："tangleithu"存储数组下标为5的地方；
产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
目前来看一切好像很完美 ， 但这终归是假设 ， 我不能假设这个hash都很完美的将不同的字符串都映射到了不同的下标处 。
另外来了个字符串 ， hash("石头")=2 ， 怎么办？这就是所谓的“Hash冲突” ， 最常见Hash冲突的解决方案其实就是“开链”法 ， 其实还有比如线性试探、平方试探等等 。
类似讲解HashMap的文章满大街都是 ， 一搜一大把 ， 本文就不详述了 。 为了方便读者理解 ， 就简单来个例子 。
产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
Hash冲突开链法
开链法如上图所示 ， 我们存储元素的时候 ， 存储形式为一个链表 ， 当冲突的时候 ， 就在链表末尾直接添加冲突的元素 。 上图示例恰好运气比较差 ， 字符串shitou ， stone算出来的下标都为2 。
这样一来 ， 问题大了 。 原本我们期望O(1)的时间复杂度查找元素 ， 现在变成在链表中线性查找了 ， 而如果这个时候插入N个数据 ， 最坏的情况下的时间复杂度就是
了 。 （这里就不讨论链表转树的情形）
产业气象站|Hash 冲突还能这么玩，你的服务中招了吗？，没想到
文章图片
坏人可乘机而入
这就又给坏人留下了想象空间 。 只要坏人精心设计一组要放进hash表的字符串 ， 且让这些字符串的hashcode都一样 ， 这就会导致hash冲突 ， 结果会导致cpu要花费大量的时间来处理hash冲突 ， 造成DoS（DenialofService）攻击 。
而用hash表存储的情形太常见了 。 在Web服务中 ， 一般表单的处理都是用hash表来保存的（后端往往要知道通过某个具体的参数key获取对应的参数value） 。
实战本文石头哥将以JavaSpringBoot为例 ， 尝试进行一次攻击 。
不过别以为这种“Hash冲突DoS”以为只有Java才有哦 ， 什么Python ， ApacheTomcat/Jetty ， PHP之类都会有这个问题的 。 其实早在2011年年末的时候就被大量爆出了 ， 有的框架陆陆续续有一些改进和修复 。 详细情况可以看这篇文章：oCERT-2011-003multipleimplementationsdenial-of-serviceviahashalgorithmcollision[1] 。


推荐阅读


上一篇：数码小王|EOS R5 等新品威武亮相，真香现场：佳能

下一篇：产业气象站|无需用户交互即可传播，微软发现最高等级“可蠕虫”漏洞