HITCON CTF 2015

今回は fuzzi3 というなんか卑怯な人の多さのチームに混ぜてもらいました。用事もあったのでゆるく参加するつもりが割と頑張ったけ。けどゆるく参加しても貢献度変わらなかったんじゃね?という感じの成果でした。

チームがものすごいので4位。他人の成果に乗っかってなんかするのができるのはラクだなーというのと、ちゃんと自分の成果を後に引きつげるように考えるべきだなーとか思った。

https://ctf2015.hitcon.org/scoreboard

hard to say

なんか shell 呼べる Ruby で記号しばり 10B で cat flag しろ、という問題。4つにわかれてる問題で、1つ目とかは結構サイズ制限ゆるい。とりあえず任意コードの記号化プログラム的なものが手元にあるのでそれで1問目終了。全チーム最初の1以上の得点だったと思う。

2,3とうーんどっちかというとshell芸だなーと思いつつ m4 flag とかしてこなす感じで。4つ目は全然わからなくて、1つ目で環境見て遊んでる最中に書き込める領域見つけたのでそこに cat flag て内容のファイル書いて実行して終わり。

https://gist.github.com/shinh/4999b3d154aafc774b91

本当は $0 が /bin/sh だからそれ使えば良かったらしい。

おでかけに行く。

babyfirst

出先で docs を見ると、空白と改行と \w+ だけで shell のコード適当に動かせるよ、 wget で色んなファイル置けるよ、ただファイル名指定できない、ということをチームの人が発見していた。ファイル名指定できないと index.html になるので、 . が使えないと実行できない。うんテザリングであれこれ試すにはちょうどいいくらいかな…とあれこれ試す。

まー redirect っしょーと色々やるも、どうもファイル名が index.html になる。 ftp どうよ、と ftp://.../robots.txt にリダイレクトすると robots.txt という名前で落ちてくる。ああこれいけるなーと思ったけど anonymous write できる ftp わからんかったし ftp サーバ出先で上げるのは困難な気がしたので(よく考えると VPS 使えばできたが)、チャットで言ったら他の人が終わらせてくれた。

risky

酒飲んで帰って、適当に見てると risky というのが x86 でない謎アーキテクチャで僕好み。見る。適当に PLT とか見て命令推測…とか少しやってたけどよく docs 見ると RISC-V であることはわかってたぽいので、ツールチェインインストール…とかやってたけどよく見ると他の人が objdump の結果はってた。

適当にアセンブリを方程式にするコード書いて、でこれどうやって解くかな、と思いつつ結果を docs に貼ってたら、他の人が z3 にかけて終わらせてくれた。なるほどこういう時に使うのかーと。これは解析的にも解けたと思うけど、まああきらかに便利そうだから使いかた覚えよう。。

https://gist.github.com/shinh/c67ed9379ef8e5ef4740

unreadable

他の問題解いてる間に足されてて、 xxd したら終わった。

http://shinh.skr.jp/tmp/unreadable.png

moonglow

心を砕いた問題。フラグのファイル名を知らないプロセスから、同じUIDで動いてる、フラグを知ってるプロセスにフラグの内容を送って、あってるか間違ってるかをチェックしてもらう、って問題。

