だって、 hashdos 脆弱性の時、 Python とかの言語が、外部入力をハッシュに入れるときに衝突を狙えないように対策したのに、phpだけPOST処理で対策したからね？
json を受け取るような口もってるphpアプリのほとんどがhashdos残ってるんじゃない？
— INADA Naoki (@methane) 2015, 6月 17
このような状況に対して、約1年前にjson_decodeを入力経路とするHashosのPoC（概念実証コード）が公開されており、潜在的には「いつ攻撃があってもおかしくない」状況になっています。この攻撃をJSON HashDosと呼ぶことにします。本稿はJSON HashDosの概要を説明し、その影響と対策等について報告します。はじめに
昨年の11月17日、スイスの Lukas Martinelli によって、PHPのjson_decode関数にHashDos脆弱性があることと、具体的な攻撃方法が公表されました。PHP Denial of Service Attack Revisitedそして、この記事がPHP Internals - PHP Runtime Development Mailing List にて紹介されました（2014/12/23）。
http://lukasmartinelli.ch/web/2014/11/17/php-dos-attack-revisited.htmlSigh（やれやれ）の中身の心は「スイスの若造がいきなりこんなゼロデイ脆弱性をPoCつきで公表しやがって」くらいでしょうか(PoCは現在は削除されているようです)。しかし、皮肉なことに、このメーリングリストの投稿（公開です）により、この攻撃方法が広く知られることになってしまいました。
Sigh
[PHP-DEV] JSON HASHDOS （アーカイブ）より引用
以下、攻撃の概要と対策について説明します。
HashDosとは何だったか
古典的なHashDos(Hash Collision Attack)は、PHPをはじめ多くの言語で使用されているデータ構造「ハッシュテーブル」の「衝突(Collision)」を巧妙に悪用したサービス妨害攻撃です。ハッシュテーブルでは、キー文字列のハッシュ関数（MD5などの暗号的なハッシュ関数である必要はない）を用います。PHPで用いられているハッシュ関数はDJBX33Aと呼ばれるもので、概ね以下のようなコードです。実際のコードは速度最適化のためにこれより複雑です。
ulong get_hash(const char *arKey)
{
ulong hash = 5381; // 初期値
while (*arKey) {
hash = hash * 33 + *arKey++;
}
return hash;
}
この関数で求めたハッシュ値（整数）を配列に添字として用いることにより、平均的には、データのサーチ、挿入、削除をO(1)（定数オーダー）の時間で求めることができるというものです。しかし、最悪ケースでは「たまたま」ハッシュ値がすべてのデータで一致した場合は、すべてのデータが配列上の同じ添字のところに入る（衝突）ため、一件あたりのサーチ、挿入、削除の処理時間はO(N)（データ量に比例するオーダーの）時間になります。N件のデータの挿入はO(N ** 2) （データ量の2乗のオーダーの）時間がかかります。2011年末に28C3(28th Chaos Communication Congress)において発表されたHashDosのPoCでは、DJBX33AではEz、FY、G8等のハッシュ値が等しくなることから、これらを組み合わせることにより簡単にハッシュ値の衝突が起こせることを悪用していました。例えば、EzEz、EzFY、FYEz、FYFYは、上記のハッシュ関数ではいずれも0x17c84f603を返します（64ビット環境の場合）。その場合、ハッシュテーブルにデータを挿入する様子は下図で示されます。この図（アニメーションGIF）はLukas Martinelliのブログから引用しました。
28C3で発表されたPoCでは、HTTPのリクエスト（GET/POST/Cookie等）をPHPが内部的に連想配列（ハッシュ）として取り込むところを攻撃経路にしていました。この時点ではアプリケーションは処理を開始しておらず、アプリケーション側での対処は不可能なため、PHP5.3.9にて実行時設定max_input_varsが導入され、POST等の変数の数を制限する（デフォルトは1000）という対症療法がとられました。
JSON HashDosの概要
上記の「古典的HashDos」に対して、Lukas MartinelliのPoCは以下の点が異なっています。- json_decode関数によるJSONデータの受付処理を攻撃経路としている
- ハッシュの衝突をハッシュ値の下位16ビットに限定している
$body = file_get_contents('php://input'); // POSTデータを取得
$params = json_decode($body); // POSTデータをJSONとしてデコード
最近のWeb APIではJSONでデータをWebサーバーに送信（リクエスト）する場合が多いと思いますが、上記は、PHPでこれを実現する場合の典型的なコードでしょう。そして、Lukas MartinelliのPoCでは、ハッシュ値の衝突を起こすキー文字列は以下のようになっています（オリジナルのPoCでは2個目のキーが4wP2となっていますが、4wPの誤植と思われます）。
PoC: {"4vq":"key1", "4wP":"key2", "5Uq":"key3", "5VP":"key4", "64q":"key5" }
hash('4vq') = b879fc0
hash('4wP') = b879fc0
hash('5Uq') = b879fc0
hash('5VP') = b879fc0
hash('64q') = b879fc0
...
// 以下はgithub上で紹介されていたPoCに存在するキー
...
hash('aOtw') = 17c939fc0
...
hash('dUUuVB') = 652f7559fc0
Lukas MartinelliのPoCにて、ハッシュ値の衝突を下位16ビットに限定している理由は、PHPが内部で使用しているハッシュ表のサイズnTableSizeが2のn乗であり、ハッシュ値は nTableSize - 1でマスクして用いているからです。すなわち、実際には、ハッシュ値の下位ビットのみが用いられるため、すべてのビットが一致している必要はありません。実験
キーのハッシュ値下位16ビット（128K個のデータは17ビット）が全て一致するJSONデータを用い、先の「脆弱なコード」に処理させた結果を以下に示します。実行環境は、Windows7(Intel Core i7-4770 3.4GHz)上のVMware Playerで動くUbuntu12.04 32bitです。PHP-5.6.14
| データ数 | 実行時間（秒） | データサイズ(バイト) |
|---|---|---|
| 32K(2^15) | 5.7 | 346,157 |
| 64K(2^16) | 20.2 | 708,676 |
| 128K(2^17) | 91.3 | 1,435,685 |
参考までにPHP-7.0.0RC4での結果を以下に示します。ハッシュ関数の実装は変わっていないようですが、内部処理の高速化により、全体で 1.7倍から 2倍近く高速化されていて素晴らしいですね…しかし、HashDosの影響を受けること自体は変化がないようです。
PHP-7.0.0RC4
| データ数 | 実行時間（秒） | データサイズ(バイト) |
|---|---|---|
| 32K(2^15) | 3.2 | 346,157 |
| 64K(2^16) | 11.8 | 708,676 |
| 128K(2^17) | 46.0 | 1,435,685 |
攻撃の影響
JSON HashDosの影響により、CPU負荷が上昇し、新たなリクエストを受け付けにくい状態になります。一方、サーバーダウンや、内部情報の漏洩、データの改ざん等は発生しません。類似の脆弱性であるApacheKillerの場合は、メモリ消費量が急上昇することによりサーバーがダウンする可能性もあります（参考: Apache killerは危険～Apache killerを評価する上での注意～）が、HashDosは単にCPU負荷の上昇だけであり、攻撃がやめば比較的短時間にサーバーは復旧します。
現状での攻撃の有無
今回紹介するJSON HashDosについては、Lukas Martinelliの発表後一年近くが経ちますが、現実に攻撃に使われたとするニュースは見当たりません。それ以前の話として、過去に話題となったいわゆるApache KillerやオリジナルのHashDosについても、攻撃はほとんど見当たらない状況です。それは、下記に引用する金床氏のブログ記事でも指摘されています。数年前に発見されたHashDoSですが、実際に攻撃が行われているケースは殆ど目にしません。ソフトウェアのロジックを突くDoSとしては、他にApacheに対してRangeヘッダを使う攻撃手法(Apache Killer)なども発見されましたが、こちらも同様に、殆ど実際の攻撃としては検知していません。DoS攻撃にはもっと単純で、攻撃対象のアーキテクチャを調べる必要のない、シンプルな物量攻撃が好まれているような印象です。そのため筆者としてはHashDoSのセキュリティリスクは非常に低いものという認識です。
ScutumのゼロデイHashDoS対策と、JavaのXMLパーサ実装より引用
既存ソフトウェアへの影響
JSON HashDosは、PHPのjson_decode関数に外部データをそのまま与えると発生するというシンプルな条件なので、JSONを入力とするPHP記述のWeb APIでは該当する可能性があります。私は、WordCamp Tokyo 2015にて講演するため、そのネタ探しとして、WordPressに対するJSON HashDosの影響を調べたところ、以下が判明しました。
- WordPress 2.5から3.8.11（3.8系の最新版）はJSON HashDosの影響を受ける
従って、WordPress3.8以下をお使いのサイトは、緊急ではないものの、WordPressの最新版に移行することを推奨します。
対策
現状、HashDosや類似のDoS攻撃が実地に使用されるケースがないことと、単純なDoSであり情報漏えいや改ざん等には至らないことから、この問題に対策せず許容するという判断はあり得ると考えます。一方、JSON HashDosの影響を重視し、対策するとすれば、以下が考えられます。
(1) json_decodeの入力値を検証する
JSON HashDosの攻撃に用いるデータは、最低でも数十キロバイトはないと効果的でないため、入力値のバリデーションによりjson_decodeの入力値のデータサイズを制限できれば、攻撃を緩和できます。
(2) max_execution_time を制限する
max_execution_time は、スクリプトの最長実行時間で、この時間を過ぎるとPHP処理系により強制終了させられます。デフォルト値は30秒です。この時間を短くすると、JSON HashDosによる攻撃を早めに終わらせられるため、攻撃の緩和になります。
(3) JSONの代わりにXMLを入力とする
修正としては大掛かりになりますが、JSONの代わりにXMLを使用することでも対策になります。
筆者が確認したのは、SimpleXML系のライブラリですが、SimpleXMLを使用すると、XMLデータをPHPの配列ではなく、libxml2の内部形式でデータを保持し、かつlibxml2がHashDos対策がされているため、JSON HASH DOSの影響を受けないと考えられます（実証済み）。
一方、SimpleXMLではなく、xml_parse_into_structのようにXMLデータをPHPの配列に変換するような用法では、HashDosの影響を受けます。ただし、xml_parse_into_structはデフォルトでタグを大文字に変換するため、HashDosの影響は受けにくいのですが、以下のように大文字・小文字を区別する設定の場合は、json_decodeと同様にHashDosの影響を受けます。
(4) WAFによる防御$xml_parser = xml_parser_create(); // XMLパーサを生成 xml_parser_set_option($xml_parser, XML_OPTION_CASE_FOLDING, 0); // 大文字と小文字を区別
WAF(Web Application Firewall)によっては、JSON HashDosの防御機能を備えるものがあります。詳細についてはお問い合わせください。
まとめ
JSON HashDosについて、原理とその影響、WordPressの旧バージョンが影響を受けること、攻撃の現状と対策について報告しました。PHPのJSON HashDosは、未対策のまま一年近くが経過していますが、いまだ攻撃の兆候はありません。
PHP JSON HashDosは、いわゆるゼロデイ脆弱性ではありますが、当面攻撃の兆候がないこと、PHP7でも対策される見込みがないこと、セキュリティの専門家（攻撃者を含む）には既知の内容なのに開発者には情報が行き渡っておらず、攻撃側に情報が偏っている状態であることから、ここに問題の概要を報告し、注意喚起するものであります。
情報提供のお知らせ
スクリプトキディ等による悪用防止のため、この記事は攻撃の詳細を割愛しております。技術的な詳細情報を希望される方には、原則として無償で、情報提供をさせていただきます。ただし、秘密保持の観点から、対象は法人など実在確認のとれる団体に限らせていただきます。また、オープンソース・ソフトウェアの開発者等に対しても、情報提供いたします。以下のページよりご連絡ください。お問い合わせ - HASHコンサルティング株式会社WordCampの私のセッションにてWordPress 3.8に対するJSON HashDosのデモを予定しております。ただし、WordCampはセキュリティ専門家向けのカンファレンスではないため、あくまで概要の報告になります。