技術者ブログ

はじめに

2011年末に発表されたHashDoS攻撃は、JavaやPHP、ASPなど非常に広い範囲に影響を及ぼすものであり、大きな話題となりました。筆者はちょうど大晦日にこの情報をキャッチし、その内容にのけぞりそうになりました。というのも、Javaアプリケーション内でHashMapを使い、そこにユーザ（この場合は攻撃者）からのデータを格納するだけで脆弱だというからです。

JavaではHashMapは非常に頻繁に使われる基本的なクラスであり、TomcatやJettyなどが当然のように影響を受けました。私たちが提供しているSaaS型WAFサービス「Scutum(スキュータム)」は、筆者が開発しているGuardian@JUMPERZ.NET(以下、Guardian)というJava製のWAFアプリケーションがコアとなっており、内部では非常に多くの箇所でHashMapを使用しています。大晦日の午前中、大掃除をあきらめてまず最初に確認したのは、Guardian自体がこの攻撃に脆弱かどうか？という点です。ウェブアプリケーションやウェブサーバを守るべきWAFそのものがDoS攻撃に弱いとなってしまうと、極めてまずいと考えました。

WAFは当然、HTTPリクエストに含まれる各パラメータをパースして検査しますが、これらのパラメータは「name=value」というスタイルを取っているため、単純に考えればアプリケーション内部ではHashMapにそのまま格納するようなソースコードを書いてしまうことは十分あり得ます。どんな実装をしたのか記憶があいまいだったので、半ば祈りながらソースコードを確認したところ、ラッキーなことにパース後のデータはHashMapではなくListで管理していました。Guardian自体はこの攻撃には脆弱でないと確認でき、ほっと一息つけたのです。

その後ウェブ上で次々に更新される情報を確認しながら、お正月であるにもかかわらず防御機能の開発を開始しました。今回は、私たちのWAFでどのようにHashDoS攻撃を検知しているかについて、技術的な解説を行います。

シグネチャでは検知できない

HashDoSでは計算されたハッシュ値が同じになるような組み合わせを攻撃者が自由に選ぶことができます。筆者は最初に出回ったExploitコードの内容が「EzEzEzEz...」という特徴的な文字列を含むものだったため、まずはこれをシグネチャにすれば防御できるのか？と考えたのですが、すぐにそれではダメであることがわかりました。

PHP5のハッシュ値の計算は、Javaで表現すると以下のような関数で行われているものと思われます。

public static int PHP5Hash( String s ) {
	int h = 5381;
	int count = s.length();
	int offset = 0;
        int len = count;
	if ( len > 0) {
	    int off = offset;
	    char val[] = s.toCharArray();

            for (int i = 0; i < len; i++) {
                h = 33*h + val[off++];
            }
        }
        return h;
    }

最初に出回ったExploitは「Ez」と「FY」を上記関数で計算した結果のハッシュ値が同じ値になることを利用していましたが、これには他の組み合わせがいくらでも存在し、例えば「PH」と「Oi」も同じ値となります。そのため

PHPH
PHOi
OiOi
OiPH

の4つは同じ値となり、「Ez」と「FY」の場合と同様に、もっと長い文字列とすることで攻撃が可能となります。攻撃者はかなり自由に文字列の組み合わせを選択できるため、単純なシグネチャではHashDoS攻撃を検知することはできません。

HashDoS検知のロジック

そこで、シグネチャマッチングによる検知はあきらめ、解析するコードを書くことで検知することにしました。

リクエストに含まれるパラメータの名前の部分に注目し、そのハッシュ値を計算します。通常、上記関数によって計算されるハッシュ値は、さまざまなパラメータの名前においてそれほど重複することはありません。数千個の英単語のうち、2、3個が重複する、といったイメージです。しかしHashDoS攻撃ではこの重複率が異常に高くなるので、実際にハッシュ値を計算し、その重複率を求めることで攻撃（明らかに不自然なケース）を検出することができると考えました。

ハッシュ値を計算すること自体はCPU負荷としては軽い処理なので、数千や数万のパラメータがある場合でもすぐに処理が終わり、DoS状態になることはありません。リクエストに含まれるパラメータの名前について、順番にハッシュ値を計算し、重複を取り除くためにHashSetに格納していきます。コードの断片は以下のようになります。