chroot の中にいるので /proc/*/cmdline とか見てコマンドラインに渡されてるフラグの名前を調べたりできないし、フラグの置かれてるディレクトリは x しか立ってないので中を見ることはできない。 ptrace は yama に殺されている。

なんかマイナーなシステムコールを使うか、チェックにかかった時間を計測するしかないかなーとあれこれする。 prlimit がなにかに使えそうだなーとコアを吐くように変更してみたりするもダメ。 Ubuntu だと apport かなんかに投げるのと、あとそもそも core て chroot されてると出ないらしい。知らなかった。

あと試したのは inotify syslog などなど。時間はかる方も、なんかの間違いで wait4 できねーかなーとやってみたり少し待ってから kill 送って死んだか死んでないかで分離できないか一応チェックしたり。まあ無理に決まっていた。

答えは perf_event_open だったらしい。なるほど perf かー。思いついても良いレベルだった気がするなあ…と悔しい。

waterleaf

なんか波ぽいノイズが乗った動画の中の steganography 。画像化とかはぷよAIの時のがあるのでさっくりできるし、まあ画像系は苦手ではない…ということで見てた。ヒントが出て、波の方向とかにデータ乗ってる、としか思えなくて脊髄反射的に波の方向を調べてどうこうするプログラム書いたり、波の方向目で見てフラグぽい文字列が出ないか…と頑張ってた。

答えは FFT しろってことだった。ヒントも波の形もあきらかにそういう感じでした。。。物理やってたんなら見覚えあるだろうに。。

kati について

https://github.com/google/kati

kati について、ドキュメント書こう…と思っていたのですがなかなか進まないので、とりあえず日本語で書いてみることにしました。何書くかがあまり明確じゃないテーマなので、何書くか考えるのと英語考えるのを両方同時にやるのが少し大変で。

動機

kati は GNU make のクローンです。いずれ完全なコンパチになると嬉しいですが、なかなか難しいだろうと個人的には諦めています。用途に対して実用的ならば良いかなと。

動機としては、 Android platform のビルドシステムが、なかなかシュールな GNU make 黒魔術で構成されていて、 make が実際になんかしはじめるまでが遅かったので、そこを高速化したいというものでした。

ビルドシステムが遅いという時、まずだいたいヌルビルドとフルビルドの2点を考えます。ヌルビルドてのは生成物が全てできている時の、 make て叩いてから Nothing to be done て出るまでの時間で、フルビルドは生成物が全くない時の時間です。現実のビルドは両者の間になりますが、大雑把に言って、ヌルビルドは開発中に .c を一ついじった時のターンアラウンド時間などに強く影響し、フルビルドは新しいリビジョンをチェックアウトした時や多くのファイルから include されてるファイルをいじった時などのビルド時間に影響します。

Android の場合、結構立派なワークステーション+SSDで、ヌルビルドが100秒ほど、フルビルドが30分てとこでした。30分はまぁ良いんです、30000ターゲット以上あるので。ヌルビルド100秒の方が終わっています。 C ファイル一個書き換えて、コンパイルが通るかがわかるのが100秒後というのは結構つらい。 kati 使うと Makefile 書き換えや Java ファイル追加が無い時のヌルビルドは5秒、ある場合で50秒てとこです。

というわけで GNU make クローン作ってみるのはどうよ、ということで始めたプロジェクトでした。最初はコマンド実行もやる予定でしたが、 ninja 出力する方が色々都合が良い部分もあり今はそうなっています。 20% 的に始めたプロジェクトでしたが、気がついたら本職になってて、 AOSP で make て叩くと勝手に kati+ninja でビルドされるようになりました。

最初は色んなものキャッシュするとかちゃんとやれば十分パフォーマンスが出るだろう、という見通しで ukai さんと Go で書き始めたのですが、主に GC のせいかすごく遅かったので一人で C++ で書き直しました。とはいえそれまでにわかった知見やテストケースが生かせたり、ほぼ Go のコードを単純作業で C++ に翻訳すれば良い部分も多かったことから、 Go バージョンも無駄ではなかった、という感じでした。

構成

大雑把に言って、 kati には以下のようなコンポーネントがあります:

  • パーサ
  • 評価するとこ
  • 依存グラフ作るとこ
  • 依存グラフを実行するとこ
  • 依存グラフから ninja ファイルを作るとこ

GNU make ではパーサと評価するとこはひっついてると思われます(GNU make のコードは OSS トップクラスの俺的可読性の低さなので、ほとんど読んでないです)。最後の実行するところと ninja ファイルを作るところはモードによって切り替えることになります。

パーサと評価器は文のパース/評価と式のパース/評価にそれぞれ2つあります。 make は行指向なので文は1行と対応し、一つの文は種類によって0個以上の式を持ちます。

普通の make ユーザは、評価器をあまり意識しないんでないかと思います。ただ実は関数とか作れてこの部分はチューリング完全です。また、 Android のヌルビルドのほとんどの時間がここに使われています。グラフ作るところとか stat してまわるのが相対的にたいしたことないのは、たぶん Android 固有の話です。要は黒魔術駆使しすぎてるので評価器の負担がすごい。

評価が終わって得られるのはルールのリストと、変数テーブルです。ルールを次々と適用させていくと依存グラフが完成します。このフェーズで変数テーブルは基本使わないです。

実行する時か ninja ファイルを生成する時にコマンドに対する式の評価が行なわれます。この時に再度変数テーブルが必要です。

以下では個々のコンポーネントを見ていきます。 CS の常識が通用しない、 GNU make の狂気が散見される予定です。

文のパーサ

既に書いた通り、文のパーサと式のパーサがあります。あと実はルールのパーサというのもありますがそれは後で。前述の通り GNU make ではおそらくパーサと評価器はひっついてますが、 kati で分けた理由は速度のためです。普通は分けなくて良いと思うのですが、 Android のビルドでは同じファイルや式を何度も参照します。どのくらいかというと3千ファイルを5万回を越える回数読みます。最も何度も読まれるファイルは5千回以上読まれます。こんなものを毎度パースするのは完全にムダです。 Android の場合、文のパース結果を記憶しておくのをやめると、パースと評価の部分が倍程度遅くなります。

文の種類は

  • ルール
  • 代入
  • コマンド
  • ディレクティブ

の4つです。ディレクティブには if 系、 include 系、 export/unexport がありますが重要でないです。あと内部的にはパースエラー文というのがあります。というのは GNU make の if 系は実行しないところのパースエラーはエラーにならないので、もしここが評価されたらエラーよろしくー、という文が必要なのでした。

残りの3つは

VAR := yay!      # これは代入
all:             # これはルール
	echo $(VAR)  # これはコマンド

となっています。 make でルールと言うと普通コマンドも含む気がしますが、まぁこう呼んでいます。

文のパーサで厄介なのは、コンテキストに依存してパース結果を変えないといけないことです。一つ目として、式を評価しないと文の種類がわからないケースがあることがあります。例えばこの2行目はなんでしょうか

$(VAR)
	X=hoge echo $${X}

この2行目は、 $(VAR) の展開結果がルールならコマンド文で、そうでなければ代入文です。もし手前に

VAR := all:

なんてのがあるとコマンドになるわけですね。コロンを変数に入れて展開してもルールとして認識される、というのが一つ驚きなのではないかと思います。式を評価してみないとルールの中身のパースに入れないということなので。では必ず式の評価をしてから文の種類判定が行なわれるかというと、そうではなく、ルールだけが式評価の後に中身チェックがなされます。変数に X=Y のような代入文や include ディレクティブなどを入れても、それは単にルールと解釈されます。例えば

ASSIGN := A=B
$(ASSIGN):
	echo $@

は A に B: を代入するのではなく、 A=B というターゲットに対するビルドルールです。

こういった理由から、 kati ではタブで始まってる行はとりあえずコマンドとして解釈しつつ元の文字列を覚えておき、もし間違ってたらパースしなおす、ということをしています。

また、2つ目の厄介な点として、普通のプログラム言語ではパースの前に \ による行連結や # によるコメントの処理が行なわれるのではないかと思いますが、 GNU make ではこれらの処理の仕方が3種類あるので、この段階でまだできないということがあります。例えば

VAR := has\
space
all:
	echo $(VAR)
	echo has\
nospace

の結果は has space と hasnospace 、です。

式のパーサ

A := B

のような代入文だと、 A と B がそれぞれ式です。式は一般的には他の式の配列で木構造をなしていて、リーフは、リテラル、変数参照、変数少しいじる参照、関数、となってます。

式のパースで狂っているのは、前述の通りこのタイミングで \ や # による行連結とコメントに対応しないといけないこと、対応が取れてない括弧の組がエラーにならない場合があること、あとは関数によってパースの仕方が少し違うものがあること、です。

まず対応が取れない括弧は、 $($(foo) などという式がある場合、 "$(foo" という名前の変数を参照する、というのが GNU make の挙動になっています。これを意図的に利用する Makefile は無いでしょうけど、 GNU make が許す以上括弧の対応が取れてない式は世の中に存在するので、これに対して適切にカラ文字列を出す必要があります。

GNU make には関数があります。だいたいの人は $(wildcard ...) や $(subst ...) あたりしか使わないやつです。でもこれは実は $(if ...) や $(call ...) などがあって、条件分岐と関数呼び出しができるので、 GNU make の評価器はチューリング完全になってます。パースでここが問題になるのは $(if ...) 、 $(and ...) 、 $(or ...) の3つだけ、空白の処理の違いかたが少し違う、ということです。

ルールのパーサ

代入でもコマンドでもディレクティブでも無いものはルール文としてあるわけですが、このルール文は評価の後、実際には4つのものになりえます。

  • ルール
  • target specific variable
  • 空白だけの場合何もしない
  • コロンが無い空白以外の文字列だとエラー

ここでいうルールというのが all: hello.exe みたいなやつです。 target specific variable というのは、ほとんどの人が知らないと思います。これを使うと特定のターゲットだけで有効な変数を定義することができて、例えば

VAR := X
target1: VAR := Y
target1:
	echo $(VAR)
target2:
	echo $(VAR)

などとあると、 target1 は Y と表示し、 target2 は X を表示します。感覚としては namespace のような動きをするものです。詳しくは後述しますが、 GNU make での変数は2種類あって、 := の右辺は即座に評価、 = の右辺の評価は展開時に遅延される、という特徴があります。つまり target specific variable のあるルール文の右辺の評価は遅延しないといけないため、「ルール文全体をとりあえず評価してからパースする」というような簡単なやり方は通用しません。このへんものすごいコーナーケースがたくさんあるので、たぶん ckati は厳密に実装してなかった記憶があります。

同様に、ルールにも実行が遅延されなければならない部分があって、ほとんどの人が知らないであろうセミコロンというのがあって、

target:
	echo hi!

という普通の Makefile

target: ; echo hi!

は等価ということになっています。これのせいで話が2つの意味でややこしくなります。1つ目はさっきの = と同じで、 ; から先の評価はコマンド実行時まで遅延させないといけない、ということ。あと = と ; が両方ある場合は基本的には左にある方が勝つ…はずです。

2つ目は ; が存在した場合、その後のパースの仕方が変わる、ということです。具体的には前述の \ と # の処理が、コマンドとして処理する時のモードになります。

あとおまけとして、おそらく普通知らないであろう、 double colon rule やら order only dependency なんてものも GNU make にはあったりします…がここでは詳しいことは書きません。

文の評価

文の種類は

  • ルール
  • 代入
  • コマンド
  • ディレクティブ

という話でした。ディレクティブは全て比較的常識的な挙動をし、コマンドは単に一個手前のルールにコマンドの式を追加していくだけのことです。ルール文は前述のルールパーサがだいたいの処理をすることになります。

意外と欝陶しいのは代入です。先に少し書いた通り GNU make の変数には2種類あります。 recursive と simple と呼ばれています。 $(info ...) という print みたいな GNU make 関数があるのですが、それを使って

A = $(info world!)
B := $(info Hello,)
$(A)
$(B)

というコードを書いたと思います。これだと world! が先に出ちゃうんじゃ…と思うかもしれませんが、これはちゃんと Hello, と出力してから world! と出力します。なぜそうなるかというと、 A は = で代入されててこっちは評価が遅延される recursive という種類の変数定義で、 B は := なので即時評価なのです。よって A の方は $(A) とした時に始めて出力が行なわれているのですが、 B の方は代入時に評価されています。

少しややこしいのは += と ?= です。これらは前回の代入文の形式を引き継ぎます。まだ定義されてない変数に += や ?= を使った場合は recursive 、つまり = の方の代入となります。

さらに target specific variable と += が組み合わさると、結構複雑なことになります。詳しくは説明しませんが、 http://shinh.skr.jp/slide/make/014.html に一例があります。

式の評価

なにぶん関数の種類が多くて実装の量は多い部分ですが、この部分は結構普通です。コマンド行が評価される場合は $@ などの特殊変数が定義されるなどもありますが、まぁとにかく常識的な動きをします。

少しヘンな部分は $(wildcard ...) くらいで、これは GNU make の最適化が入ってるためか、コマンド行にあっても評価タイミングが遅延されないという特徴があります。というか評価タイミングがヘン。これについては kati は Go の方も C++ の方も別の意味で実装が正しくないと思ってます…が実害は普通ないです。

ninja ファイルを出力する場合、コマンドに対してこの部分が少しややこしくなるのですが、それは後述。

AndroidMakefile には $(shell find ...) というパターンが大量に出てきます。これは同じところ何度も find するのですごく遅いです。 kati では高速化のために find コマンドのエミュレータを書いてあって、最初にコード全域を find しておいて、その結果を使って $(shell find ...) を高速実行する、ということをしています。 find コマンドってそれなりにややこしいので結構めんどくさかった部分です。

依存グラフを作る

さてこれまでは GNU make のカジュアルユーザーにとっては異世界の話だったと思うのですが、ここは馴染みのある話、というか make というと思い浮かべるのはこの部分かと思います。

この部分もそれなりに複雑なのですが、理不尽な挙動はしません。 GNU make のルールには3種類のものがあります。

  • explicit rule
  • implicit rule
  • suffix rule

explicit rule はターゲット名が明確なルールで、 implicit rule はターゲット名に % が含まれていて、色んなものにマッチするルールです。 suffix rule はサフィックスでマッチする歴史のある書き方。要はこの3つ

all: hoge.o
hoge.o:
	echo explicit
%.o:
	echo implicit
.c.o:
	echo suffix

優先順位は suffix が最弱で、後は % にマッチした量が少ないものが優先されます。要はより厳密な方なので、 explicit rule は優先度最大です。このマッチングを、ルールにコマンドがついていて、前提条件を満たせるものが見つかるまで行ないます。

Android には % のついてるルールが1000以上あってコマンドのついてないルールが万単位であるため、このマッチングをナイーブにやると100万回単位のループが回って、遅いです。よってここは trie 使って速くなるようにしてあります。

見つかったルールは色々とマージされたりするので色々ややこしかったりします。このへんは kati は厳密にはおかしい実装になってるはず…です。

コマンド実行する

コマンドの式は実行する直前に、特殊変数 $@ などと、 target specific variable を仕込んだ後に評価されます。ここもまぁおおむね普通です。

実装自体は普通なのですが、 target specific variable が大変筋の悪いものであることを説明しておきたいと思います。 target specific variable は、その target specific variable が仕込んであるターゲットから起爆されたターゲットにも適用されます。どういうことかというと、

VAR:=global
all: VAR:=target specific
all: hoge
hoge:
	echo $(VAR)

は "target specific" と出力します。 all に仕込んである target specific variable がターゲット hoge にも影響を及ぼしているわけです。で、何が問題かというと、これ "make hoge" としてターゲット hoge をターゲット指定すると、ターゲット all から起動されたわけじゃないので、 "global" と出力しちゃうんですね。 make って途中のターゲット指定した場合も同じものができる、ってのは当たり前の期待だと思うので、これは本当に筋が悪いと思います。

ninja ファイルを生成する

GNU make の話はここで終了です。 exec するかわりに同じ情報を ninja ファイルに書き込めば終わり…なのですが、なかなかそれが難しい。

まず GNU make は一つのルールにコマンドが複数くっついてたりしますが、これは ninja には無いので、 (cmd1) && (cmd2) && ... などと混ぜたり、色んなものをエスケープしたり、 $(SHELL) に対応したり…など、割と色々やることがあります。

本気で厄介なのは、コマンド内にある副作用のある make 関数、具体的に $(shell ...) です。これの実行は ninja 実行時にしなければならないので、適切な shell script に変換しないといけませんが、 $(if $(shell ...),X,Y) などと $(shell ...) の結果がまた GNU make 関数に渡されると詰みます。

これの正しい対処は試験的なパッチも書いてみたのですが、めんどくさすぎるので放棄していて、 Android に出てくるパターンだけ対処できれば良いや、というアドホックなコードが入っています。

ninja ファイルの再生成が必要かどうかを判断する

kati は AndroidMakefile に対して、 GNU make より3倍程度速く Makefile を評価しますが、 ninja を生成している時間も含めると2倍程度しか高速でなく、毎度実行してると Android のヌルビルドは結局50秒程度になってしまいます。

これだと別にあまり嬉しくないので、 ckati には以前生成した ninja ファイルが再生成必要かどうかを判断する機能がついています。これは結構難しい問題で、一番自明なのは Makefile が書き変わった時で、これは単にパースした全ての Makefile のタイムスタンプを記録しておけば必要な時に再生成ができます。現状、 ckati がチェックしている項目は5つあって

  • ckati 起動時のコマンドライン
  • パースした全ての Makefile のタイムスタンプ
  • 全ての評価に用いられた環境変数、全ての最初の評価時に未定義だった変数。後者は定義されてなかった環境変数が定義されることによって Makefile の挙動が変化する可能性があるからです
  • $(wildcard ...) の結果
  • $(shell ...) の結果

最後のがめんどくさいです。というのは前述の通り、 $(shell find ...) は遅いので、これを毎度チェックすると遅くなってしまうからです。幸い ckati は Android の find のほとんどに対応できる find エミュレータを持っているので、 find エミュレータで評価した場合、チェックしたディレクトリのタイムスタンプを全て覚えておいて、それらが1つでも変化した時にだけ find を走らせる、などということをしています。

あとは $(shell date) みたいな毎回変わるのが当然でかつ本質的に重要でないもの、 $(shell echo foo > file) などというファイル書き込みに使われてるもの、あたりは再実行する必要がないのでしてません。

そんなこんなでこのステップは1秒ほどで終わります。 ninja の読み込みに4秒ほどかかるので、トータルで5秒のヌルビルドになってます。

goma サポート

Google 内では goma という、主に Chrome で使ってるビルドインフラとうまいこと組み合わせれるようになってて、フルビルドも2倍くらい速くなってる…はずです。まぁ外からは見えてなくて意味ないので詳しく説明しませんが、これ ninja だから組み合わせやすい感じになっていて、 GNU make だと実現が困難だったりします。

goma についてはGoogle Developer Day 2011 Japan: 「Chromium 開発を支えるクラウドの技術Googleクラウドコンパイラ」 - Google Developer Japan Blogをどうぞ。 goma の言い出しっぺでもあったので、このスライド出た時は私も goma チームにいたような気がします、たしか。

TODO

デカい TODO としては $(MAKE) で起動される sub-make と呼ばれてるもの、があります。これは ninja 経由で正しくやるのは結構大変…で考え中。

まとめ

始める前から GNU make が複雑なものだってのは知ってたつもりだったのですが、クローンを書いてみると想像以上に大変でした。おおむね楽しく作業してましたが、たまにつらくもありました。

あなたの知らない超絶技巧プログラミングの世界

奇書を頂きました。

f:id:shinichiro_h:20150917020433j:plain

一応レビュアーとして参加したことになっています…が、掲示板かなにかと勘違いした人が雑談をして邪魔をしているな、という感じでした。浜地慎一郎という文字列が10回くらい出てくる残念な本です。

もう少しマジメに説明すると、私がクソコードとか読んでいるような、トリッキーなコードの作品集兼使われているテクニックの解説などがなされています。読んでいてこの本面白いなーと思ったのは、関連する他の人が書いたコードも紹介されていますが、基本的に遠藤さんの作品が主人公ということでした。えっこの人本一冊書けるくらい Quine 書いてるんだ…という。

それと、クソコードコンテスト for Ruby であるところの、 TRICK 2015 が開催されますので、みなさん頑張ってクソコードを書いて、審査員をうならせて下さい。

https://github.com/tric/trick2015/blob/master/README.ja.md

makelisp.mk

https://github.com/shinh/makelisp

Lisp インタプリタを書きました。 GNU make で。

https://github.com/shinh/makelisp/blob/master/makelisp.mk

もちろん $(shell) や $(guile) は使わない縛りです。

だいたい sedlispbeflisp と似たようなことができます。

最近作ってる GNU make clone であるところの kati でもちゃんと動きます。というか fizzbuzz.l とかだと 50 倍以上速い。

実装はまあ、やるだけ…と言いたいところですが、加減乗除が無いとか、文字列演算も色々不便とかあったりはします。あと地味に引数以外にローカル変数が無いのもだるいですね。当初は lisp to make translator を実装する感じがラクかな…と思ってたんですが、ローカル変数無いとかそういう理由で、別にラクじゃないどころかむしろ大変な気がしたのでやめました。

追記: もっとガチな Lisp 実装があるとのこと https://github.com/kanaka/mal/ 四則演算とかがちゃんと速いのがマジメ感あってやばい。おかげで一個 kati のバグ見つけた。。

MMA CTF 2015

http://uecmma.github.io/mmactf/ja/

なんかとても面白かった。21位。あまり気力の無い季節なので、 Pwn を避けて慣れないジャンルを解く感じで。ただスプラトゥーンを始めてしまったため、最後の20時間は問題読むくらいしかしてなくて28時間コンテストでした。

マジメに参加してない上に簡単な問題しか解いてないですけど、問題セットは僕にはすごく楽しかったです。色んなジャンルで、ちょっとこじゃれた感じというか。運営もほとんどヘンなトラブル無かったように思いますし。

成果物: https://github.com/shinh/mma-ctf-2015

解いた問題

Pattern Lock

https://github.com/shinh/mma-ctf-2015/blob/master/pat.cc

https://github.com/shinh/mma-ctf-2015/blob/master/pat3.cc

Android のパターンでロックを解除するやつ、何通りあるか、て問題。2問目は4x4で最長のパターンの長さを求めよ、てやつ。2問目はメモ化必要だった。割と ICPC スタイル。

Login as admin!

SQL injection

Splitted

https://github.com/shinh/mma-ctf-2015/blob/master/splitted.rb

pcap 内の Partial Content で帰った HTTP リクエストを適当につなげるだけ。

How to use?

https://github.com/shinh/mma-ctf-2015/blob/master/howtouse.rb

DLL らしいが win バイナリ作るとかめんどくさいんで、 objdump 見て答えぽいところのデータをつないでるだけ。

RPS

https://github.com/shinh/mma-ctf-2015/blob/master/rps.rb

じゃんけんに50回勝てという問題。名前を最初に入れるのでバッファオーバーフローさせてエンディングにいきなり飛ばすゲー。

This program cannot be run in DOS mode

https://github.com/shinh/mma-ctf-2015/blob/master/cannotberun.rb

MZ ヘッダから PE ヘッダが参照されてないのでオフセットを書くだけ。笑っちゃうくらい短い解答やな。

Signer and Verifier

https://github.com/shinh/mma-ctf-2015/blob/master/sign.rb

本来 sign させたいメッセージを少し加工したものに sign してもらうと、そこから元のメッセージを sign できるという話。

Encrypted

見てない

Impossible?

見てない

Simple Hash

解けなかった

文字列に対して、

hash = 0;
for (ch in str) {
  hash *= 577;
  hash += ch;
  hash %= <50bitくらいのでかい数字>

で計算されるハッシュで、狙った数字を出せってもの。

時間内に解けなかったのだけど、 50bit なので最後の方の文字列で調整できる部分以外を bruteforce すればたぶん 30bit もやれば良い気がするので解ける気がする。

これ一般的に解くことできるのかなぁ…というのがわからない。

あとハッシュアルゴリズムの確認はアセンブリ読むのだるかったので、与えられたプログラムに色々入力喰わせて調べてみた。

https://github.com/shinh/mma-ctf-2015/blob/master/sh.c

Uploader

script タグがあれば <? とか php とか使わずに PHP が実行させられる。

パス知ってれば他のチームが upload したファイルが見えるので、適当に flag とかそういうファイル名のファイルを見てみたら、 MMA{uploader_is_not_safe} みたいなそれっぽいニセフラグをアップロードしてたチームがあったぽくて笑った。

Login As Admin!(2)

見当もつかなかった。

Mortal Magi Agents

遊んでみたけど閃きの神様は降ってこなかった。

Motto Mijikai Address

ちょっと遊んでみたけどわからなかった。てかほとんど誰も解いてないじゃないか。

regrettable ecc

見てない

LCGsign

見てない

stream...

ストリーミング動画再生してた pcap 的なものから動画取り出せと。まあやりゃできるんだろうけど、と思いつつぱっと見て使えそうなヘッダとかがわからなかったのでやらなかった。

spell

ちょっと遊んでみてクラッシュしなかったので、まあ良いかと思った。

d3flate

解けなかった。 zlib で圧縮した結果がうまいこと shell 奪える攻撃になるようにしろってこと?

Nagoya Castle

https://github.com/shinh/mma-ctf-2015/blob/master/nagoya.cc

点数的にとりあえず下位1bitでーと思ったらあってた。

Miyako

点数的にあきらめた

QR code recovery challenge

一応 QR code 画像をテキストに落とすくらいはやって、 strong-qr-decoder でデコードできなかったぽいので放置した。 SECCON で QR code 嫌いになったんだ。。

https://github.com/shinh/mma-ctf-2015/blob/master/qr2txt.cc

Money Game

https://github.com/shinh/mma-ctf-2015/blob/master/money.rb

1問目は株の売買で1万ドルを10万ドルに増やせというマネーゲーム。うーんこれ最適解計算できるのかな?とか思いつつ、とりあえず買ってすぐ売るというのを貪欲にやるのを書いたら、イマイチ足りない。任意の期間で買って休んで売る、てのを一番トクするやつから順に貪欲に取っていったら、10回に1回くらいは成功するようになったので良いとした。

2問目は1問目解くと名前聞かれて、 printf format を喰わせるとあら大変という定番のやつ。

GOT 書き換えて、ただ実行と書き込み可能な領域は無いから stack を大幅に pop してくれるところに飛んでから、 ROP 。なんだか結構手こずった。

第一段階の成功率があまり高くないのと bruteforce 好みでないから、 stack のアドレス決め打ちとかはせず、メインバイナリの中にあるものだけでやろうとしたからかなと思った。あと1回で行けそうだから、1回でやったけど、結構長くなってしまって色々調整手こずったのもあるので、2回に分けた方が良かった気がする。

手口的には fclose の飛び先を stack を 11 回分 pop してくれる地点にして、 fopen を呼ぶ call 命令の地点に飛び、引数は flag2 になるように stack が調整されてて、 2 回目の fclose でまた 11 回 pop してその後の飛び先を fflush にして完了。

この問題、なぜか最初に解けた。 Pwn 強い人が前哨戦解けなかったか解かなかったのでは。。

Alicegame

やってない

Bow tickets

やってない

Digital Circuit

https://github.com/shinh/mma-ctf-2015/blob/master/dc.rb

普段やらないジャンルーということでハードウェア。 Verilog のコードから変換されたアセンブリみたいなもの(素人すぎてこれをなんというのかすら知らない)に適切な入力を与えて Correct!!! と出させましょう、みたいなやつ。

素人すぎてよくわからないので、適当に途中結果を $display 足して見てみたりして、その後 gtkwave というのがあるなーと色々値を見てみたりする。

でーめんどくさくなって、どうもよくわからんが c1 てのと c2 てのと c4 てのが全部 0 になったらよくて、 256bit の入力のうち、 c1 は 64bit を使い c2 も 64bit 、 c4 は 128bit 使うぽいじゃん、という程度のことを理解して方針転換。

c4 はかけ算と xor が目に入ったので、 invmod した結果を喰わせてみたらいきなり 0 になる。やる気向上。

c2 は色々入力を与えてみると、どうも本質的に定数と xor してるだけぽかったのだったか、そういう理由で解けた。

c1 は c2 よりややこしくて、入力の 1bit いじると複数 bit が変わるぽかった。まあその変化する bit は固定かな…と適当にやってみると、全然うまくいかない。

とはいえどうも 1bit の入力が変化させる bit 数はたいした数無いぽかったので、 1bit ずつ立てるべきか立てないべきかを手で調整していってしたら解けた。

MQAAAA

謎の Base64 。よくわからんサイトとかひっかかるが、エスパーチックだったのであきらめる。

pieceofeight reloaded

解けなかった。 16パズルの9マスバージョン。解けないようになってると思うので、ゲームを続行するための復活の呪文みたいなやつをリバースエンジニアリングせよって問題かと思ったんだけど、なんでジャンルが Reverse とか Crypto じゃなくて Misc なんだろ…と思いつつ放棄。

i

https://github.com/shinh/mma-ctf-2015/blob/master/gen_q_i.rb

クソ言語で Quine を書けという問題。私にはサービス問題です。2番目に解いたチームだったけど、それは問題が現れた時に寝てたからってだけじゃないかなたぶん

Perfect Matching

https://github.com/shinh/mma-ctf-2015/blob/master/pm.rb

これは今回一番好きな問題だった気がする。

グラフを与えるから完全マッチングをかえしなさい、という問題。グラフとか苦手なので完全マッチングて何だったかなぁ…とか調べたりする。

これ適当に作ったグラフだと完全マッチングができることが保証できないから、なにか問題のグラフには制約がかかってるんだろうな、とグラフを生成するプログラムを読む…普通。というかこの方法だとガチャの原理によりエッジの無いノードすらできるんじゃね?ていうような生成方法。実際できてる。これ普通には無理だ。

…というあたりで、おっとこれは TopCoder じゃなくて CTF だった、ということで解答をチェックする部分の Python コードを読む。うーん正しいように見えるなーと思ってたけど、よく考えるとわかった。

グラフは配列の配列を使ってあらわしていて、最初の配列は頂点IDがインデックスになっていて、2つ目の配列はその頂点と接続されてる頂点IDの列。入力は int(raw_input()) みたいな感じで取ってるから数でないといけないけど、負数がダメとは言ってなくて、配列の負のインデックスを使えば、1つの頂点が2回使えるじゃん! というわけで後は貪欲に取ってけば終わった。

Alphabet Programming

https://github.com/shinh/mma-ctf-2015/blob/master/alpha.rb

アルファベットだけで、 flag というファイルを開く Ruby プログラムを25行以内で書け、という問題。まぁサービス問題…なんだけど最初不注意で大文字が禁止されてると気付いてなかったので、少しムダな時間を使ったりも。

inspect.each を呼んで flag て文字列に破壊的変更して、 each を read に変更しておいてから open self をレシーバに each 、て感じか。

機械は人狼を見つけられるかな、の各国対応

ずいぶん昔に作った対人狼ベイジアンフィルタ、少し前に各国対応してたんですが、 @mr_konnさんのtweetで思い出したのでここに書いておきます。

使いかたはサンプルURLを参照のこと

http://shinh.skr.jp/expwolf/

人狼AIなんてなー10年近く前に俺が通った道だ…とかいえるレベルのものではなく、まあオモチャです

ICFPC 2015

開始1時間くらい前に酒飲まないかと誘われる。まー ICFPC 一応やるんで、とか言うと一緒にやることになった。ので初のチームでの参加。チーム名は N6B 。

FFRK やってたら始まる。なにこれ落ちゲーとかやる気起きないっていうかこれやるなら puyoai の方が面白いんじゃね…と移動する部分だけ書いて寝落ち。僕の中の今やりたいことランキングは、スプラトゥーン>>FFRK>仕事>>puyoai>ICFPC と致命的にモチベーションが湧かない状態。

3時頃起きた。相方にシミュレータ完成させたらいいんじゃねみたいなことを言う。僕は C++ でソルバ書き始める。また寝て起きる。ソルバがそれっぽくなる、が、リモート環境と結果が喰い違ってるらしく点数取れない。

いくつかバグなおすと、回転無しでやると得点取れるようになる。回転むずいなあ…とどはまりする。そのうちシミュレータの回転が完成したらしい。 C++ の方もなんかできた気がする。なんか色々やってると1位とかに一時的になったりする。まあ他のチームが潜伏してただけだが。ただその頃には lightning division は終了済み。ひどい。

その後は酒飲みながらだらだらやる。とりあえず、置きたいところを決めてからフレーズを探すように分離する。そうこうしてるうちに r'lyeh がフレーズだと相方が発見したので、そういえば…とマップの絵を見るとそれがあるので、他も試したらいいんじゃね、て言うと yuggoth と ia! ia! を見つけてくれる。

r'lyeh はおいしいのでそれまで使ってた bap (対抗のバグ修正の後は ei!) のかわりになるべく多用するようにする。このへんでまた1位になってたと思う。

テトリス部分を書かなければいけないが、どう考えても puyoai の方がまだ楽しい。やる気起きない。現実逃避にタイムアウト対策やマルチコア活用を入れる。やる気おきないーと思いつつ、今まで1手探索だったのを2手探索にする…と少しは良くなるが遅すぎてうざい。もういいやと放棄してスプラトゥーン。

終了。1日ちょいくらいでできそうなことしかやってない。ビールは8*350mlくらいでした。

コード: https://github.com/shinh/icfpc2015/

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h