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

7顶
0踩

编程语言

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

2012-01-06 17:30 by 资深编辑 luiang1018 评论(5) 有14366人浏览
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 防范 ...

  • AVR单片机项目-ADC键盘（源码+仿真+效果图）.zip

    使用adc功能来判断不同电压，那必定是通过电压的不同来区分的，这就需要按键与电阻进行组合，我设计打算使用正比关系的按键阻值，这样会比较好在程序判断，最后就如仿真图那样设计，按键按下让某部分电路短路，剩下的电路得到不同的电压值，而不同按键按下，对应的电阻值是10k的倍数，很好区分。而基地的电阻设为10k，按键靠近gnd的电压值最小，远离则慢慢增大，可大概计算出来的，分压的电压为5v。按键不按时为0v，有按键按的电压范围为2.5v~0.238v。然后用以前编写好的数码管驱动拿过来用，也就是用动态扫描的方式进行显示的。然后编写adc代码，根据atmega16的数据手册就可以慢慢写出来了，即配置好ADMUX、ADCSRA寄存器，使用单次触发的方式，写好对应的函数，在初始化之后，使用定时器1中断进行adc的读取和数码管的刷新显示。而adc对应按键的判断也使用了for循环对1024分成1~21份，对其附近符合的值即可判断为按键i-1，可直接显示出来，而误差值可以多次测量后进行调整。 使用adc功能来判断不同电压，那必定是通过电压的不同来区分的，这就需要按键与电阻进行组合，我设计打算使用正比关系的按

  • java毕设项目之基于SpringBoot的失物招领平台的设计与实现(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明： 开发语言：Java 框架：springboot，mybatis JDK版本：JDK1.8 数据库：mysql 5.7 数据库工具：Navicat11 开发软件：eclipse/idea Maven包：Maven3.3

  • java毕设项目之基于springboot的智能家居系统(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明： 开发语言：Java 框架：springboot，mybatis JDK版本：JDK1.8 数据库：mysql 5.7 数据库工具：Navicat11 开发软件：eclipse/idea Maven包：Maven3.3

  • 【SCI一区】海洋捕食者算法MPA-CNN-LSTM-Attention风电功率预测【Matlab仿真 5558期】.zip

    CSDN Matlab研究室上传的资料均有对应的仿真结果图，仿真结果图均是完整代码运行得出，完整代码亲测可用，适合小白； 1、完整的代码压缩包内容 主函数：main.m； 调用函数：其他m文件；无需运行 运行结果效果图； 2、代码运行版本 Matlab 2019b；若运行有误，根据提示修改；若不会，私信博主； 3、运行操作步骤 步骤一：将所有文件放到Matlab的当前文件夹中； 步骤二：双击打开main.m文件； 步骤三：点击运行，等程序运行完得到结果； 4、仿真咨询 如需其他服务，可私信博主或扫描博客文章底部QQ名片； 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

  • 111人工智能代码.zip

    111人工智能代码.zip

  • 基于因果关系知识库的因果事件图谱实验项目，本项目罗列了因果显式表达的几种模式，基于这种模式和大规模语料，再经过融源码+文档+全部资料.zip

    【资源说明】 基于因果关系知识库的因果事件图谱实验项目，本项目罗列了因果显式表达的几种模式，基于这种模式和大规模语料，再经过融源码+文档+全部资料.zip 【备注】 1、该项目是个人高分项目源码，已获导师指导认可通过，答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功，功能ok的情况下才上传的，请放心下载使用！ 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用，也可作为毕业设计、课程设计、作业、项目初期立项演示等，当然也适合小白学习进阶。 4、如果基础还行，可以在此代码基础上进行修改，以实现其他功能，也可直接用于毕设、课设、作业等。 欢迎下载，沟通交流，互相学习，共同进步！

  • java毕设项目之基于Spring Boot的疗养院管理系统的设计与实现(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明： 开发语言：Java 框架：springboot，mybatis JDK版本：JDK1.8 数据库：mysql 5.7 数据库工具：Navicat11 开发软件：eclipse/idea Maven包：Maven3.3

  • java毕设项目之基于JAVA语言的在线考试与学习交流网页平台(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明： 开发语言：Java 框架：springboot，mybatis JDK版本：JDK1.8 数据库：mysql 5.7 数据库工具：Navicat11 开发软件：eclipse/idea Maven包：Maven3.3

  • elasticsearch-analysis-dynamic-synonym-8.16.2

    解压之后在elasticsearch的jdk\conf\security\java.policy文件下新增这段，然后重启es就可以使用了 permission java.net.SocketPermission "*", "connect,resolve"; permission java.lang.RuntimePermission "setContextClassLoader"; permission java.lang.RuntimePermission "accessDeclaredMembers"; permission java.lang.RuntimePermission "createClassLoader"; permission java.security.SecurityPermission "putProviderProperty.MySQLScramSha1Sasl"; permission java.security.SecurityPermission "insertProvider";

  • 【SCI一区】基于matlab飞蛾扑火算法MFO-CNN-BiLSTM-Mutilhead-Attention多变量时序预测【Matlab仿真 5610期】.zip

    CSDN Matlab研究室上传的资料均有对应的仿真结果图，仿真结果图均是完整代码运行得出，完整代码亲测可用，适合小白； 1、完整的代码压缩包内容 主函数：main.m； 调用函数：其他m文件；无需运行 运行结果效果图； 2、代码运行版本 Matlab 2019b；若运行有误，根据提示修改；若不会，私信博主； 3、运行操作步骤 步骤一：将所有文件放到Matlab的当前文件夹中； 步骤二：双击打开main.m文件； 步骤三：点击运行，等程序运行完得到结果； 4、仿真咨询 如需其他服务，可私信博主或扫描博客文章底部QQ名片； 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

  • 基于知识图谱的豆瓣书籍推荐问答系统源码+文档+全部资料.zip

    【资源说明】 基于知识图谱的豆瓣书籍推荐问答系统源码+文档+全部资料.zip 【备注】 1、该项目是个人高分项目源码，已获导师指导认可通过，答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功，功能ok的情况下才上传的，请放心下载使用！ 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用，也可作为毕业设计、课程设计、作业、项目初期立项演示等，当然也适合小白学习进阶。 4、如果基础还行，可以在此代码基础上进行修改，以实现其他功能，也可直接用于毕设、课设、作业等。 欢迎下载，沟通交流，互相学习，共同进步！

Global site tag (gtag.js) - Google Analytics