桔子建站官网,甘肃模板型网站建设,国外 网站源码,大型网站seo方法hashdos近一个月前#xff0c;我就如何在不与供应商互动的情况下临时解决 28C3上出现的HashDoS问题或其他代码缺陷发表了一些想法。 现在是时候更深入地研究复杂性攻击并查看源了。 我完全假设java.util.HashMap和java.util.Hashtable是受此攻击影响的最常用的Java数据结构我就如何在不与供应商互动的情况下临时解决 28C3上出现的HashDoS问题或其他代码缺陷发表了一些想法。 现在是时候更深入地研究复杂性攻击并查看源了。 我完全假设java.util.HashMap和java.util.Hashtable是受此攻击影响的最常用的Java数据结构因此本文仅将代码集中在这些类型的后面。 哈希函数和索引数据结构的简要介绍 哈希索引数据结构因其简单的用法和优点而非常受欢迎 无需打扰索引表即可找到所需数据的正确位置 通过使用关键字而不是索引号访问数据 添加或删除操作的时间几乎恒定 为了获得这些好处哈希索引数据结构遵循有关如何索引数据的聪明思想。 索引是通过散列与背后数据关联的关键字来计算的。 考虑以下示例这是一个类似于代码的简单示例 myHashIndexedDataStructure [hashkeyword] 特定数据 听起来很完美但是它有一个主要缺点在大多数情况下使用的哈希函数不是加密函数。 根据Wikipedia的说法函数本身调用哈希函数的唯一强制特征是 “将可变长度的大型数据集称为键映射到固定长度的较小数据集” 与称自己为密码哈希函数再次是来自Wikipedia的定义相反它必须满足更多甚至更强大的要求 ” 计算任何给定消息的哈希值很容易但不一定很快 生成具有给定哈希值的消息是不可行的 在不更改哈希的情况下修改消息是不可行的 找到两个具有相同哈希值的不同消息是不可行的 ” 长话短说让我们总结一下我们学到的知识以及用这些知识可以得出的结论 哈希索引数据结构利用哈希函数 哈希函数不一定是抗冲突的只要它们不是加密的 缺乏抗碰撞性意味着可以轻松计算具有相同哈希值的多个值 如果关键字冲突则哈希索引数据结构需要某种计划b–一种后备算法–关于如何处理具有相同关键字哈希值的多个数据集。 实际上有几种可行的方法 探测转移到固定或可计算的间隔 多重哈希 条目链接冲突条目的构建列表 覆盖现有条目 以下哪种策略需要Java 首先我们将检查java.util的代码。 Hashtable 仅显示有趣的部分为清晰起见省略了其余代码 public synchronized V put(K key, V value) { ... // Makes sure the key is not already in the hashtable. Entry tab[] table; int hash key.hashCode(); int index (hash 0x7FFFFFFF) %tab.length; for (EntryK,V e tab[index] ; e ! null ; e e.next) { if((e.hash hash) e.key.equals(key)) { V old e.value; e.value value; return old; } } ... // Creates the new entry. EntryK,V e tab[index]; tab[index] new Entry(hash, key, value, e); count; return null;
} 可以看出该类使用键对象 关键字 的hashCode 函数来计算哈希值。 它遵循ANDing运算符为了将其正确表示为IntegerMODULO运算符将表大小建立循环环结构table.length 1mod table.length1用余数除法始终解决标签 []中的条目。 此后将考虑所有条目 -ies并检查哈希值是否相同且对象本身是否相同。 if -clause防止存储同一对象的多个实例-旧的实例仅由新的实例替换。 如果在由key.hashCode 标识的当前位置上找不到相同的对象关于哈希值和equals 方法则将创建一个新的Entry并将其放置在当前位置并在该位置处理旧的Entry对象。 到目前为止看起来java.util.Hashtable在每个tab []之后都使用某种列表作为数据结构。 查看私有内部类java.util.Hashtable.Entry KV的代码时可以确认此假设。 private static class EntryK,V implements Map.EntryK,V { int hash; K key; V value; EntryK,V next; 下一个Entry对象仅指向下一个Entry 。 这代表一个定制的链表。 java.util.HashMap的代码更加复杂并且表现部分不同允许使用null值不同步但是基于相同的思想。 在这里调查代码不会发现任何新内容除了Entry重新被重新实现的事实…。 两种实现都依赖于哈希索引数组的每个条目后面的链接列表。 进攻思路 现在我们知道了java.util.Hashtable和java.util.HashMap背后的实现细节我们可以回到称为HashDoS的攻击。 该攻击实现了CrosbySAWallachDS的想法 通过算法复杂性攻击拒绝服务。 在关于USENIX安全研讨会的第12届会议论文集–第12卷USENIX协会2003 总结一下散列索引的数据结构会因引发不利的状态而大大减慢速度。 理想的哈希索引数据结构如下所示 ... table[hash(keyA)] dataA table[hash(keyB)] dataB table[hash(keyC)] dataC table[hash(keyD)] dataD ... 在这种情况下使用具有不同哈希值的关键字更改删除或添加数据的时间几乎是恒定的。 通过使用关键字的哈希值作为索引可以轻松找到位置并且无需迭代列表即可立即显示数据。 让我们看一下哈希索引数据结构的另一种不利状态 ... hash(keyA) hash(keyB) hash(keyC) hash(keyD) k table[k] dataA - dataB - dataC - dataD ... 像这样的结构CRUD操作的恒定时间已经结束了…… 计算关键字的哈希值 遍历链表 比较每个条目的关键字如果它与应用程序正在寻找的关键字匹配 这会大大减慢处理线程的速度。 一个非常快的数据结构已经变成了一个链表并带有额外的开销计算哈希值。 散列索引数据结构的所有好处都将被抹去。 好像还不够糟糕大多数哈希索引数据结构都启用了称为重新哈希的功能。 当数据结构超过定义的负载例如在Java中为75时出于优化原因重新整理表。 大多数情况下绝对希望使用此功能但在这种特殊情况下它甚至会减慢整个过程。 利用问题 要利用此行为有必要计算一大堆冲突关键字。 例如如果我们假设关键字的类型为java.lang.String 我们可以看一下其hashCode 函数 public int hashCode() { int h hash; if (h 0) { int off offset; char val[] value; int len count; for (int i 0; i len; i) { h 31*h val[off]; } hash h; } return h; } 这似乎是DJ Bernstein设计的功能DJBX33A的自定义版本可以在其中轻松发现冲突。 该函数具有一个有趣的属性将在以下示例中进行演示 0w.hashCode() 1607 1X.hashCode() 1607 29.hashCode() 1607 0w1X.hashCode() 1545934 0w29.hashCode() 1545934 1X0w.hashCode() 1545934 1X29.hashCode() 1545934 290w.hashCode() 1545934 291X.hashCode() 1545934 ... 我们看到碰撞值的串联再次导致碰撞值。 我们可以继续做下去并获得大量碰撞关键字。 这使查找冲突比单纯的暴力破解更加容易。 我们针对本地Web服务对此进行了测试并且可以通过使用冲突关键字作为标记属性来显着降低正在运行的Web应用程序服务器的速度。 我不确定是否确实可能使计算机崩溃或者是否存在某种非显而易见的机制来防止服务器自行杀死我们尚未在服务器端研究处理代码但是可以肯定地阻止服务器在可接受的时间内正常运行。 对Web服务的请求很容易被延迟。 也许我会在不久的将来付出一些努力来收集测量数据#colliding keys –系统响应时间。 如果我这样做您将在此博客上找到数据… 带你去的拐角点 永远不要单独依赖hashCode() –容易出错 避免像 if(password.hashCode() referencePassword.hashCode()) { return godMode; 在决定/反对数据类型/结构时花几秒钟的时间在实现细节上 筛选传入的数据–裁剪其大小拒绝超长参数等。 小心并始终注意编码最佳实践 进一步有趣的观点 在此示例中我们使用java.lang.String作为关键字对象。 有趣的是还可以使用什么以及在JRE代码或大量使用的项目中冲突的哈希值在何处用于数据结构或什至更坏的目的。 可以看看Object.hashCode 是如何实现的它是本机代码–这将是一个不错的目标因为所有其他对象都扩展了该基类。 如果扩展类没有覆盖hashCode 函数而是依赖于正确的无冲突的输出则这对于更复杂的攻击可能很有用。 考虑一下如果序列化依赖于相应的代码会发生什么……。 如果有人已经知道一些脆弱的地方请告诉我们 我们非常有兴趣但是由于时间有限无法达到我们想要的深度。 谢谢 我要再次感谢Juraj Somorovsky所做的丰富的联合研究工作 此外我们还要感谢oCERT团队的Andrea Barisani和红帽安全响应团队的 Vincent Danen 他们与我们讨论了这个问题 参考从我们的JCG合作伙伴处 调查HashDoS问题 Java安全和相关主题博客中的Christopher Meyer。 翻译自: https://www.javacodegeeks.com/2012/02/investigating-hashdos-issue.htmlhashdos
