2014年01月06日

PHPのセッションIDは暗号論的に弱い乱数生成器を使っており、セッションハイジャックの危険性がある

はてなブックマークに登録

下記の文章は、PHPのセッションIDに対する攻撃についてFull Disclosure MLに2010年に投稿された文章を和訳したものです。訳者の意見としては、攻撃の成立条件は極めて厳しく、そこまで深刻度は高くないと考えています。

とはいえ、疑似乱数列への攻撃がどのように行われるのか、その可能性を示す文章は比較的珍しいもののように思います。暗号論的に安全な疑似乱数とは何か、なぜ必要なのかといった内容を間接的に教えてくれる面白い文章だと感じましたので、今回翻訳してみました。

(以下、原文の和訳です)

PHPのセッションIDは暗号論的に弱い乱数生成器を使っており、セッションハイジャックの危険性がある

原文:http://seclists.org/fulldisclosure/2010/Mar/519

Advisory (c) 2010 Andreas Bogk <andreas () andreas org>

Product:
PHP
Version:
5.3.2 以降
脆弱性の種類:
暗号論的な弱さ、セッションハイジャック
深刻度:

概要

PHPはセッションIDを生成する際、暗号論的に弱い乱数生成器を利用しています。加えて、乱数生成器の初期シードに十分なエントロピーが確保できていません。さらに一部のエントロピーについてはuniqid()関数を不注意に利用している場合に外部に漏れてしまいます。これらの弱点が相互作用してPHPのセッションIDの可能性を狭めてしまい、Webサーバに対するセッションIDの総当たり攻撃が可能になることがあります。

必要条件

以下の条件を満たすとき、PHP製サービスは今回指摘する攻撃に対して脆弱になります。

  • PHP標準のセッション機構を利用している
  • uniqid関数の第二引数 "more_entropy" にtrueを指定している箇所があり、その返り値がユーザーから見える
  • FastCGIのようなPHPインタプリタを維持する機構を利用している
  • 同じサービスを利用している他ユーザーのログイン状況とリモートアドレスが公開されている

攻撃の詳細

今回の攻撃のゴールは、有効なセッションIDを推測し、特定のユーザーのふりをしてセッションを乗っ取ることです。PHPの標準のセッション機構ではsession_id()関数経由でセッションIDが提供されます。セッションIDはHTTPレイヤーではクッキーまたはリクエストパラメータの形でPHPSESSIDまたはPHPSESSIONIDという名前で受け渡されます。

セッションIDがどう作られるのかを理解するため、セッションIDを生成しているコードを見てみましょう。

