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

7顶
0踩

编程语言

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

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

  • 零拷贝网络编程：RustTokio实现百万级QPS服务.pdf

    文档支持目录章节跳转同时还支持阅读器左侧大纲显示和章节快速定位，文档内容完整、条理清晰。文档内所有文字、图表、函数、目录等元素均显示正常，无任何异常情况，敬请您放心查阅与使用。文档仅供学习参考，请勿用作商业用途。 Rust 以内存安全、零成本抽象和并发高效的特性，重塑编程体验。无需垃圾回收，却能通过所有权与借用检查机制杜绝空指针、数据竞争等隐患。从底层系统开发到 Web 服务构建，从物联网设备到高性能区块链，它凭借出色的性能和可靠性，成为开发者的全能利器。拥抱 Rust，解锁高效、安全编程新境界！

  • PLC与触摸屏控制的流水线贴膜机程序项目完成，涵盖多种控制功能，适合初学者学习简单控制工艺及运动控制，支持博图V13及以上版本。

    内容概要：本文详细介绍了流水线贴膜机的PLC程序和触摸屏程序控制逻辑，涵盖气缸、输送带、伺服电机等关键部件的控制方法。文中通过具体代码示例解释了各个组件的工作原理及其协同运作的方式，如气缸的互锁逻辑、输送带的速度控制以及伺服电机的精确贴膜控制。此外，还强调了HMI界面设计的重要性，提供了报警处理、权限管理和调试技巧等方面的实践经验。 适合人群：工控行业初学者和技术爱好者，尤其是希望深入了解PLC编程和运动控制系统的人员。 使用场景及目标：①帮助读者掌握PLC编程的基本技能，如气缸控制、伺服电机控制等；②提供实际项目的调试经验和常见问题解决方案；③指导读者进行HMI界面设计，确保操作的安全性和便捷性。 其他说明：文章不仅包含了详细的代码示例，还分享了许多来自实际项目的经验教训，有助于读者更好地理解和应用所学知识。

  • 智能车换道路径规划与行为决策：改良版三维危险势能场建模法的高效应用

    内容概要：本文介绍了一种用于智能车换道路径规划与行为决策的改良版人工势场法。该方法通过引入三维势能场模型，不仅考虑车辆当前的空间位置，还预判了未来3秒内的运动趋势。文中详细描述了动态障碍物处理、车道保持势能场设计以及三维势能场的融合策略。特别是在处理动态障碍物时，采用速度相关的高斯函数，使得车辆能够更好地应对快速接近的障碍物。此外，车道保持势能场通过分段函数设计，在车辆靠近车道边缘时提供更强的回正力矩。三维势能场融合策略则通过加权求和的方式，综合考虑障碍物、车道线和速度等因素，从而提高换道的成功率并减少能耗。 适用人群：从事智能驾驶研究的技术人员、自动驾驶算法开发者、机器人导航领域的研究人员。 使用场景及目标：适用于智能车在复杂交通环境中的换道路径规划与行为决策。主要目标是提高换道成功率、减少能耗、提升乘客舒适度，并解决传统人工势场法中存在的局部极小值和动态障碍物处理难题。 其他说明：该方法已在多个实际场景中进行了测试，如高速公路、山区道路等，均取得了显著的效果。特别是在处理“剪刀车”场景时，能够在短时间内生成符合人类驾驶习惯的避让路径。

  • APK包名类名查看工具

    APK包名类名查看工具

  • 遗传算法优化支持向量机(GA-SVM)在时间序列预测中的应用及基于matlab代码实现

    内容概要：本文详细介绍了利用遗传算法（GA）优化支持向量机（SVM）进行时间序列预测的方法及其MATLAB实现。首先，通过对时间序列数据进行预处理，如标准化和滑动窗口分割，将时间序列转换为监督学习任务。接着，设计遗传算法的染色体结构，采用二进制编码表示SVM的关键参数C和gamma，并通过5折交叉验证的均方误差（MSE）作为适应度函数，确保每一代种群都能朝着更优解进化。文中还分享了一些实践经验，如种群多样性的保持、时间滞后的选择以及参数范围的调整。最后，展示了GA-SVM在不同数据集上的预测效果，并提供了完整的MATLAB代码。 适合人群：从事时间序列预测研究的技术人员，熟悉MATLAB编程环境的研究者。 使用场景及目标：适用于需要高效自动化调参的时间序列预测任务，特别是在面对非线性和高噪声数据时，能够显著提高预测精度。目标是帮助研究人员减少手动调参的工作量，提升模型性能。 其他说明：作者强调了遗传算法在参数优化方面的优势，但也指出其局限性，如可能存在早熟收敛等问题。同时提醒使用者关注数据特性和预处理步骤对最终结果的影响。

  • C# Winform 图书管理系统

    内容概要：本文详细介绍了使用C# Winform和ASP.NET开发的一个图书管理系统。系统分为后台和读者端两部分，后台主要用于管理员管理图书、用户和借阅信息，读者端则提供图书查询、借阅和归还等功能。文中展示了具体的代码实现，如图书查询、用户添加、图书入库、借阅功能等，并强调了数据库连接的安全性和性能优化措施，如参数化查询、事务处理、异步加载等。此外，还讨论了一些常见的开发陷阱和最佳实践，如防止SQL注入、使用配置文件管理连接字符串、利用RDLC生成报表等。 适合人群：具有一定C#和ASP.NET基础的开发者，尤其是对Winform桌面应用开发感兴趣的程序员。 使用场景及目标：适用于需要开发类似图书管理系统的项目，帮助开发者理解和掌握Winform应用程序的设计和实现，提高开发效率并确保系统的稳定性和安全性。 其他说明：本文提供了丰富的代码片段和详细的解释，有助于读者快速上手并应用于实际项目中。同时，文中提到的一些优化技巧和注意事项对于提升系统的性能和用户体验也非常有帮助。

  • 少儿编程scratch项目源代码文件案例素材-厄运洞穴.zip

    少儿编程scratch项目源代码文件案例素材-厄运洞穴.zip

  • 基于蒙特卡洛模拟的电动汽车日充电负荷Matlab程序：可灵活调整EV数量，随机数据生成

    内容概要：本文详细介绍了利用蒙特卡洛方法在Matlab中模拟电动汽车日充电负荷的方法。通过设定基本参数如电动汽车数量、充电功率、时间步骤等，采用随机函数生成每辆车的充电开始时间和持续时间，进而构建日充电负荷曲线。文中提供了完整的代码实现，包括参数初始化、随机数生成、时间轴处理、负荷叠加及结果可视化。此外，还讨论了模型的改进方向，如引入不同类型电动汽车、考虑充电桩功率限制等。 适合人群：对电力系统、电动汽车充电管理感兴趣的科研人员、工程师及高校学生。 使用场景及目标：适用于研究电动汽车充电对电网负荷的影响，帮助城市规划者评估大规模电动汽车普及后的电力需求，优化充电设施布局。同时，也为智能充电调度系统的开发提供理论依据和技术支持。 其他说明：该模拟方法简单直观，能够快速生成充电负荷曲线，便于理解和应用。尽管模型存在一定简化，但对于初步分析和规划已足够使用。未来可以通过引入更多现实因素提升模型准确性。

  • app查看工具.rar

    app查看工具

  • 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码（毕业设计&课程设计&项目开发）

    基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用~ 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用 基于java开发的菜鸟驿站快递管理系统（客户端+服务端）+源码，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用

  • 基于自回归整合滑动平均模型(ARIMA)的时间序列预测

    内容概要：本文详细介绍了ARIMA（自回归整合滑动平均模型）在时间序列预测中的应用及其Python实现。文章首先解释了ARIMA的基本概念，即通过历史数据、计算差异和纠正误差来进行预测。接着，通过具体案例展示了如何使用Python进行数据预处理、平稳性检验（如ADF检验）、差分处理、参数选择（如使用ACF/PACF图或auto_arima自动寻优）、模型构建与训练以及最终的预测和可视化。文中强调了ARIMA适用于轻量级任务，在处理非平稳和周期性数据时需要注意的问题，并提供了多个实用技巧和注意事项。 适用人群：对时间序列预测感兴趣的初学者和有一定编程基础的数据分析师、研究人员。 使用场景及目标：帮助读者掌握ARIMA模型的工作原理和实际应用，能够独立完成从数据准备到模型部署的完整流程，特别是在销售预测、经济数据分析等领域。 其他说明：文章不仅提供了详细的代码示例，还分享了许多实践经验，如避免过度差分、处理异常值、选择合适的预测步长等。同时指出ARIMA虽然是经典模型，但在某些情况下可能不如现代深度学习模型表现优异，因此建议结合具体情况灵活选用。

Global site tag (gtag.js) - Google Analytics