ichirin2501's diary

いっちりーん。

気になった

CVE-2011-4885が気になったので調べてみました。
脆弱性対策情報データベースには

PHP は、ハッシュ衝突を想定して制限を行わずにフォームパラメータのハッシュ値を算出するため、
サービス運用妨害 (CPU 資源の消費) 状態となる脆弱性が存在します。
影響を受けるシステムは PHP5.3.9未満

実際にどのような処理が行われてるのか見てみる。
公式からPHP5.2.17のソースコードをダウンロードしてきて、
ハッシュ計算を行なっているを部分を探すと、
Zend/zend_hash.h

254 static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
255 {
256         register ulong hash = 5381;
257 
258         /* variant with the hash unrolled eight times */
259         for (; nKeyLength >= 8; nKeyLength -= 8) {
260                 hash = ((hash << 5) + hash) + *arKey++;
261                 hash = ((hash << 5) + hash) + *arKey++;
262                 hash = ((hash << 5) + hash) + *arKey++;
263                 hash = ((hash << 5) + hash) + *arKey++;
264                 hash = ((hash << 5) + hash) + *arKey++;
265                 hash = ((hash << 5) + hash) + *arKey++;
266                 hash = ((hash << 5) + hash) + *arKey++;
267                 hash = ((hash << 5) + hash) + *arKey++;
268         }
269         switch (nKeyLength) {
270                 case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
271                 case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
272                 case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
273                 case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
274                 case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
275                 case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
276                 case 1: hash = ((hash << 5) + hash) + *arKey++; break;
277                 case 0: break;
278 EMPTY_SWITCH_DEFAULT_CASE()
279         }
280         return hash;
281 }

DJBX33Aという名称のハッシュ値算出方法らしい。
上記のコードは地味に高速化されているけど、計算式は以下のようになっている。
hash(0) = 5381
hash(i) = hash(i-1) * 33 + str[i] (mod 2^32
2文字に絞って、ハッシュ値が同じになるものを全探索で調べてみると、

#!/usr/bin/env python
#! -*- coding:utf-8 -*-

import itertools

def calc(s): #str -> integer
    h = 5381
    mask = 2 ** 32 - 1
    for c in s:
        h = ((33 * h) + ord(c)) & mask
    h = ((33 * h) + 0) & mask
    return h

def main():
    a = ''.join([chr(x) for x in xrange(256)])
    d = {}

    for x in itertools.product(a, repeat=2):
        s = ''.join(x)
        h = calc(s)
        if d.has_key(h):
            d[h].append(s)
        else:
            d[h] = [s]

    print d
    print len(d)

if __name__ == "__main__":
    main()
$ python hashcoli.py
{193560576L: ['\xa1\xfa', '\xa2\xd9', '\xa3\xb8', '\xa4\x97', '\xa5v', '\xa6U', '\xa74', '\xa8\x13'], 
193593345L: ['\xbf\xfd', '\xc0\xdc', '\xc1\xbb', '\xc2\x9a', '\xc3y', '\xc4X', '\xc57', '\xc6\x16'], 
193626114L: ['\xde\xdf', '\xdf\xbe', '\xe0\x9d', '\xe1|', '\xe2[', '\xe3:', '\xe4\x19'],
193658883L: ['\xfc\xe2', '\xfd\xc1', '\xfe\xa0', '\xff\x7f'],
...
8671

2文字のパターンは256*255=65280あるはずなのに、
重複しないハッシュ値は8671パターンしかない。
この2文字の文字列を利用してハッシュ衝突を起こす異なる文字列が大量に生成できます。
同じハッシュ値の集合を一つ例に出すと、
193462599L: ['G\xfb', 'H\xda', 'I\xb9', 'J\x98', 'Kw', 'LV', 'M5', 'N\x14']
これらを使ったKwLVLV, LVKwM5, M5M5Kwなどの文字列は全て同じハッシュ値になります。
そもそも、ハッシュ値の算出方法からして
ある値xに対して、2文字の文字列をハッシュ計算に適応させると、
33 * {(33 * x + str[0]) % 2^32} + str[1] (mod 2^32
合同式の性質から(途中は端折ります)
= {(33^2 * x) % 2^32} + {(33 * str[0]) % 2^32} + {str[1] % 2^32} (mod 2^32
この式を見ると、文字の値は範囲[0,255]なので、
後ろ2つの項は値が変化しないことがわかります。
33 * str[0] + str[1] = 33 * str'[0] + str'[1]
この等式が成り立つ2文字の文字列の場合、
ある値xが同じなら必ず同じハッシュ値になります。
これでハッシュ衝突を起こす異なる文字列が大量に作れるというわけです。


GETやPOSTリクエストで送信するデータはわかりましたが、
PHPはハッシュテーブルの処理をどの段階で行なっているのかが気になりました。
そこで、ハッシュテーブルの処理を行なっているであろう、
Zend/zend_hash.c に定義されていた以下の関数
_zend_hash_add_or_update
zend_hash_find
に、適当に処理を追記してコンパイルし、動作確認を行いました。
当初の予想では、スーパーグローバル変数である$_GET, $_POSTが
呼ばれた段階で処理されるものだと考えていましたが、
PHPソースコードに$_GET, $_POSTが一切記述されていなくても、
ハッシュテーブルへの追加、更新、検索処理は行われていました。
PHPで動いているなら同様にDOS攻撃が行える、ということ…。
怖すぎ。


この脆弱性に対して、対策された最新版の5.3.9では、
Added max_input_vars directive to prevent attacks based on hash collisions. (CVE-2011-4885)
ということなので、パラメータ数に制限が加わったようです(ソースは未確認)
IPAの記事には回避策として、

・リクエストごとの処理時間を制限する
・POST リクエストのサイズを制限する
・リクエストごとのパラメータ数を制限する

とありますが、
HTTP1.1の仕様上、HTTPリクエストにサイズ制限はないので、
POSTだけじゃなくて、GETもサイズ制限するという記述が必要なのでは?