---- ext/session/session.c, php_session_create_id() -----
        spprintf(&buf, 0, "%.15s%ld%ld%0.8F",
                 remote_addr ? remote_addr : "",
                 tv.tv_sec,
                 (long int)tv.tv_usec,
                 php_combined_lcg(TSRMLS_C) * 10);

        switch (PS(hash_func)) {
                case PS_HASH_FUNC_MD5:
                        PHP_MD5Init(&md5_context);
                        PHP_MD5Update(&md5_context,
                                      (unsigned char *) buf,
                                      strlen(buf));
                        digest_len = 16;
                        break;
---------------------------------------------------------

"remote_addr" というのはCGI環境に渡されたユーザーのリモートアドレスで、ドット区切りのIPv4アドレス文字列です。"tv" はID生成時にgettimeofday()が返すtimeval構造体です。php_combined_lcg() は乱数生成器で、このあと詳しく見ていきます。

まとめると、PHPはユーザーのリモートアドレスと、そのときのサーバのマイクロ秒精度の時刻と疑似乱数値を元にしたMD5値をセッションIDとして利用しています。

攻撃者が有効なセッションIDを得るためには、元になった全パラメータを知る必要があります。もう少し正確に言えば、総当たり攻撃が可能な程度にパラメータを絞り込めれば十分です。では、これらのパラメータについて詳しく見ていきましょう。

リモートアドレス

リモートアドレスをPHPが知らない(空文字列になる)という自明な場合を除けば、この攻撃が成功するかどうかはIPアドレスがわかるかどうかに依存します。

たとえば匿名のWikipediaユーザーの場合のように、PHPアプリケーションがリモートアドレスを単に表示することもありえます。もう少し現実的な場合を考えると、攻撃者が攻撃者のコントロール下にあるURLに被害者をアクセスさせることもありえます。つまり、攻撃サイトに画像リンクを置いて被害者に画像を見させるなどです。

これらが全て失敗した場合、攻撃者は被害者に関する知識を利用するしかありません。たとえば住んでいる街やISP、勤務地やよく使われるproxyサーバなどを元にIPアドレスを限定することはできます。とはいえ攻撃の労力は増えてしまうでしょう。

IPv6を使っている場合は特別です。ここで注意すべきことは、上記コードではリモートアドレスの最初の15文字しか使われていないということです。これはIPv6のアドレス表記で言うと最初の6オクテットに相当します。この6オクテットは同一ISP内であればまず変わりません。また、現在のIPv6アドレス空間の利用状況はスカスカなので、有効なプレフィックス全てを試すことは十分現実的です。

(訳注:SSLアクセラレータ配下のPHP環境やnginx+php-fpm環境など、リモートアドレスが単に127.0.0.1やその他のプライベートIPアドレスになっている環境があります。このような場合、リモートアドレス部分で担保できるエントロピーは無いということになってしまいますので注意してください。)

タイムスタンプ

セッションID生成時、MD5処理前の情報量の多くはgettimeofday()関数由来です。しかし、NTPサーバがどこにでもある昨今、攻撃者は単に自分の時計を見ればサーバ時刻のとても良い推測値が得られます。さらに、多くのHTTPサーバは秒精度でサーバ時刻を返してくれます。

攻撃対象のPHP製サービスに被害者がオンラインかどうか状態を表示する機能がついていた場合、攻撃者はセッションIDが生成された瞬間のタイムスタンプ値を推測できます。gettimeofday()関数はマイクロ秒単位の解像度を持ちますので、理屈で言えば、オンラインかどうかの観測を1マイクロ秒刻みで行うことで1個の推測値を得ることができます。もちろん、実際のシステム時刻と推測値とのズレ幅について計算に入れる必要があります。実際には、gettimeofday()が1msまたは10msの精度しか持たない環境もありますので、こうした場合は、必要な試行回数はかなり抑えられます。

とはいえ、攻撃者が正しいセッションIDを生成する上で、タイムスタンプを正確に予測することは大きな障害です。これに対し、uniqid()関数は攻撃者の時計とサーバーの時計のズレを精密に知る上で助けになります。これについては乱数生成器の予測についての文脈で議論していきましょう。

乱数生成器

PHPのセッションIDの最後の構成要素はphp_combined_lcg()から得られた値です。この関数は2つの線形合同法(LCG)を組み合わせた実装であり、それぞれが32bitの状態を持ちます。Samy Kamkar[1]が指摘した通り、これは暗号論的に安全な疑似乱数生成器ではありません。乱数生成関数の内部状態さえ得られれば、それまでに生成された値もこれから生成される値も予測することができます。これは驚くには値しません。線形合同法が暗号論的に弱いことは学術論文においては1977年に指摘されています。

しかし、我々は乱数生成器の内部状態を直接知ることはできません。では、php_combined_lcg() 関数の中身を見てみましょう。

---- ext/standard/lcg.c ----
PHPAPI double php_combined_lcg(TSRMLS_D)
{
        php_int32 q;
        php_int32 z;

        if (!LCG(seeded)) {
                lcg_seed(TSRMLS_C);
        }

        MODMULT(53668, 40014, 12211, 2147483563L, LCG(s1));
        MODMULT(52774, 40692, 3791, 2147483399L, LCG(s2));

        z = LCG(s1) - LCG(s2);
        if (z < 1) {
                z += 2147483562;
        }

        return z * 4.656613e-10;
}
----------------------------

我々はこの関数の出力から2^31通りの値しか得ることができません。とはいえ、ここから我々はかなりの情報を得ることができます。もし内部状態のうち35bitを言い当てられれば、1回の出力を元に総当たり攻撃で内部状態を特定することができるでしょう。

次に、lcg_seed() についても考えてみましょう。

---- ext/standard/lcg.c ----
static void lcg_seed(TSRMLS_D) /* {{{ */
{
        struct timeval tv;

        if (gettimeofday(&tv, NULL) == 0) {
                LCG(s1) = tv.tv_sec ^ (tv.tv_usec<<11);
        } else {
                LCG(s1) = 1;
        }
#ifdef ZTS
        LCG(s2) = (long) tsrm_thread_id();
#else
        LCG(s2) = (long) getpid();
#endif

        /* Add entropy to s2 by calling gettimeofday() again */
        if (gettimeofday(&tv, NULL) == 0) {
                LCG(s2) ^= (tv.tv_usec<<11);
        }

        LCG(seeded) = 1;
}
----------------------------

これはPHP 5.3.2で修正されたコードで、Samyの攻撃を解決するものとされています。2回目のgettimeofdayの呼び出しが新しいコードです。古いコードでは、getpid()の呼び出しがs2と名付けられた線形合同法の唯一のエントロピー源でした。そして、Samyのコードは非常に賢くこの性質を利用し、時間とメモリ使用量のバランスが取れた攻撃を組み立てていました。

しかし、上記の最新版ソースコードを見てみましょう。我々がすぐ気づくことは、初期シードに予測不可能なエントロピー源が使われていないということです。ここで使われているエントロピー源はプロセスIDとgettimeofday()の値です。すでに説明したように、現在時刻の上位ビットについては攻撃者が予測可能です。マイクロ秒部分の下位ビットだけが真のエントロピーと言えるものを提供してくれます。また、プロセスIDについては、システムリブート直後であれば予測可能な傾向があります。

ここで、攻撃者がphp_combined_lcg() の結果を見る方法があったと仮定してみましょう(すぐ後にそれが事実になるんですけどね)。この状況で攻撃者がすべきことはシステムリブートを待つことです。これは、対象のシステムにICMP Echoリクエストをずっと送り続けて、いったん反応がなくなって再び反応するようになるのを待つなどすれば実現できます。システムリブート後、攻撃者はいくつか乱数をシステムから取り出し、PIDと時刻の値について良い推測値を付け加え、システムから取り出した乱数と一致するまで総当たり攻撃を行って線形合同法の内部状態を得ることができます。

この総当たり攻撃にはどれくらいの時間がかかるのでしょうか?これを推測するには、まず手元のマシンで2回gettimeofday()を呼び出してみて結果がほぼ同じであることとを確認して、両者の経過時間を測定してみましょう。おそらく、OSのスケジューリングによる割り込みが発生しなければ、両者は1桁マイクロ秒の差しか出ず、ほんの数ビットのエントロピーしか与えないはずです。(訳注:lcg_seed()の1回目と2回目のgettimeofday()で何マイクロ秒の差が出るのか推測値を得る必要があるという意味でしょう)

もし乱数生成器の初期シードに使われたサーバ時刻を1秒以内に限定できたと仮定すると、マイクロ秒部分で20ビットとPIDで15ビットのエントロピーが残ります。線形合同法による値の生成は1回の除算と3回の乗算が必要なので、2つの線形合同法で8回の浮動小数点演算が必要になります。最新のGPUであれば1TFLOPSの処理ができますので、1秒以下で解空間を調べ尽くせます。

ですから、パズルの最後のピースは、攻撃者が線形合同法による疑似乱数値をどこから得るのかということです。その答えは、サーバーがuniqid()関数を呼んで、攻撃者にその値を渡すのを期待することです。またまたコードを見てみましょう。

---- ext/standard/uniqid.c, PHP_FUNCTION(uniqid) ----
        gettimeofday((struct timeval *) &tv, (struct timezone *) NULL);
        sec = (int) tv.tv_sec;
        usec = (int) (tv.tv_usec % 0x100000);

        if (more_entropy) {
                spprintf(&uniqid, 0, "%s%08x%05x%.8F", prefix, sec,
                usec, php_combined_lcg(TSRMLS_C) * 10);
        } else {
                spprintf(&uniqid, 0, "%s%08x%05x", prefix, sec, usec);
        }
-----------------------------------------------------

わかりましたか?uniqid関数は我々にサーバーの時刻を精密に教えてくれるだけでなく、我々が"more entropy"を要求すれば線形合同法の出力まで追加してくれるのです。イェイベイビー、もっとエントロピーをちょうだい、そうすればセッションIDの総当たり攻撃ができるよ!

コホン、おっと失礼。もし私がuniqid()を通じてphp_combined_lcgから最初に値を取り出したのだとすれば、私が受け取ったタイムスタンプは線形合同法の初期シードに使われたタイムスタンプとほとんど同じ値である、という事実に注意してください。というのも、両者はプログラムの手順として非常に近いタイミングで呼び出されるからです。これにより、不明なエントロピーをPIDの分と数十マイクロ秒程度まで減らすことができます。(訳注:これまでの説明と合わせて考えると、0.1ミリ秒以下の時間でLCGの内部状態に対する総当たり攻撃が終わるということになります)

PHPアプリケーション中の"xxxxxxxxxxxxx.dddddddd"というフォーマットのデータには気をつけてください。ここでのxは16進数でdは10進数です(訳注:これはuniqid()の返り値の特徴です)。これはURLの一部やCookieやファイルアップロード時に自動生成されるファイル名だったりするでしょう。ここから攻撃の材料になる情報が漏洩します。

uniqid()の出力を得る代わりに、強力なコンピュータの計算能力を使うことできる点にも注意してください。攻撃者は自分自身のリモートアドレスとログイン時間を知っており、自分のセッションIDにもアクセスできます。また、これまでに説明した通り、線形合同法の出力は31ビットのエントロピーを持ちます。マイクロ秒部分に含まれる不確実性の20ビットを追加すると、攻撃者のCookieを元に線形合同法の内部状態を総当たり攻撃するのに、MD5処理が計2^51回必要です。最新のGPUはMD5処理を1秒に2^30回行えるので、我々は2^21GPU秒を使えばよいことになります。これは巨大な組織であれば十分現実的でしょう。

まとめ

これまで説明してきた攻撃の手順をまとめます。

  • サーバのリブートを待ちます。
  • uniqid()の値を取得します。
  • その結果を利用し、総当たり攻撃で乱数生成器の初期シードを特定します。
  • ターゲットのログイン状況をポーリングして、被害者が出現するのを待ちます。
  • ログイン状況のポーリングと並行してuniqidのポーリングを行います。これはサーバ時刻と乱数生成器の値を調べ続けるためです。
  • ポーリングで得られた時刻と乱数生成器の値を利用して、セッションIDに対する総当たり攻撃を行います。

制限

この攻撃が成功するためには、攻撃対象のシステムについて、これまで説明したような性質が全て備わっている必要があります。また、この攻撃は攻撃対象のシステムにかなりの負荷をかけます。とはいえ、uniqid()の漏洩の代わりに攻撃者が用意したコンピュータの計算能力を使うこともできますし、その他の情報をその他の方法で集めることも可能ですから、攻撃の成立には多少の柔軟性があります。

PHP利用者へ推奨すること

  • セッションIDには十分なエントロピーが使われていることを確認しましょう。バージョン0.9.31以降の Suhosin[2]パッチを利用すれば自動的にエントロピーが高まります。(訳注:Suhosinパッチを使うかわりに、php.iniで「session.entropy_file=/dev/urandom」「session.entropy_length=32」と設定する方が最近の定番だと思います。また、PHP 5.4.0以降はこの設定がデフォルト値になっています。)
  • uniqid()の値を直接使わないようにし、常にハッシュ関数を適用した値を使うようにしましょう。これは第1項目とは直行するものです。特に、あなたのプログラムでuniqid()の値が他人に推測不可能であることを前提としている場合は重要です。

PHP本体のメンテナへ推奨すること

  • ユーザーが危険なセッションIDを生成できないようにすべきです。近年のプラットフォームで性質の良い乱数列を持たないものはありません。これを初期シードに使うべきです。線形合同法の代わりに chained hash や cipher を使うべきです。
  • uniqid()が必ずハッシュ値を返すようにすべきです。
  • セッションIDはMD5でなくSHA384にすべきです。
  • Schneierを読みましょう。(訳注:『暗号技術大全』を読めの意味?)

謝辞

この調査を行う刺激を与えてくれた Samy Kamkar と、意見をくれた Stefan Esser に感謝を表します。Jarno Huuskonen が9年前に同じ問題を指摘していた[3]ことにも敬意を表します。

(ここまでが原文の和訳です)

訳者による補足

上記の乱数生成器の初期シードへの攻撃は、乱数生成器が最初に返す値にアクセスできることを前提にしています。原文ではそれほど強調されていませんが、サーバリブートを待つことはプロセスIDを推測しやすくするためだけでなく、乱数列の1つ目の値を攻撃者が手に入れる上でも重要なのです。サーバリブートを待たないと攻撃が成立しないというのは条件としてかなり厳しいように思います。

また、乱数生成器はプロセスごとに別々の乱数列を持ちます。Webサーバ複数台構成の環境を考えると、攻撃を成立させるには全Webサーバの全プロセスの線形合同法の初期シードを知る必要があります。というのも、セッションID生成の際にどの乱数生成器が使われたかを外部から知ることはできないからです。

さらに、全ての乱数生成器の初期シードがわかっているとしても、ある時点で乱数生成器が乱数を何個生成したかを外部から知る方法もありません。uniqid()のポーリングである程度まで絞り込むことはできますが、それでも限度があります。どの乱数生成器が使われたか、何個目の乱数が使われたか、全ての可能性をカバーしないと任意のユーザーのセッションハイジャックを成立させることはできません。以上を加味して考えると、攻撃の成立は非常に難しいと言えそうです。

とはいえ、むやみに線形合同法の出力をユーザーに見せるべきではない、というのは重要な指摘です。この文書ではuniqid()関数の利用に注意すべきだと指摘していますが、lcg_value()関数にも注意が必要です。これは線形合同法による疑似乱数値をそのまま返す関数ですので、uniqid()と同様、この値をそのままユーザーに見える形で使ってはいけません。

文中でも説明があった通り、PHP5.3.1以前および5.2.12以前のバージョンでは乱数生成器のシードがさらに推測しやすいものになっていました。Samy Kamkarによる、これらのバージョンに対する攻撃コードとデモが[1]にありますので、併せて参照してください。


@hnw
klab_gijutsu2 at 18:00│Comments(0)TrackBack(0)php 

トラックバックURL

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント