ichirin2501's diary

いっちりーん。

記号

ご無沙汰です。
はてなブログに貼り付けるつもりでしたが、ハイライトがまだ効かないのでこちらに。
バイナリエディタの開発を一旦中断して、夏コミネタに向けて違うことしてました。
その結果↓

__attribute__((section(".text"))) char main[] = 
    "%@@@@%!!!!-|||!-$*:!-/~{<`[[[[[[[%@@@@%!!!"
    "!-!!!!%!!!!`[[[[[[[%@@@@%!!!!-!!!!-!!!!-!|"
    "|]-!:`)-|:`~`[[[[[[[%@@@@%!!!!-!@!!%:+@@-`"
    "!@@`[[[[[[[%@@@@%!!!!-?!?!-&&:%-/?|``[[[[["
    "[[%@@@@%!!!!-!!?!--:$!-??/[`[[[[[[[%@@@@%!"
    "!!!-]!!!-%`!,-~~\\?`[[[[[[[%@@@@%!!!!-]!?!"
    "-%{:`-~{|~`[[[[[[[%@@@@%!!!!-!!!!%:^\\\\-_"
    "\\\\\\`[[[[[[[%@@@@%!!!!-!!!!%$!!!`[[[[[[["
    "%@@@@%!!!!-!!!!-@@@!%+,,[-{{{``[[[[[[[%@@@"
    "@%!!!!-!!!!-/*\\[-`/~{`^^^^^^^^%@@@@%!!!!-"
    "!!]]-$?::-`~<<`________!~,%@@@@%!!!!-!]!!-"
    "#:##-`<@@`________)~,____";

このままでは動きません。
スタックの実行権限許可と、書き換え許可を行う必要があります。
さらに絶対アドレスを使用しているため強く環境に依存します。
動作確認
gcc (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4)
kernel 2.6.35.14-103.fc14.i686
プログラムヘッダ?の書き換え許可の変更には、
http://ph.halfmoon.jp/
trash -> 「プログラムヘッダのパーミッションをrwx にするスクリプト
をお借りした。

$ gcc kigou.c -z execstack
$ python pgm_hdr.py < a.out > b.out
$ chmod 755 b.out
$ ./b.out
$ assembly


本来の目的は、このプログラムを書くためのプログラムを書くことでした。
作成過程を夏コミネタにしようと思います。受かれば、ですが。


参考
http://perl-users.jp/articles/advent-calendar/2010/sym/16

近況

訳あってめでたくニートになりました。それは置いておいて、

特に記事にするようなネタがないのですが、更新する意思表示も含め、近況報告です。

現在、バイナリエディタを開発中です。

「低機能バイナリエディタ いっちー君」

として公開予定です(コミケネタになる可能性有り)。

今のところ、Linuxのみ、CUIでの動作を想定しています。

巨大なデータも扱えるように、データ構造としては PieceTable を採用(実装済み)、

Undo, Redoともに実装済みです。

以上

 

ζ*'ヮ')ζ<$_

ブログの方向性が迷子なので、ちょっと考えます。
方向が定まったら、恐らく新しいブログに移行すると思います。
新ブログ予定地 : ichirin2501's diary
競技プログラミング記事 : rintpsyの日記

気になった

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

urllib2周辺は触りたくないですね

またpythonでネットワークプログラミングする機会があったのだけど、
urllib2付近の処理が面倒です。いい加減、処理をまとめようと思って作成してみた。
複雑なことは出来ないけど、簡単なことならこれで十分。
Cookieはデフォルトで機能します。
POSTするデータは辞書のまま渡す、わざわざurlencodeしなくてもいい。

# -*- coding: utf-8 -*-
# python 2.7
import urllib2
from cookielib import CookieJar
from urllib import urlencode

class request():
    def __init__(self, debug=None):
        self.opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(CookieJar()))
        if debug :
            for h in self.opener.handlers:
                if isinstance(h, urllib2.HTTPHandler):
                    h._debuglevel = 1
                elif isinstance(h, urllib2.HTTPSHandler):
                    h._debuglevel = 1

    def get(self, url, _headers={}):
        req = urllib2.Request(url, headers=_headers)
        return self.opener.open(req)

    def post(self, url, _data={}, _headers={}):
        req = urllib2.Request(url, data=urlencode(_data), headers=_headers)
        return self.opener.open(req)


header = {
    'User-Agent' : 'Mozilla/5.0 (X11; U; Linux i686; en-US) AppleWebKit/534.16 (KHTML, like Gecko) Chrome/10.0.648.205 Safari/534.16'
}

url = "https://www.hatena.ne.jp/login"
r = request(debug=True)
res = r.post(url, {'name':'ichirin2501', 'password':'****'}, header)
print res.read()