PythonによるBloom Filter(Counting Filter)の実装

はじめに

PythonでBloom Filter(Counting Filter)の実装を行いました.
特定のデータが既にデータ構造内に保存されているかを,高速に判定できるアルゴリズムです.(計算量はO(ハッシュ関数の個数))
Apache HBase等でも用いられており,大規模データに対する特定のデータの存在性判定に向いているようです.

なお,Bloom Filterには偽陽性,つまりデータが保存されていないのに保存されていると判定されることがあります.(でもBloom Filterの配列要素数がある程度大きければそれなりの精度は出せるっぽいです.)

Bloom Filterに関する詳しいアルゴリズムは以下が参考になると思います.

ブルームフィルタ - Wikipedia

知っておくと便利な Bloom Filter - kakakakakku blog

実装

全然テストしてないのでバグがあるかも,許して...

import hashlib

SELECT_ADD    = 1
SELECT_SEARCH = 2
SELECT_REMOVE = 3
SELECT_QUIT   = 4

class Bloomfilter:
    def __init__(self):
        self.table = [0] * (2**16)

    # Use md5, sha256, sha384 hash value to determine
    def get_hashvalue(value):
        md5value    = int(hashlib.md5(value.encode()).hexdigest(), 16) % (2**16)
        sha256value = int(hashlib.sha256(value.encode()).hexdigest(), 16) % (2**16)
        sha384value = int(hashlib.sha384(value.encode()).hexdigest(), 16) % (2**16)

        return md5value, sha256value, sha384value

    def add(self, value):
        md5value, sha256value, sha384value = Bloomfilter.get_hashvalue(value)
        self.table[md5value]    = 1
        self.table[sha256value] = 1
        self.table[sha384value] = 1

    def is_exist(self, value):
        md5value, sha256value, sha384value = Bloomfilter.get_hashvalue(value)
        return (self.table[md5value] and self.table[sha256value] and self.table[sha384value])


class Countingfilter(Bloomfilter):
    # Override
    def add(self, value):
        md5value, sha256value, sha384value = Bloomfilter.get_hashvalue(value)
        self.table[md5value]    += 1
        self.table[sha256value] += 1
        self.table[sha384value] += 1

    
    def remove(self, value):
        md5value, sha256value, sha384value = Bloomfilter.get_hashvalue(value)
        self.table[md5value]    -= 1
        self.table[sha256value] -= 1
        self.table[sha384value] -= 1


def menu():
    while True:
        user_input = input("[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> ")
        if user_input.isdigit() and SELECT_ADD <= int(user_input) <= SELECT_QUIT:
            return int(user_input)


def main():
    user_input = ""
    countingfilter = Countingfilter()

    while True:
        user_input = menu()

        if user_input == SELECT_ADD:
            add_value = input("[?] Value to add >> ")
            countingfilter.add(add_value)
            print("[*] '{}' Successfully added.".format(add_value))

        if user_input == SELECT_SEARCH:
            search_value = input("[?] Value to search >> ")
            
            if countingfilter.is_exist(search_value):
                print("[*] '{}' may be stored.".format(search_value))
            else:
                print("[*] '{}' is NOT stored.".format(search_value))

        if user_input == SELECT_REMOVE:
            remove_value = input("[?] Value to remove >> ")
            
            if countingfilter.is_exist(remove_value):
                countingfilter.remove(remove_value)
                print("[*] '{}' is Successfully removed.".format(remove_value))
            else:
                print("[*] '{}' is NOT stored. Failed to remove.".format(remove_value))

        if user_input == SELECT_QUIT:
            break
        
        print()

    print("[*] Quit.")


if __name__ == '__main__':
    main()

結果