private Set hashSet1 = new HashSet();
...
hashSet1.add( Integer.toString( PHP5Hash( parameterName ) ) );

ここでHashSetクラスを利用していますが、HashSetクラスもHashMapと同様にDoS攻撃を受ける可能性があるため、実際のコードではHashSetに格納する前に、ランダムな値を足す対策をしています。ここでは分かりにくくなるため割愛しています。

攻撃でない場合の例として、パラメータが3つあり、それぞれ名前が「foo」「bar」「baz」である場合を考えます。この3つのハッシュ値はそれぞれ異なるため、計算後のハッシュ値をHashSetに追加していくと、HashSetのサイズは3になります。

次に攻撃の例として、パラメータ名が先ほど示した「PHPH」「PHOi」「OiOi」の場合を考えます。この3つのハッシュ値は同じ値となるため、計算後のハッシュ値をHashSetに追加していった場合、HashSetのサイズは1となります。

このように、パラメータの数と、計算後のハッシュ値の種類の比率を求めることで、HashDoS攻撃を検知します。

同名のパラメータの場合の問題

前項で示した方法の場合、次の例のような、同じ名前のパラメータが大量に存在する場合に誤検知を起こしてしまいます。

GET /?foo=1&foo=2&foo=3&foo=4&...

これらはパラメータ名が同じであるため、当然ながら計算されるハッシュ値も同じ値になってしまうからです。

このようなケースを判別できるようにするために、ハッシュ値をさらに別のロジックでも計算するようにします。文字列のハッシュ値の計算方法は1つだけではなく、JavaやPHP5、PHP4などでそれぞれ別のロジックが使用されています。パラメータ名がまったく同じであれば、別のロジックで計算したハッシュ値もやはり同じ値となります。しかし、「PHPH」「PHOi」「OiOi」のようなHashDoSを狙ったパラメータ名は、別のロジックで計算したハッシュ値はばらばらになるため、ここで問題にしている「同名のパラメータが多数ある場合」と区別することが可能です。

比率の設定

ScutumはWAFであるため、PHP5/PHP4/ASP/Javaなどに対するHashDoS攻撃はすべて検知することが目的です。そのため3つの関数を使ってハッシュ値を計算することにしました（PHP4とASPは同じロジックを用いているようです）。計算後のハッシュ値を、さらにHashSetに入れていきます。

hashSet1.add( Integer.toString( PHP5Hash( parameterName ) ) );
hashSet2.add( Integer.toString( PHP4Hash( parameterName ) ) );
hashSet3.add( Integer.toString( JavaHash( parameterName ) ) );

これらの3つのHashSetのうち、最も要素の数（サイズ）が大きいものに注目し、そのサイズがユニークなパラメータ名の数であると考えます（厳密には自然なハッシュ値の重複が無視されてしまうために異なりますが、この値はざっくりとした比率の計算に用いるため、特に問題ありません）。残りの2つのHashSetのサイズをこれと比較して、それぞれ比率を求めます。HashDoS攻撃の場合、あるHashSetについて、この割合が著しく低くなります。攻撃ではない場合には、ほぼ同数のユニークなハッシュ値の集合となるため、比率は1に非常に近い値となります。

通常、大量にあるパラメータ名についてハッシュ値を計算した場合、少なくとも98%以上はユニークになるだろう（=2%以上のハッシュ値が重複することはないだろう）と考え、比率を0.98と仮定します。残りの2つのHashSetについて、どちらか、あるいは両方の比率が0.98よりも小さい場合に、HashDoS攻撃だとみなします。攻撃に含まれるパラメータ名がきれいに同じハッシュ値になればなるほどこの比率は小さくなり、0.98どころか0.001等のような小さな値を示すことになります。

ソースコード

前項までに解説した内容を、次のようなクラスとして実装しています(ライセンスはGPLです)。(MHashDoSDetector.java)

public class MHashDoSDetector
{
public static final int UNKNOWN	= 0;
public static final int GOOD	= 1;
public static final int BAD	= 2;

public static float threshold = 0.98f;

private Set hashSet1 = new HashSet();
private Set hashSet2 = new HashSet();
private Set hashSet3 = new HashSet();
private int r = ( new Random() ).nextInt( 20000 );
//---------------------------------------------------------------
public void addParameterName( String parameterName )
{
hashSet1.add( Integer.toString( PHP5Hash( parameterName ) + r ) );
hashSet2.add( Integer.toString( PHP4Hash( parameterName ) + r ) );
hashSet3.add( Integer.toString( JavaHash( parameterName ) + r ) );
}
//---------------------------------------------------------------
public static int JavaHash( String s ) {
return s.hashCode();
}
//---------------------------------------------------------------
public static int PHP5Hash( String s ) {
	int h = 5381;
	int count = s.length();
	int offset = 0;
        int len = count;
	if ( len > 0) {
	    int off = offset;
	    char val[] = s.toCharArray();

            for (int i = 0; i < len; i++) {
                h = 33*h + val[off++];
            }
            //hash = h;
        }
        return h;
    }
//---------------------------------------------------------------
    public static int PHP4Hash( String s ) {
	int h = 5381;
	int count = s.length();
	int offset = 0;
        int len = count;
	if ( len > 0) {
	    int off = offset;
	    char val[] = s.toCharArray();

            for (int i = 0; i < len; i++) {
                h = 33*h ^ val[off++];
            }
            //hash = h;
        }
        return h;
    }
//---------------------------------------------------------------
public int getResult()
{
int uniqueParameterCount = hashSet1.size();
if( hashSet2.size() > uniqueParameterCount )
	{
	uniqueParameterCount = hashSet2.size();
	}
if( hashSet3.size() > uniqueParameterCount )
	{
	uniqueParameterCount = hashSet3.size();
	}

if( uniqueParameterCount < 500 )
	{
	return UNKNOWN;
	}
else
	{
	/*
	java.text.NumberFormat format = new java.text.DecimalFormat( "0.0000" );

	System.err.println( "----" );
	System.err.println( format.format( (float)hashSet1.size() / (float)uniqueParameterCount ) ) ;
	System.err.println( format.format( (float)hashSet2.size() / (float)uniqueParameterCount ) ) ;
	System.err.println( format.format( (float)hashSet3.size() / (float)uniqueParameterCount ) ) ;
	*/

	if( ( (float)hashSet1.size() / (float)uniqueParameterCount ) <= threshold
	 || ( (float)hashSet2.size() / (float)uniqueParameterCount ) <= threshold
	 || ( (float)hashSet3.size() / (float)uniqueParameterCount ) <= threshold
	  )
		{
		return BAD;
		}
	else
		{
		return GOOD;
		}
	}
}
//---------------------------------------------------------------
}

呼び出し側では、このクラスのインスタンスをリクエスト毎に生成し、パラメータ名を引数にして、addParameterNameをそれぞれのパラメータについて呼び出します。その後、getResult()を呼び出し、結果を取得してそれが攻撃であるかどうかを判断します。

このクラスは、例えばTomcatのようなJava製のアプリケーションに組み込んで使うことも可能です（筆者は個人的にテストしてみましたが、うまく動きました）。

パラメータ数の上限

HashDoS攻撃への対策として、多くのアプリケーションサーバやミドルウェアにおいて、単純にパラメータ数の上限（1000や10000など）が設定される方法が取られました。これは確かに多くの環境で有効なものではあるものの、それほどスマートな解決策であるとは思いません。世の中には実際に数千や数万のパラメータを使用するウェブアプリケーションもたくさん存在しますし、なにより上限が10000の場合などには、一応の攻撃が可能であるからです（わずか数秒CPU使用率を高めることができますが、並行して多数のリクエストを送りつければそれなりに有効な攻撃となります）。

本エントリで解説したハッシュ値に基づく対策でも、比率として2%の重複を許可しているために、例えば100万個のパラメータのうち2万個は重複が許されることになります。攻撃者が巧妙であれば、わざとこのような内容のリクエストを送り攻撃することが可能です。そのため、パラメータ数の上限として10万程度を設定しておき、さらにこの検出ロジックと組み合わせることで、とても有効な防御が可能と考えられます。

まとめ

今回は、実際にハッシュ値を計算することでHashDoS攻撃を検出する方法について解説しました。複数のロジックによってハッシュ値を計算することで、単純に同じ名前のパラメータが重複した場合と本当のHashDoS攻撃の違いを区別します。また、CookieへのHashDoS攻撃についても、同じクラス実装を用いることで検知が可能です。