Hash碰撞的拒绝式服务攻击(Hash Collision DoS) 问题

fmms 12年前
     <p>最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比。<strong>这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%)</strong>。目前,这个问题出现于<a href="/misc/goto?guid=4958324591009965295">Java</a>, <a href="/misc/goto?guid=4958196052934300882">JRuby</a>, <a href="/misc/goto?guid=4958191778886660494">PHP</a>, <a href="/misc/goto?guid=4958185439955761087">Python</a>, <a href="/misc/goto?guid=4958186864231483269">Rubinius</a>, <a href="/misc/goto?guid=4958324594758760390">Ruby</a>这些语言中,主要:</p>    <ul>     <li><a href="/misc/goto?guid=4958324591009965295">Java</a>, 所有版本</li>     <li><a href="/misc/goto?guid=4958196052934300882">JRuby</a> <= 1.6.5 (目前fix在 1.6.5.1)</li>     <li><a href="/misc/goto?guid=4958191778886660494">PHP</a> <= 5.3.8, <= 5.4.0RC3 (目前fix在 5.3.9,  5.4.0RC4)</li>     <li><a href="/misc/goto?guid=4958185439955761087">Python</a>, all versions</li>     <li><a href="/misc/goto?guid=4958186864231483269">Rubinius</a>, all versions</li>     <li><a href="/misc/goto?guid=4958324594758760390">Ruby</a> <= 1.8.7-p356 (目前fix在 1.8.7-p357, 1.9.x)</li>     <li><a href="/misc/goto?guid=4958199496154655219">Apache Geronimo</a>, 所有版本</li>     <li><a href="/misc/goto?guid=4958188844195451926">Apache Tomcat</a> <= 5.5.34, <= 6.0.34, <= 7.0.22 (目前fix在 5.5.35,  6.0.35,  7.0.23)</li>     <li><a href="/misc/goto?guid=4958183145339715559">Oracle Glassfish</a> <= 3.1.1 (目前fix在mainline)</li>     <li><a href="/misc/goto?guid=4958184803864787499">Jetty</a>, 所有版本</li>     <li><a href="/misc/goto?guid=4958184489457545763">Plone</a>, 所有版本</li>     <li><a href="/misc/goto?guid=4958183525874143900">Rack</a> <= 1.3.5, <= 1.2.4, <= 1.1.2 (目前fix 在 1.4.0, 1.3.6, 1.2.5, 1.1.3)</li>     <li><a href="/misc/goto?guid=4958324604344519844">V8 JavaScript Engine</a>, 所有版本</li>     <li>ASP.NET 没有打MS11-100补丁</li>    </ul>    <p>注意,Perl没有这个问题,因为Perl在N年前就fix了这个问题了。关于这个列表的更新,请参看 <a href="/misc/goto?guid=4958324605148992216" target="_blank">oCERT的2011-003报告</a>,比较坑爹的是,这个问题早在2003 年就在论文《<a href="/misc/goto?guid=4958324605936174382" target="_blank">通过算法复杂性进行拒绝式服务攻击</a>》中被报告了,但是好像没有引起注意,尤其是Java。</p>    <h4>弱点攻击解释</h4>    <p>你可以会觉得这个问题没有什么大不了的,因为黑客是看不到hash算法的,如果你这么认为,那么你就错了,这说明对Web编程的了解还不足够底层。</p>    <p></p>    <p>无论你用JSP,PHP,Python,Ruby来写后台网页的时候,在处理HTTP POST数据的时候,你的后台程序可以很容易地以访问表单字段名来访问表单值,就像下面这段程序一样:</p>    <div>     <div id="highlighter_205745" class="syntaxhighlighter php">      <pre class="brush:cpp; toolbar: true; auto-links: false;">$usrname = $_POST['username'];  $passwd = $_POST['password'];</pre>     </div>    </div>    <p>这是怎么实现的呢?这后面的东西就是Hash Map啊,所以,我可以给你后台提交一个有10K字段的表单,这些字段名都被我精心地设计过,他们全是Hash Collision ,于是你的Web Server或语言处理这个表单的时候,就会建造这个hash map,于是在每插入一个表单字段的时候,都会先遍历一遍你所有已插入的字段,于是你的服务器的CPU一下就100%了,你会觉得这10K没什么,那么我就发很多个的请求,你的服务器一下就不行了。</p>    <p>举个例子,你可能更容易理解:</p>    <p>如果你有n个值—— v1, v2, v3, … vn,把他们放到hash表中应该是足够散列的,这样性能才高:</p>    <blockquote>     <p>0 -> v2<br /> 1 -> v4<br /> 2 -> v1<br /> …<br /> …<br /> n -> v(x)</p>    </blockquote>    <p>但是,这个攻击可以让我造出N个值——  dos1, dos2, …., dosn,他们的hash key都是一样的(也就是Hash Collision),导致你的hash表成了下面这个样子:</p>    <blockquote>     <p>0 – > dos1 -> dos2 -> dos3 -> …. ->dosn<br /> 1 -> null<br /> 2 -> null<br /> …<br /> …<br /> n -> null</p>    </blockquote>    <p>于是,单向链接就这样出现了。这样一来,O(1)的搜索算法复杂度就成了O(n),而插入N个数据的算法复杂度就成了O(n^2),你想想这是什么样的性能。</p>    <p>(关于Hash表的实现,如果你忘了,那就把大学时的《数据结构》一书拿出来看看)</p>    <h4>  Hash Collision DoS 详解</h4>    <p>StackOverflow.com是个好网站, 合格的程序员都应该知道这个网站。上去一查,就看到了这个贴子“<a title="Application vulnerability due to Non Random Hash Functions" href="/misc/goto?guid=4958324606742798389" target="_blank">Application vulnerability due to Non Random Hash Functions</a>”。我把这个贴子里的东西摘一些过来。</p>    <p>首先,这些语言使用的Hash算法都是“非随机的”,如下所示,这个是Java和Oracle使用的Hash函数:</p>    <div>     <div id="highlighter_964814" class="syntaxhighlighter cpp">      <pre class="brush:cpp; toolbar: true; auto-links: false;">static int hash(int h)  {  h ^= (h >>> 20) ^ (h >>> 12);  return h ^ (h >>> 7) ^ (h >>> 4);  }</pre>      <br />     </div>    </div>    <p>所谓“非随机的” Hash算法,就可以猜。比如:</p>    <p>1)在Java里, Aa和BB这两个字符串的hash code(或hash key) 是一样的,也就是Collision 。</p>    <p>2)于是,我们就可以通过这两个种子生成更多的拥有同一个hash key的字符串。如:”AaAa”, “AaBB”, “BBAa”, “BBBB”。这是第一次迭代。其实就是一个排列组合,写个程序就搞定了。</p>    <p>3)然后,我们可以用这4个长度的字符串,构造8个长度的字符串,如下所示:</p>    <pre style="padding-left:30px;"><code>"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",   "BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",   "AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",   "BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",</code></pre>    <p><code>4)同理,我们就可以生成16个长度的,以及256个长度的字符串,总之,很容易生成N多的这样的值。</code></p>    <p>在攻击时,我只需要把这些数据做成一个HTTP POST 表单,然后写一个无限循环的程序,不停地提交这个表单。你用你的浏览器就可以了。当然,如果做得更精妙一点的话,把你的这个表单做成一个跨站脚本,然后找一些网站的跨站漏洞,放上去,于是能过SNS的力量就可以找到N多个用户来帮你从不同的IP来攻击某服务器。</p>    <p> </p>    <h4>防守</h4>    <p>要防守这样的攻击,有下面几个招:</p>    <ul>     <li>打补丁,把hash算法改了。</li>     <li>限制POST的参数个数,限制POST的请求长度。</li>     <li>最好还有防火墙检测异常的请求。</li>    </ul>    <p>不过,对于更底层的或是其它形式的攻击,可能就有点麻烦了。</p>    <p>(全文完)<br /> 原文出处:<a href="/misc/goto?guid=4958324607527921258" rel="nofollow" target="_blank">http://coolshell.cn/articles/6424.html</a></p>