37

Below excerpt is from an article that explains possibility of Denial Of Service(DoS) attack because of non random hash functions used in Hash Data Structures.

[…] the condition can be leveraged by exploiting predictable collisions in the underlying hashing algorithms.

In order to verify it I went through reference implementation of Java HashMap from Oracle and indeed found a static hash functions used: 

    static int hash(int h) {
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
    }

Another paper on the topic tells:

A Tomcat 6.0.32 server parses a 2 MB string of colliding keys in about 44 minutes of i7 CPU time, so an attacker with about 6 kbit/s can keep one i7 core constantly busy. If the attacker has a Gigabit connection, he can keep about 100.000 i7 cores busy

How can we safeguard against this vulnerability. Moreover so with so many of softwares we use being open source (Tomcat etc.) which rely on this implementation.

4

5 に答える 5

54

攻撃ベクトルを理解する

HashMapsのしくみ

ブログのコメントフォームがパラメータ（first_name、last_name、comment）を投稿パラメータとして受け入れると言います。内部的には、TomcatはこれらのパラメーターをHashMapとして格納します。

このHashMapの論理構造は次のようになります-


"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"

しかし、物理的な構造は異なります。キーは最初にhashCodeに変換され、次にhashCodeが配列インデックスに変換されます。

したがって、理想的な物理的構造は次のようになります。


0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"

しかし、可能なキーは無限です。したがって、ある時点で、2つのキーが同じハッシュコードを持つようになります。これはハッシュ衝突になります。

衝突があると、物理的構造は次のようになります。


0 --> "Sripathi", "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"

ハッシュ衝突とパフォーマンスへの影響

ハッシュの衝突がある場合、新しいエントリを挿入するということは、単一のハッシュ「バケット」内のすべての要素を順番に繰り返して、マップにすでに存在するかどうかを確認することを意味します。すべての要素が同じ値にハッシュされる場合、1つの要素を挿入するとO（n）の複雑さに近づく可能性があります。この最悪の場合にn個の要素を挿入すると、O（n * n）の複雑さになります。

つまり、同じhashCodeを持つ数千のキーを挿入すると、サーバーは多くのCPUサイクルを必要とします。

同じハッシュでどのようにキーを生成しますか？

Javaでは、「Aa」と「BB」のハッシュコードは同じです。

「EquivalentSubstrings」というプロパティがあるため、これら2つの文字列から始めるだけで、同じハッシュコードで他のいくつかの文字列を生成できます。

最初の反復：「AAAA」、「AABb」、「BbAA」、「BbBb」は同じハッシュコードを持ちます

これで、同じハッシュコードを持つ4つの文字列ができました。それらを並べ替えて、同じハッシュコードを持つ16個の文字列を生成できます。例えば ​​：


"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

これらの16個の文字列はすべて同じハッシュコードを持っています。

これで、これらの16個の文字列を取得して、同じハッシュコードを持つ256個の文字列を生成できます。

つまり、正確なハッシュコードを持つ文字列の大規模なセットを生成するのは非常に簡単です。

サーバーをどのように攻撃しますか？

  1. 同じハッシュコードを持つ何千もの文字列を作成します（上記を参照）
  2. 次のようなPOSTリクエストを作成します-AaAa=＆AaBB =＆BBAa =＆BBBB=...。
  3. フォームを送信する
  4. ループで繰り返し、すべてのサーバーリソースが使い果たされるように、いくつかのスレッドを作成します

これは単なるPOSTリクエストであるため、攻撃者は無実のブラウザを使用してサーバーを攻撃することもできます。クロスサイトスクリプティングの脆弱性があるWebサイトを見つけ、POSTリクエストを行うためのコードを埋め込んでから、ソーシャルエンジニアリングを使用してリンクをできるだけ多くのユーザーに広めます。

防止

一般に、基盤となるプラットフォームはこれを修正できません。これは、アプリケーションフレームワークの問題と見なされます。つまり、TomcatはOracle / Sunではなく、これを修正する必要があります。

考えられる修正は次のとおりです。

  1. POSTパラメータの数を制限する-Tomcat6.0.35+には新しいパラメータmaxParameterCountがあります。デフォルト値は10,000です。機能を損なわない限り、低いほど良いです。

  2. POSTリクエストのサイズを制限する-攻撃が機能するためには、ペイロードが巨大である必要があります。Tomcatで許可されるデフォルトのPOSTは2MBです。これを200KBに減らすと、この攻撃の効果が低下します。tomcatのパラメータはmaxPostSizeです

  3. Webアプリケーションファイアウォール-Webアプリケーションファイアウォールがある場合は、疑わしいと思われるリクエストをブロックするように設定できます。これは事後対応策ですが、上記の解決策のいずれかを使用できない場合に備えておくと便利です。

参考までに-Tomcatのドキュメントはこちら-http://tomcat.apache.org/tomcat-6.0-doc/config/http.html

于 2011-12-29T17:55:28.017 に答える
3

最も簡単な解決策は、修正済みバージョンの tomcat にアップグレードすることです。ただし、Tomcat の人々が変更する必要があることの詳細を知りたいと思われます。

この攻撃は、ハッシュ データ構造の一般的な実装の詳細を悪用することによって機能します。つまり、リンク リストを使用して、ハッシュが同じすべての値を保持します。リストのサイズが大きくなるため、このリンクされたリストに値を追加するのは非効率的です。攻撃者は、衝突するハッシュを生成することが知られている値のリストを作成して、この非効率的な動作を強制することができます。これを防ぐには、いくつかのオプションがあります。

  • 衝突を防ぐ - ハッシュ関数に (疑似) ランダム要素を持たせることで、攻撃者が衝突する値を生成するのを防ぎます。Perl は長い間これを行ってきました。

  • バケットにはリンク リスト以外のものを使用します。リンク リストに N 個のアイテムを挿入すると N^2 の成長があるため、攻撃が機能します。バランス ツリーまたは挿入時に N logN 成長する他の構造を使用する場合、問題は軽減されるはずです。これにより、最悪のケースがどれほど悪いかを制限するために、最良/平均的なケースのパフォーマンスが犠牲になる可能性があります。

于 2011-12-29T16:44:03.967 に答える
1

影響を受ける Tomcat のバージョンは、提供されたリンクによると、Apache Tomcat <= 5.5.34、<= 6.0.34、<= 7.0.22 です。このページには、修正済みバージョンとして Apache Tomcat >= 5.5.35、>= 6.0.35、>= 7.0.23 がリストされています。

于 2011-12-29T16:14:47.553 に答える
0

これらのキーを生成するためのPythonコードを次に示します...まだテストしていませんが、フィードバックを得ることに興味があります。

#!/usr/bin/python
import sys
alphabet = ["Aa","BB"]

def func(str, length):
                global alphabet
                if(length != 0):
                                for x in alphabet:
                                                new_str = str+x
                                                func(new_str, length-1)
                else:
                                sys.stdout.write(str+"=&")


for x in range(1,16):
        func("",x)
于 2012-05-29T17:31:14.813 に答える
-1

Java HashMap / HashTableは、入力されたエントリがしきい値に達したときに「サイズ変更」操作を実行できます。固定バケットのHashMapがあなたを待っているとは言い難いです。バケットを選択する操作のため、2つのステップがあります。1つは指定されたキーのハッシュ値を取得することです。もう1つの主要なステップは、バケットの合計サイズを使用した剰余操作です（サイズは「サイズ変更」によって変更されています）。

于 2012-01-06T06:16:10.677 に答える