资讯频道 → 编程语言
阅读更多

7顶
0踩

编程语言

转载新闻 关于Hash Collision DoS漏洞：解析与解决方案

2012-01-06 17:30 by 资深编辑 luiang1018 评论(5) 有14262人浏览
Hash Collision DoS Java
最近一个Hash Collision DoS（Hash碰撞的拒绝式服务攻击）漏洞影响颇大，有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比，本文试图对这一漏洞的原理及可采取措施做一解析，供大家参考。

一言蔽之，该安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样，但是key一样数据，然后让你的Hash表成为一张单向链表，而导致你的整个网站或是程序的运行性能以级数下降（可以很轻松地让你的CPU升到100%）。

目前，这个问题出现于Java、JRuby、PHP、Python、Rubinius、Ruby这些语言中，主要有：

  • Java，所有版本
  • JRuby <= 1.6.5（目前fix在 1.6.5.1）
  • PHP <= 5.3.8，<= 5.4.0RC3（目前fix在5.3.9、5.4.0RC4）
  • Python，所有版本
  • Rubinius，所有版本
  • Ruby <= 1.8.7-p356（目前fix在 1.8.7-p357、1.9.x）
  • Apache Geronimo，所有版本
  • Apache Tomcat <= 5.5.34，<= 6.0.34，<= 7.0.22（目前fix在 5.5.35、6.0.35、7.0.23）
  • Oracle Glassfish <= 3.1.1（目前fix在mainline）
  • Jetty，所有版本
  • Plone，所有版本
  • Rack <= 1.3.5, <= 1.2.4, <= 1.1.2 （目前fix 在 1.4.0、1.3.6、1.2.5、1.1.3）
  • V8 JavaScript Engine，所有版本
  • ASP.NET，没有打MS11-100补丁之前
注意，Perl没有这个问题，因为Perl在N年前就fix了这个问题了。关于这个列表的更新，请参看oCERT的2011-003报告。这个问题早在2003 年就在论文《通过算法复杂性进行拒绝式服务攻击》中被报告了，但是好像没有引起注意，尤其是Java。

弱点攻击解释

你可能会觉得这个问题没有什么大不了的，因为黑客看不到hash算法，如果你这么认为，那么你就错了，这说明对Web编程的了解还不足够底层。

无论你用JSP、PHP、Python、Ruby来写后台网页的时候，在处理HTTP POST数据的时候，你的后台程序可以很容易地以访问表单字段名来访问表单值，就像下面这段程序一样： 
$usrname = $_POST['username'];
$passwd = $_POST['password'];

这是怎么实现的呢？这后面的东西就是Hash Map啊，所以，我可以给你后台提交一个有10K字段的表单，这些字段名都被我精心地设计过，他们全是Hash Collision ，于是你的Web Server或语言处理这个表单的时候，就会建造这个hash map，于是在每插入一个表单字段的时候，都会先遍历一遍你所有已插入的字段，于是你的服务器的CPU一下就100%了，你会觉得这10K没什么，那么我就发很多个的请求，你的服务器一下就不行了。

举个例子，你可能更容易理解：

如果你有n个值—— v1, v2, v3, … vn，把他们放到hash表中应该是足够散列的，这样性能才高：
引用
    0 -> v2
    1 -> v4
    2 -> v1
    …
    …
    n -> v(x)

但是，这个攻击可以让我造出N个值——  dos1, dos2, …., dosn，他们的hash key都是一样的（也就是Hash Collision），导致你的hash表成了下面这个样子：
引用
    0 – > dos1 -> dos2 -> dos3 -> …. ->dosn
    1 -> null
    2 -> null
    …
    …
    n -> null

于是，单向链接就这样出现了。这样一来，O(1)的搜索算法复杂度就成了O(n)，而插入N个数据的算法复杂度就成了O(n^2)，你想想这是什么样的性能。

（关于Hash表的实现，如果你忘了，那就把大学时的《数据结构》一书拿出来看看）

Hash Collision DoS 详解

StackOverflow.com是个好网站，合格的程序员都应该知道这个网站。上去一查，就看到了这个贴子“Application vulnerability due to Non Random Hash Functions”。这里把这个贴子里的东西摘一些过来。

