`
desert3
  • 浏览: 2159231 次
  • 性别: Icon_minigender_1
  • 来自: 合肥
社区版块
存档分类
最新评论

哈希碰撞Hash Collision

 
阅读更多
转自:哈希碰撞相关

哈希碰撞Hash Collision DoS(Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比。这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多hash运算前value不一样,但是hash运算后值一样数据,然后让你的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, all versions
  Rubinius, all versions
  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,增加maxParameterCount限制单个request的参数个数!默认值10000)
  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碰撞攻击解释
  你可以会觉得这个问题没有什么大不了的,因为黑客是看不到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 Collision DoS 详解: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的请求长度。
限制POST请求的大小
最好还有防火墙检测异常的请求。
不过,对于更底层的或是其它形式的攻击,可能就有点麻烦了。
分享到:
评论

相关推荐

    关于Hash Collision DoS漏洞:web实例

    标题中的“Hash Collision DoS漏洞:web实例”指的是在Web应用程序中出现的一种安全问题,即哈希碰撞拒绝服务攻击(Hash Collision Denial of Service)。这种攻击利用了哈希表(Hash Table)数据结构的特性,当两个...

    哈希碰撞与生日攻击

    哈希(Hash)是一种算法,用于将任意长度的数据映射为固定长度的值。这些值通常称为哈希值或摘要。哈希算法的一个重要特性是,对于任何给定的输入,其输出始终相同,且即使是微小的变化也会导致完全不同的哈希值。...

    警惕Hash Collision Dos.pdf

    【警惕Hash Collision Dos】这篇文档主要讨论了一种名为“Hash Collision Dos”的网络安全威胁,这种攻击方式利用了哈希表(HashTable)的冲突特性对Web服务器进行拒绝服务(Denial of Service,DoS)攻击。哈希表在...

    python 密码学示例——理解哈希(Hash)算法

    1. 抗碰撞(Collision Resistance):难以找到两个不同的输入产生相同的哈希值,这使得篡改数据后保持哈希值不变变得困难。 2. 弱抗原像(Weak Preimage Resistance):对于给定的哈希值,找到一个输入使得哈希结果...

    前端大厂最新面试题-hash-table.docx

    本文档总结了 Hash Table 的基本概念、哈希函数、Collision 解决方法、Hash Table 的实现和应用、Hash Table 相关算法、LeetCode 相关题目和 Hash Table 的优点和缺点等方面的知识点,为读者提供了 Hash Table 相关...

    hashcollision

    莫尔斯电码哈希碰撞检测器这是什么? 这个小工具将相当于字母表中每个字母的二进制莫尔斯电码转换为一个数字。 这个数字可以用作表的索引。你为什么需要这个? 如果您正在尝试莫尔斯电码挑战,此工具会计算将二进制...

    试谈哈希树(HashTree)数据结构分析报告.doc

    哈希树,也称为HashTree,是一种数据结构,它结合了哈希函数和树状结构的特点,用于高效地存储和检索数据。哈希树的概念源于哈希表,它旨在通过哈希函数直接定位数据,避免传统查找算法中的多次比较,从而提高查找...

    各种hash算法-hashcodeUtil

    1. **哈希碰撞(Hash Collision)**:由于哈希函数的输出空间有限,不同的输入可能会得到相同的哈希值,这种情况称为哈希碰撞。优秀的哈希函数应尽量减少哈希碰撞,以提高查找效率。 2. **优化哈希码**:在自定义类...

    C++源代码:哈希表算法

    2. **碰撞处理**:由于哈希函数不能保证完全无冲突,当两个不同的输入得到相同的哈希值时,就需要采取碰撞处理策略。常见的处理方法有开放寻址法(Open Addressing)和链地址法(Chaining)。C++标准库中的`std::...

    哈希摘要算法编程设计源代码

    1. **抗碰撞(Collision Resistance)**:给定一个哈希函数,难以找到两个不同的输入数据,使得它们的哈希值相同。这是哈希函数的核心安全性要求。 2. **非可逆性(One-Wayness)**:一旦数据被哈希,无法通过哈希...

    Hash_function_hashtable_hash_

    哈希冲突(Hash Collision)是使用哈希函数时不可避免的问题,即不同的输入可能会得到相同的哈希值。处理哈希冲突的方法主要有两种:开放寻址法和链地址法。开放寻址法是指当发生冲突时,寻找下一个空的哈希地址,...

    哈希表实验报告.doc

    * 哈希函数(Hash Function):将键转换为索引的函数。 * 索引(Index):哈希函数计算出的索引值。 * 冲突(Collision):多个键映射到同一个索引的情况。 哈希表的实现 在本实验中,我们将实现一个哈希表,用于...

    数据结构 哈希查找 上机实验

    这里采用了一个简单的线性哈希函数:`Hash(K) = (3 * K) % length`。其中,`3`是一个常量,`%`操作符表示取模运算,`length`是哈希表的长度。 ### 四、解决冲突的方法 当两个不同的关键字通过哈希函数映射到了同一...

    hash_map的详解

    理想情况下,哈希函数应该能够均匀分布数据,从而减少碰撞(hash collision)的概率。碰撞指的是两个不同的键被哈希到同一个位置的情况。 - **解决冲突**:即使是最优的哈希函数也无法完全避免碰撞的发生。常见的...

    数据结构哈希表

    在这个例子中,`Hash`函数简单地通过取模运算实现了键值到数组下标的映射,即`Hash(KeyType K) = K % m`,其中`m`是哈希表的长度。当两个不同的键通过哈希函数得到相同的数组下标时,就会发生冲突。 处理冲突的一种...

    数据结构中的哈希表查找

    哈希表(Hash Table)是一种基于数组的数据结构,它通过将关键字映射到数组的某个位置来存储和检索数据,这种映射过程通常由一个哈希函数完成。哈希表能够实现快速的数据查找、插入和删除操作,在理想情况下,这些...

    c语言基础-c语言编程基础之哈希表示例-存在重复单元.zip

    然而,由于哈希函数可能存在多个键映射到同一个索引,导致哈希冲突(Collision)。解决哈希冲突有多种策略,常见的包括开放寻址法、链地址法和再哈希法等。 1. **开放寻址法**:当发生冲突时,不是立即在当前位置...

    JS散列表碰撞处理、开链法、HashTable散列示例

    在实际应用中,由于不同的键可能会通过散列函数得到相同的索引,这就产生了散列碰撞(hash collision)。本文将深入探讨JS散列表中的碰撞处理,特别是使用开链法(separate chaining)以及一个具体的HashTable散列...

Global site tag (gtag.js) - Google Analytics