気になった
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もサイズ制限するという記述が必要なのでは?