首先，这些语言使用的Hash算法都是“非随机的”，如下所示，这个是Java和Oracle使用的Hash函数： 
static int hash(int h)
{
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

所谓“非随机的” Hash算法，就可以猜。比如：

1）在Java里，Aa和BB这两个字符串的hash code（或hash key）是一样的，也就是Collision 。

2）于是，我们就可以通过这两个种子生成更多的拥有同一个hash key的字符串。如：”AaAa”, “AaBB”, “BBAa”, “BBBB”。这是第一次迭代。其实就是一个排列组合，写个程序就搞定了。

3）然后，我们可以用这4个长度的字符串，构造8个长度的字符串，如下所示：
引用

"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

4）同理，我们就可以生成16个长度的，以及256个长度的字符串，总之，很容易生成N多的这样的值。

在攻击时，我只需要把这些数据做成一个HTTP POST 表单，然后写一个无限循环的程序，不停地提交这个表单。你用你的浏览器就可以了。当然，如果做得更精妙一点的话，把你的这个表单做成一个跨站脚本，然后找一些网站的跨站漏洞，放上去，于是能过SNS的力量就可以找到N多个用户来帮你从不同的IP来攻击某服务器。

防御措施

要防守这样的攻击，可以尝试下面几招：

  • 打补丁，把hash算法改了。
  • 限制POST的参数个数，限制POST的请求长度。
  • 最好还有防火墙检测异常的请求。

来自: 酷壳
7
顶
0
踩
评论 共 5 条 请登录后发表评论
5 楼 whiletrue 2012-01-10 12:59
jindw 写道
xifo 写道
很想知道这个Hash算法应该怎么个改法。


static int r1 = Math.radom(); 

static int hash(int h)  {  
    h ^= (h >>> r1) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
 }


这样可行不？

用随机数好像还不错啊,不过会不会还很容易算出相同的hash码呢
4 楼 jindw 2012-01-09 13:36
xifo 写道
很想知道这个Hash算法应该怎么个改法。


static int r1 = Math.radom(); 

static int hash(int h)  {  
    h ^= (h >>> r1) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
 }


这样可行不？
3 楼 loookto 2012-01-08 13:19
xifo 写道
很想知道这个Hash算法应该怎么个改法。

+1
2 楼 whiletrue 2012-01-07 12:21
只要语言的hashcode计算是开源的,很容易就能造出类似的数据出来.
1 楼 xifo 2012-01-07 08:53
很想知道这个Hash算法应该怎么个改法。

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 关于Hash Collision DoS漏洞：web实例

    NULL 博文链接：https://goodscript.iteye.com/blog/1338973

  • Hash Collision DoS

    Hash Collision DoS事件及影响  Hash Collision DoS能让受攻击的服务器变得巨慢无比。 这不是因为服务器的编码原因或是疏忽造成的，而是程序语言自身的问题，Hash Collision DoS利用了各语言中Hash算法...

  • Hash Collision DoS 攻击

    Hash Collision DoS事件及影响  Hash Collision DoS能让受攻击的服务器变得巨慢无比。 这不是因为服务器的编码原因或是疏忽造成的，而是程序语言自身的问题，Hash Collision DoS利用了各语言中Hash算法的...

  • 资源工具分享（第1期）：后端架构师技术图谱

    容量评估 CDN 网络 连接池 性能调优 大数据 流式计算 Storm Flink Kafka Stream 应用场景 Hadoop HDFS MapReduce Yarn Spark 安全 web 安全 XSS CSRF SQL 注入 Hash Dos 脚本注入 漏洞扫描工具 验证码 DDoS 防范 ...

  • 后端架构师技术图谱

    Hash Dos 脚本注入 漏洞扫描工具 验证码 DDoS 防范 用户隐私信息保护 序列化漏洞 加密解密 对称加密 哈希算法 非对称加密 服务器安全 数据安全 ...

  • Find-Sec-Bugs 漏洞范例

    Find-Sec-Bugs 漏洞范例 欢迎使用Markdown编辑器 你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。 新的...

  • 从初级开发者到资深架构师，看这

    Hash Dos 脚本注入 漏洞扫描工具 验证码 DDoS 防范 用户隐私信息保护 序列化漏洞 加密解密 对称加密 哈希算法 非对称加密 服务器安全 数据安全 数据备份 网络隔离 内外网分离 登录跳板机 授权、认证 RBAC OAuth2.0 ...

  • 《后端架构师技术图谱》

    Hash Dos 脚本注入 漏洞扫描工具 验证码 DDoS 防范 用户隐私信息保护 序列化漏洞 加密解密 对称加密 哈希算法 非对称加密 服务器安全 数据安全 数据备份 网络隔离 内外网分离 登录跳板机 授权、认证 RBAC OAuth2.0 ...

  • java技术点

    容量评估 CDN 网络 连接池 性能调优 大数据 流式计算 Storm Flink Kafka Stream 应用场景 Hadoop HDFS MapReduce Yarn Spark 安全 web 安全 XSS CSRF SQL 注入 Hash Dos 脚本注入 漏洞扫描工具 验证码 DDoS 防范 ...

  • 基于Ssm和Vue的电影网站源码 电影网站代码（程序，中文注释）

    电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站-电影网站 1、资源说明：电影网站源码，本资源内项目代码都经过测试运行成功，功能ok的情况下才上传的。 2、适用人群：计算机相关专业(如计算计、信息安全、大数据、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工等学习者，作为参考资料，进行参考学习使用。 3、资源用途：本资源具有较高的学习借鉴价值，可以作为“参考资料”，注意不是“定制需求”，代码只能作为学习参考，不能完全复制照搬。需要有一定的基础，能够看懂代码，能够自行调试代码，能够自行添加功能修改代码。 4. 最新计算机软件毕业设计选题大全(文章底部有博主联系方式): https://blog.csdn.net/2301_79206800/article/details/135931154 技术栈、环境、工具、软件： ① 系统环境:Windows ② 开发语言：Java ③ 框架：Ssm ④ 架构:B/S、MVC ⑤ 开发环境:IDEA、JDK、Maven、Mysql ⑥ 数据库：mysql ⑦ 服

  • 基于微盾品牌的VwFirewall防火墙设计源码

    该项目为微盾品牌VwFirewall防火墙的完整设计源码，由342个文件组成，涵盖了多种编程语言和资源类型，包括55个头文件、40个GIF图像、34个ICO图标、33个C++源文件、27个PNG图片、21个BMP图像、19个PSD设计文件、12个数据文件、11个C源文件、8个可执行文件。该源码集合了C、C++、C、HTML、JavaScript和PHP等编程语言，适用于防火墙的安全防护设计开发。

  • 高校推免报名 基于Ssm和Mysql的高校推免报名代码（程序，中文注释）

    高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名-高校推免报名 1、资源说明：高校推免报名源码，本资源内项目代码都经过测试运行成功，功能ok的情况下才上传的。 2、适用人群：计算机相关专业(如计算计、信息安全、大数据、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工等学习者，作为参考资料，进行参考学习使用。 3、资源用途：本资源具有较高的学习借鉴价值，可以作为“参考资料”，注意不是“定制需求”，代码只能作为学习参考，不能完全复制照搬。需要有一定的基础，能够看懂代码，能够自行调试代码，能够自行添加功能修改代码。 4. 最新计算机软件毕业设计选题大全(文章底部有博主联系方式): https://blog.csdn.net/2301_79206800/article/details/135931154 技术栈、环境、工具、软件： ① 系统环境:Windows ② 开发语言：Java ③ 框架：Ssm ④ 架构:B/S、MVC ⑤ 开发环境:IDEA、JDK、M

  • 党务政务服务热线平台 基于Ssm和Mysql的党务政务服务热线平台代码（程序，中文注释）

    党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台-党务政务服务热线平台 1、资源说明：党务政务服务热线平台源码，本资源内项目代码都经过测试运行成功，功能ok的情况下才上传的。 2、适用人群：计算机相关专业(如计算计、信息安全、大数据、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工等学习者，作为参考资料，进行参考学习使用。 3、资源用途：本资源具有较高的学习借鉴价值，可以作为“参考资料”，注意不是“定制需求”，代码只能作为学习参考，不能完全复制照搬。需要有一定的基础，能够看懂代码，能够自行调试代码，能够自行添加功能修改代码。 4. 最新计算机软件毕业设计选题大全(文章底部有博主联系方式): https://blog.csdn.net/2301_79206800/article/details/135931154 技术栈、环境、工具、软件： ① 系统环境:Windows

  • 基于asp.net的教师工作量管理系统设计与实现.docx

    基于asp.net的教师工作量管理系统设计与实现.docx

  • ESG批发零售行业白皮书

    ESG批发零售行业白皮书

  • 基于asp.net的学生选课系统设计与实现.docx

    基于asp.net的学生选课系统设计与实现.docx

  • 基于Java后端和多种前端技术的15高德服装店电商平台设计源码

    本项目是一款采用Java后端技术，并融合多种前端技术（JavaScript, Vue, TypeScript, HTML, Shell等）构建的15高德服装店电商平台设计源码。整个项目包含3877个文件，其中JavaScript文件2944个，Java文件303个，Vue文件106个，其他类型文件如Markdown、SVG、JSON、XML、YAML等共计277个。该平台旨在为用户提供一个高效、便捷的购物体验。

  • 2024医药健康行业数字化转型白皮书

    2024医药健康行业数字化转型白皮书

  • code-server-4.93.1-rc.1-arm64.rpm

    code-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-server-4.93.1-rc.1-arm64.rpmcode-

  • 基于TGA1050收发器的STM32之间CAN通信设计源码

    该项目为基于TGA1050收发器的STM32 CAN通信设计源码，共计187个文件，涵盖34个头文件、33个数据文件、33个目标文件、32个C源文件、32个C目标文件、8个汇编文件、2个HTML文件、1个调试配置文件、1个映射文件、1个列表文件。主要采用C语言实现，旨在实现两个STM32之间的CAN通信功能。

Global site tag (gtag.js) - Google Analytics