$ python bloomfilter.py 
[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 1
[?] Value to add >> hoge
[*] 'hoge' Successfully added.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 1
[?] Value to add >> fuga
[*] 'fuga' Successfully added.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 2
[?] Value to search >> hoge
[*] 'hoge' may be stored.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 2
[?] Value to search >> fuga
[*] 'fuga' may be stored.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 2
[?] Value to search >> piyo
[*] 'piyo' is NOT stored.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 3
[?] Value to remove >> piyo
[*] 'piyo' is NOT stored. Failed to remove.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 3
[?] Value to remove >> hoge
[*] 'hoge' is Successfully removed.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 2
[?] Value to search >> fuga
[*] 'fuga' may be stored.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 2
[?] Value to search >> hoge
[*] 'hoge' is NOT stored.

[?] 1:Add value  2:Search value  3:Remove value  4:Quit >> 4
[*] Quit.

おわりに

(それなりに精度が出れば)競プロでも使えそうだな〜と思いました.
最近Pythonばっかり書いているので,そろそろ他の言語でもちょっとした何かを実装できるようにしていきたい🤔

Bug Shooting Challenge #2 に参加しました (#mixi_BSC)

はじめに

mixi社が主催するBug Shooting Challenge #2 (#mixi_BSC)に参加してきました.
本記事はその参加記を書ける範囲で書いていきます.

f:id:Szarny:20190303085536p:plain

きっかけ

Twitterで見つけました.
Twitterはいいですね🤔

Bug Shooting Challenge

Bug Shooting Challengeの詳しい概要は学生対象 不具合調査体験ワークショップのご紹介をどうぞ.

構築されたWebアプリケーションに(意図的に)仕込まれたバグがあり,実際にユーザから届いた不具合報告をもとに原因を追求し,バグフィックスを行なっていくという形式です.
mixi社では,「運用や開発のエンジニア」と「カスタマーサポート」の間に「CRE(Customer Reliability Engineering)」というチームがあり,そこがカスタマーサポートからエスカレーションされてきた技術的な問題を解決しているとのことでした.つまり,今回はCREチームにおける,不具合調査から修正までの流れを実践するといった内容です.

技術と流れ

対象のシステムはRuby on Rails (+MySQL)で構築されており,バックエンドのロギングシステムにはHadoopやHiveが用いられていました.
問題を解く流れは,だいたい以下のような感じでした.

  1. ユーザからの不具合報告を確認する
  2. Hiveを用いてアプリケーションのログを調査する
  3. 問題が発生していると思わしきRoRの処理フローをチェックする
  4. 怪しい部分を修正してDockerでデプロイする
  5. 正しく動作していればPull Requestを作成する

単純に不具合を見つければよいというのではなく,調査 > 修正 > テスト > PR作成,という現実に即した流れだったのが特徴的でした.
不具合が修正されていても,「どこをどう修正したことがどの問題の解決につながっているのか」ということをPRにおいて明確にしないといけないことを学びました.(PRには What(何が起こったのか) / Why(なぜ起こったのか) / How(どう直すのか) を明示する!!)

問題と感想

問題となっていたのは,Webアプリケーションを構築する際に作り込みがちな実装上・仕様上のバグでした.
ただし,問題公開時点ではどの処理が原因であるか明示されないため,そこから調査を始めるというのがなかなか大変でした.(現場の方はいろんなシステムを横断的に見る必要があるので,言語やフレームワークがアプリケーション毎に変わって大変とのこと.お疲れ様です...🙇‍♂️)

バグがある処理を特定しても,それをどう修正していくのかという観点に立った経験があまりなかったので,「運用を止めずに,かつ,既存の機能を殺さずに修正を行うにはどうすればよいのか」ということを考えるプロセスが非常に難しかったです.

セキュリティ勢としては,権限チェックの不備によるバグとかがあったのが面白かったなあと思います.
詳しい内容は公開NGっぽいので,ぜひ参加してみてください!(とても楽しいです)

ご飯とか懇親会とか

ご飯が美味しい f:id:Szarny:20190303085515p:plain f:id:Szarny:20190303085436p:plain

大変ごちそうになりました.
懇親会では学生エンジニアの方やmixiのエンジニアの方とお話しさせていただきました.
学生はCTF勢とか競プロ勢が多かった印象です.(他人の研究テーマを聞くのが面白かった)
今回の問題で出されたようなバグは実際の現場でも起こっているらしく(実際のインシデントを再現した問題もあった),日頃からちゃんと気をつけないとなあという気持ちになりました.

おわりに

全体を通して,とても楽しく勉強になるイベントでした.
mixi社の方々,CREチームの方々に感謝いたします🙇‍♂️🙇‍♂️🙇‍♂️

次は別のChallengeにも参加してみたいなあと思っています!

InterKosenCTF writeup

はじめに

InterKosenCTF(https://www.kosenctf.com/)のwriteupです.(ほんの一部だけですが...)
私が所属していたチームNekochanNano!は1250ptsで12位でした.

[Web 100pts] Gimme Chocolate

以下のbrainf*ck likeなPHPの関数にうまく値を与えてGive Me a Chocolate!!という文字列を作る問題.

function bf($code) {
    $ARRSIZE = 10000;
    $STEPSIZE = 100000;
    $p = 0;
    $jp = 0;
    $jbuf = [];
    $mp = 0;
    $mem = array_fill(0, $ARRSIZE, 0);
    $obuf = "";
    
    for ($s = 0; $s < $STEPSIZE && $p < strlen($code); $s++) {
        $c = $code[$p];
        if ($c === '>') {
            $mp = ($mp + 1 + $ARRSIZE) % $ARRSIZE;
        } else if ($c === '<') {
            $mp = ($mp - 1 + $ARRSIZE) % $ARRSIZE;
        } else if ($c === '+') {
            $mem[$mp] = $mem[$mp] + 1;
        } else if ($c === '-') {
            $mem[$mp] = $mem[$mp] - 1;
        } else if ($c === '[') {
            $jbuf[$jp] = $p;
            $jp++;
        } else if ($c === ']') {
            if ($mem[$mp] == 0) {
                $jp--;
            } else {
                $p = $jbuf[$jp-1];
            }
        } else if ($c === '.') {
            $obuf .= chr($mem[$mp]);
        }
        $p++;
    }

    for($i=0; $i<10; $i++){
        echo  $i . "=" . $mem[$i] . ",";
    }
    echo "\n";
    return $obuf;
}

Give Me a Chocolate!!自体はコードをちょっと読めばすぐ構成することができますが,ある条件があります.
ファイルに書き込む際に,100文字制限がついています.

$fp  = fopen($prefix.DIRECTORY_SEPARATOR.$_POST['name'], 'w');
if ($fp === FALSE || fwrite($fp, $_POST['code'], 100) === FALSE) {
  $errs []= 'Unexpected error. Please contact the admin.';
  break;
}

上記の関数を用いてGive Me a Chocolate!!を入力値100文字以内で構成するには明らかに無理があります.

しかし,ファイルを読みだして実行するところをよく見ると,$_GET['file']の値を直接指定してファイルを読みだしています.
$_GET['file']には,普通にWebアプリケーション経由だとサーバのローカルなパスが指定されますが,ここにURL(http://...)を指定することも可能です.

else if (isset($_GET['execute'])) {
  $code = file_get_contents($_GET['file']);

そこで,以下のコードをgistに登録して,$_GET['file']にそのgistのURLを指定したところFlagが出ました.

+++++++++[>++++++++>++++++++++++>++++>+++++++++++++<<<<-]>-.>---.>>+.<<----.>----.<<++++++.>.>.<----.>.<------------------------------.>>--------------.+++++++.------------.++++++++++++.---.-----------.+++++++++++++++++++.---------------.<<----------------------------------..
http://web.kosenctf.com:8100/?execute&file=https://gist.githubusercontent.com/...

f:id:Szarny:20190120215814p:plain

KOSENCTF{CIO_CHOCOLATEx2_CHOx3_IIYONE}

結構でかい口を叩いていますが,チームの人に「file_get_contents($_GET['file'])にURL直接指定できるのでは?」という助言をいただくまでずっとコードゴルフをしていました(バカ)(はい)(ごめんなさい)

[Crypto 100pts] strengthened

問題は以下の通りです.

from Crypto.PublicKey import RSA

assert(flag.startswith("KOSENCTF"))

m = int(flag.encode("hex"), 16)
key = RSA.generate(2048, e=3)

while pow(m, key.e) < key.n:
    m = m << 1

c = pow(m, key.e, key.n)
print("c={}".format(c))
print("e={}".format(key.e))
print("n={}".format(key.n))
c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
e=3
n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711

RSA暗号です.
RSA暗号を解読するときの一般的な手法はn素因数分解してp,qを割り出すことですが,nが大きすぎて明らかに無理です.

よく見ると,e3と非常に小さな値になっているのがわかります.
RSA暗号には,eの値が小さいときLow Exponent Attackという手法を用いて解読できることが知られています.
が,これは平文mne乗根以下の場合,つまりpow(m, e) < nの場合のみに限ります.
今回の問題では以下のコードによって対策がなされているため,上記攻撃は成立しません(これでInf時間溶かした)

while pow(m, key.e) < key.n:
    m = m << 1

上記のコードをよく見ると,mが2乗されていって,pow(m, e) >= nとなった瞬間にループを抜けています.
ここで,c = pow(m, key.e, key.n)より,pow(m, key.e) = c + ? * key.nです.
一般的なRSAの場合この?がとてつもなく大きな値になりますが,今回の場合そこまで大きくならないことが予想されます.

そこで,この?の値を総当たりで解読を試みるスクリプトを書いたところうまくいきました.

import gmpy2
import sys

c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
e=3
n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711

def root3(a):
    r, result = gmpy2.iroot(a, 3)
    return r

def oct2str(m):
    hm = hex(m)[2:]
    s = ""
    
    for i in range(0, len(hm), 2):
        s += chr(int(hm[i:i+2], 16))
    
    if "KOSEN" in s:
        print(s)
        sys.exit()

for x in range(1, 10000):
    print("[*] x={}".format(x))
    m_3 = c + x * n
    m = root3(m_3)
    
    while m > 1:
        oct2str(m)
        m = m >> 1
$ python solver.py 
[*] x=1
[*] x=2
[*] x=3
[*] x=4
[*] x=5
KOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}

[Forensics 50pts] attack log

pcapngファイルが渡されます.
Wiresharkで中を見てみると,大量のBasic認証を試行しているログが確認できます.

また,以下のコマンドでFlagがBasic認証における正しいパスワードだとわかります.

$ strings attack_log.pcapng | grep flag
The flag is KOSENCTF{&lt;the password for the basic auth&gt;}

本問題のログでは,認証がうまくいかなかったときに401 Unauthorizedが帰ってきています.
そのため,認証がうまく行ったときのログを見るには200 OKが帰ってきているところを調査するのが有効だと考えました.

$ strings attack_log.pcapng | grep -5 "OK"
[^G80
[^G8
(OJ@
[^G80
[^G8
(OK@
[^G8
GET / HTTP/1.1
Host: www.kosenlab.org
Connection: keep-alive
Accept-Encoding: gzip, deflate
--
--
Accept: */*
User-Agent: python-requests/2.13.0
Authorization: Basic a29zZW46YlJ1dDNGMHJjM1cwcmszRA==
[^G80
[^G80
HTTP/1.1 200 OK
Date: Thu, 27 Dec 2018 07:13:24 GMT
Server: Apache/2.4.6 (CentOS) PHP/5.4.16
Last-Modified: Thu, 27 Dec 2018 07:10:37 GMT
ETag: "a5-57dfba4b551c5"
Accept-Ranges: bytes

以上より,認証がうまく行ったときのBasic認証の値はa29zZW46YlJ1dDNGMHJjM1cwcmszRA==だとわかります.
Basic認証の値はbase64(id || pass)なので,base64デコードしてやれば良いです.

$ echo a29zZW46YlJ1dDNGMHJjM1cwcmszRA== | base64 -D
kosen:bRut3F0rc3W0rk3D
KOSENCTF{bRut3F0rc3W0rk3D}

[Forensics 200pts] conversation

Androidのダンプファイル的なものが渡されます.
とりあえずforemostを使ってどんなファイルが中にあるのか調査します.
結果は以下のようになりました.

$ ls
audit.txt   jar     pdf     zip
htm     jpg     png

jpgフォルダの中を見ると,誰かとSMSでメッセージをやり取りしているような画像が見つかります.
その中にFlagがありました.

f:id:Szarny:20190120214908j:plain

KOSENCTF{7h3_4r7_0f_4ndr01d_f0r3n51c5}

おわりに

とても楽しいCTFでした!!
チームの方がプロすぎて何もできないマンをしていたので精進したい.
Webがあまり解けなくて悔しかったので次のCTFではリベンジしたいです.

運営の方お疲れ様でした!!:bow: