TLE 2015
http://felicity.iiit.ac.in/contest/tle/
成果物: https://gist.github.com/shinh/64fbd3d43147f6a7bbb4
毎年思ってることだけど、ここ数年は特に脳死しているなーという時に行なわれてる…ので腑甲斐ないのはしょうがないんだよ。
今回は結構神回だったんじゃないかなー実は。たぶん処理速度の問題で SNUSP 問題が消え失せたんじゃないかと思うんだけど、あれ別に面白くなかった気がするから消えて良かったんでないかと思うます。あとたぶんだけどあのへんの問題が決定的な要因になったんでないかな、残っていれば。偶然から生まれた神回感が強い。
あとちなみに初回の延期時から問題は変わってない…気がするので、やろうと思えば2週間以上使えたんじゃないかな実は…僕は延期した日にやったことは SNUSP の仕様読んでたくらいで、他の問題はだいたい忘れて脳死してたので、当日まで準備とかしてないよ…ホントだよ
Distinct Substrings
ゴミみたいな答えができたらゴミを後ろにつけると高得点というすごい問題。主催者が深く考えてない問題が出るのは毎度恒例ではある。トップを取るとかはどうでもいいスコアシステムだったので瞬時に捨てた。
Find the GCD
GCD(P,Q) を求めよただし P,Q には n,m,R を使って色んなことをして作られる。みたいな問題。 P,Q は巨大でかつ問題の制限として四則演算オペレータ使っちゃいけないということなんで、賢いやりかたがあるんだろうなーと思いつつ、はて…としばらく死んでいた。
まさに脳死という感じで。脳死しててもしゃーないんで、とりあえず正の点数取るか、そのうちなんか降ってくるだろ、となるのが私の唯一偉いところだと思ってるので、とりあえず解いた。つまり多倍長整数で mod が計算できる程度のコードを +-*/% 無しで書きました。感想はしんどかった。
手元で通るぽいコードを投げてみると Runtime Error 。これは TLE だろうかなあ…と思いつつデカいケースを喰わせてみると 0.15 秒くらいかかる。 1 秒が TLE の問題でこれだけ時間かかってると、まあだめだろうな…と思いつつ、 gprof とかで最適化するのにムダな時間を使う。本当にムダだ。
本当にムダなので賢いやり方を探そう、まー R てのが与えられてるからこれとなんかすればいいんでしょ？てことで適当に色んなことをやってると、 GCD(P,Q) が GCD(P,2^R) と一致するじゃありませんか…てことで解いた。
翌日 kinaba さんにアレでなんでいいのって聞いたらそんなの当たり前じゃないですか的なこと言われて、いや実際当たり前だった。はい。
Life, the Universe and Everything
数字がいくつか与えられるので、 echo しなさい、で、 42 で出力を止めなさい。ただし -nostdlib ついてるよ、とのこと。
えっとそれは得意分野やんけ…と瞬殺してほったらかしてたけど、普通にゴルフ足りてなかった。
ASCII Weaving
もうこの手の飽き飽きなんだよ…というような、画像圧縮問題。いつも通りとりあえず RLE してそれぽい解ができる。
いつも通りだとこれに huffman かけるんだけど、なんか huffman てやる前からどのくらいのサイズになるか見積れるわけで、はてこれはそういう感じでは mame さんに絶対追いつけないぞ、なんかすごいことが行なわれてる…
ということでやる気が失せて放置。
Halting
C プログラムの停止性を判断せよとの問題。
全部停止するって言えば 4 点入るので、あとは固定解答与えりゃいいやろ…とやってみるとうまくいかないので眺めてみると。出てくる順番が変わってるぽい。
出てくる順番変わってるだけな気がしたけど、まあ限定された C インタプリタとか割とすぐ書けるよね…と思って書きはじめたら全然間に合わなかった。いやまあインタプリタ書けても停止性は判定できないわけだけど、ある程度できたらヒューリスティクス適当に入れりゃ適当に得点高いだろ、って思ってたんだけど…
Reverse Quine
いつも通りの Quine 。 g++ の時は #include のかわりに #import 使うてのは基本中の基本だったはずなのに、脳死しててできなかった。ひどい。
工夫したところは ext/rope を #include すれば stdio.h と string が自動的に手に入る、てことくらいでしょうかね…
まとめ
問題はすごく良かったと思います。が、全体的に脳死してた。そもそも開始時間から大幅に遅れて起きてる時点でアレですね…なんか年々体力とやる気が失われている気がする。それくらいしか取り柄がないというのに…
あとまあ最終版にスコアボード全く見ずに Halting やってたのもひどいなあと思う。自分が1位から落ちてることにすら気付いてたんだっけ…という感じ。もうちょい戦略的にやるべき
GLSL Quine
前から書いてみたいなーと思っていた、 GLSL による Quine です。
http://glslsandbox.com/e#23148.0
マウスカーソルを画面半分より下に送ると拡大して読みやすくなっていきます。 Quine になってるかの確認は困難ですが、ぱっと見た感じあってるような気がします…たぶん。
GPU によっては動かないみたい。 Macbookair だとデータを減らすと動くんで、なんか命令数の上限とか使ってるデータ量の上限とかにかかってるんですかね。 Macbookair で動く程度にデータを減らすのは大変そうと判断。
Tokyo Demo Fest になんか出したいなーと常に思ってるけど今年も何もしなかったので、これでお茶を濁そう…と思ってたらこれも間に合わなかった。
やりゃ動くに決まってるんだけど、 GLSL でまともな速度で動く手順を模索するのが手間でした。なんか頻繁にブラウザが刺さってみたり。
こちらの 4x4 フォントを使わせていただいています。
Exploit and defenses
会社でバイナリの脆弱性を攻撃する方法と、それに対して防御する方法の一般的な簡単な話を適当にしたので、スライドを置いておきます。
http://shinh.skr.jp/slide/exploit/000.html
なにか一般論を書いてたら終わった感。まぁそのぶん基本的なことを網羅できるかもしれません。実際どうやってんの？てのを案外知らなかったりするドメインですし。
CRC32 Quine
Quine Advent Calendar というのがあるのかーと思ったが、特にネタがなかったので一発ネタ。
http://www.adventar.org/calendars/645
$ curl http://shinh.skr.jp/dat_dir/crc32_quine1.txt > x
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 9 100 9 0 0 344 0 --:--:-- --:--:-- --:--:-- 346
$ crc32 x > y
$ diff x y2種類あります。
SECCON 2014 予戦
ソロ。30位。今回はちゃんと点数集める方向でやってみよう…と途中まで思ってやってる感じだったので、ちょっとそれにしては、なイマイチ感。
なんかエスパー力検定みたいなオーラがそこらじゅうから流れてたなあ感。
Easy Cipher / Welcome to SECCON / Get the key.txt
なんか簡単だった。
SECCON Wars
いきなりヘンな問題をやる。動画の中に QR コードが大部分隠されて流れている。人力とコードをほどほどに組み合わせてこんな画像を作って、あとは手でテキストファイルして、コードで綺麗な画像にして、 Android で読んだ。
Shuffle / Choose the number / Reverse it
覚えてないけど簡単。
Holy shellcode
UTF-16LE で表現したヘブライ語で shellcode 作れと。大変時間かかったけど、面白かった。ヘブライ語はなんかこの文字の後にはこの文字が来れないとかあるみたいで、そのへんのヒントが
http://hebrew.pwn.seccon.jp/nikud/hebrew-utf16le.html
にあった。詳細は覚えてないし、そのへんの仕様をきちんと把握していたかは謎。
8年前くらいに作った
http://shinh.skr.jp/binary/x86_ops.txt
を適当に参照しながらやる。ちょっと悲しくなるくらいまともに使える命令がない。 xchg %eax, %XXX が全て使えるのでどう見ても役に立つんだけど、これをするとヘブライ語的な理由で後に add $XXXXXXXX, %eax がついてくるので、 EAX がぶっこわれる。まあでも EAX を好きなレジスタに送ることは…できる。一度だけ。
では EAX に好きな値を作れないとキツいぞ…ということで色々やってると、 0 で初期化できる命令列を作れた。なんと 22 byte 5 命令で、やっと AL 以外をクリアできる。
and bl, bh mov eax, 0xd4fb2f05 add eax, 0xfb3005d0 sub eax, 0xd5fb39fb add eax, 0x05d005d0
AL はまあ操作するオペレーションが十分にあるので、 0-255 は作れるぽかった。メモリ書き込みは stos しか見つからなかったが、 EDI から EBX を引くことはできるので、 EDI をポインタにして書いてくことはできそうだー。
というわけで shell code 作成。なのにそこからが動かないcodered動かない… /bin/sh は動いてるのに、 cat したら fork できんと言って切られる。たぶんリソース制限かなんかが厳しいのかなぁと。 python とか perl 動かしてみたり、色々試して、 open とかする shellcode 書くのは面倒だなぁと思いつつ、 /bin/cat keyword.txt を試すと動いた。
うーんなんのための制約だったのかな。これを含めて exploit は全て相手の環境を推し量る時間がふんだんに必要だったのが残念。あとこの問題はヘブライ語の仕様とか、表が色わけしてあってヒントになってくれてるんだけど、しかし明確に教えてくれない理由はなんなんだろうか…とか。
とはいえこの問題は他と比べて、出題者技術的にがんばったなー感がして、大変良かった。
jspuzzle / REA-JUU WATCH
jspuzzle はこんなの楽勝…と思ってたがなぜかはまっていた。 Holy shellcode 終わって、寝る前にメシ喰ってる間に、アホな見落しに気付いて、頭の中で解ける。
REA-JUU はこういうのやる気おきないなあとポチポチやってたら解けた。
全体的に眠くてしょうがない日だった。
Advanced RISC Machine
ARM 。うーんこのバイナリなんだろうなあ…と思いつつ、環境がわからんので、 Linux でロードするプログラムを作って qemu で動かす。 SVC の付近のレジスタ操作から、 SVC の規約が微妙に Linux と違うなーと思ってたので、そのへんはローダで命令書き換えて対処。
exploit はまあつまんないくらいすぐ見つかるので、 shellcode を書く。できたなーと思って動かすも向こうでは動かない。うーん qemu+オレオレローダとはページの設定とか色々違っても不思議はないなあ…とか思いつつ、元々コードがあるところじゃないところにコードを置いてみたりすると、なんか少し動いてる。
うーんまあ instruction cache フラッシュしてないしなあ…とか思いつつも、あれやこれや。なんか open と write ははっきり動いてて、 open が -1 でない値 (そしてその値は 3 ではない) を返してるのははっきりしてるのに、 read が全然動かない。しょうがないから…と、元々あるコードの getchar を使って読んでやると flag が読めた。なんじゃらほい。。
途中で、 SVC の引数いじったりして syscall の種類を調べてる時のエラーメッセージから、 GDB 付属の simulator だと気付く。 instruction cache とかは実装してないとかコメントで書いてあるけど、どうなってたんだろうな… FD が 3 以外返してたから、なんか改造はされてたんだろうけど。
Decrypt it (Easy)
mtime 見ると srand に渡す引数がわかるという話。
と思ったら2面があった。なにやら数学的に意味がありそうな話だ！でもどうせ平文の最初は SECCON{ だろう、うん3つある暗号文の最初は SECCO だ。あとは N{ と } を固定して全探索…数学はどこへ。
Japanese super micro-controller
SH 。ということは、どうせこれもシミュレータだろう、あたりー。今回はラクちんだなーしかもまたつまんないくらい exploit 自明だなーと shellcode 作る、手元で動く、向こうで動かない。
またかー。
なんか SH の方は、どうもコード空間にコピーしたコードが一切動いてないような感じ。謎だなぁ困ったなぁと思うが、困っててもしょうがないので、自分で一切コード書かず、 ROP だけで処理する感じで対処。なんか ROP に便利な感じのものがいろいろあったので、まぁそういう意図だったのかな…しかしわざわざシミュレータのコードに手を入れるとか、そういうとこだけ工夫するような運営かな…不明。
あと ARM 同様 FD が乱数になってた。かえり値をちゃんと持ちまわるのはちょっと面倒だったので、単に適当な数字をたくさん試すコードを何度かサブミットしてるうちに通った。
まぁ GDB のシミュレータだとわかれば楽勝ですよ。
Let's disassemble
エスパー。エスパーだなぁ、 x86 じゃないなぁ、 CISC だけどさすがに英語圏の人が参加してるから z80 とかそういうのじゃないよねえ。と思いつつ、色んな CISC を試し、 Java bytecode とかも検討したあと、 z80 だと判明する。がー。
だいたい objdump が前提だよなあこれ。あと、 00 が来ると何かえせばいいのかわからなかったんだけど、まぁ 100 回のうちに来ない時にクリアできた。意味不明だ…
ROP: Impossible
頑張ってみたけど解けなかった問題も書いてみよう。これが筆頭、というかこれは解きたかったんだけど、時間勘違いしてて、どう考えても解けない時間しか残らなかったので、 Let's disassemble 見てたのだった。
jmp/call で chain を作るーて趣旨だと思うんだけど、そうだとすると一度やってみたかったんだよな。結構時間をかけてバイナリ内を調べて、使えそうな材料は色々あるんだけど、 call で飛んだ先で、余計なものがスタックにつまれすぎてて、大変むずかしそうに見えた。
static link について
案外、 static link ってわかってないもんです。というかリンカってわかってないもんです。そして案外はまるものです。以下のクイズに答えられるでしょうか。
クイズ1
$ nm main.o # int main() {}
0000000000000000 T main
$ nm foo.a # void foo() { bar(); } void baz() {}
foo.o:
U bar
0000000000000010 T baz
0000000000000000 T foo
$ nm bar.a # void bar() {} void baz() {}
bar.o:
0000000000000000 T bar
0000000000000006 T baz
$ gcc main.o foo.a bar.a最後のコマンドで、何が起きますか？
- 普通にリンクできる
- undefined reference to `foo'
- undefined reference to `bar'
- multiple definition of `baz'
クイズ2
$ nm main.o # int main() { foo(); }
U foo
0000000000000000 T main
$ gcc main.o foo.a bar.aクイズ1との違いは main.o だけです。最後のコマンドで、何が起きますか？
- 普通にリンクできる
- undefined reference to `foo'
- undefined reference to `bar'
- multiple definition of `baz'
クイズ3
$ nm main.o # int main() { bar(); }
U bar
0000000000000000 T main
$ gcc main.o foo.a bar.aクイズ1,2との違いは main.o だけです。最後のコマンドで、何が起きますか？
- 普通にリンクできる
- undefined reference to `foo'
- undefined reference to `bar'
- multiple definition of `baz'
クイズ4
$ nm main.o # int main() { bar(); }
U bar
0000000000000000 T main
$ nm foo.a # void foo() { bar(); }
foo.o:
U bar
0000000000000000 T foo
$ nm bar.a # void bar() { foo(); }
bar.o:
0000000000000000 T bar
U foo
$ gcc main.o foo.a bar.a最後のコマンドで、何が起きますか？
- 普通にリンクできる
- undefined reference to `foo'
- undefined reference to `bar'
- multiple definition of `baz'
クイズ5
$ nm main.o # int main() { foo(); }
U foo
0000000000000000 T main
$ gcc main.o foo.a bar.aクイズ4との違いは main.o だけです。最後のコマンドで、何が起きますか？
- 普通にリンクできる
- undefined reference to `foo'
- undefined reference to `bar'
- multiple definition of `baz'
クイズ6-10 (飽きたので雑な出題)
クイズ1-5のそれぞれのケースについて、
$ gcc main.o foo.o bar.o
として foo.a と bar.a のかわりに foo.o と bar.o をリンクした場合、何が起きますか？
おまけ
クイズ1-5について、
$ gcc foo.a main.o bar.a
や
$ gcc foo.a bar.a main.o
にした場合、いろいろ挙動が変わりますが、なぜでしょう。 1-10 に正解できる人はこれも正解できると思われるのであまりクイズにする意味は無い感じなので、おまけです。
解答
リンカの .a や .o に対しての挙動について知っていれば、ラクに全問正解できると思います。全問正解できなければ、いくつあってても、あまり大差無くわかってない、という感があります。
正解は…
- クイズ1: 普通にリンクできる
- クイズ2: multiple definition of `baz'
- クイズ3: 普通にリンクできる
- クイズ4: undefined reference to `foo'
- クイズ5: 普通にリンクできる
- クイズ6: multiple definition of `baz'
- クイズ7: multiple definition of `baz'
- クイズ8: multiple definition of `baz'
- クイズ9: 普通にリンクできる
- クイズ10: 普通にリンクできる
です。いやー何故か偉そうな文体で書いてるから、こういうの間違ってると恥ずかしいから確認した…
説明
まず、リンカのコマンドラインは基本的に左から右に眺めていきます。 .o ファイルがあると、その中にある全てのシンボルをリンクします。クイズ6-8はこの理由で単に baz が2回出現してしまっていて、クイズ9-10は循環参照があるけど両方ちゃんと定義してあるから大丈夫、ということになります。
.a は知らない人にはやや意外性のある挙動を示します。 .o を眺める時、未定義だったシンボルの一覧をリンカは覚えています。 .a に出くわすと、その中の各 .o を眺めてみて、未定義だったシンボルの入ってる .o を全てリンクします。この際、 .o についでに入っている、使用されてないシンボルなんかもリンクされます。
クイズ1では、 main.o を見て未定義シンボルが無いので、 foo.a と bar.a からは何もリンクされず、 main だけのバイナリができます。
クイズ2では、 main.o を見て foo が未定義なので、 foo.o をリンクします。すると bar が未定義なので、 bar.o もリンクします。そして baz が多重定義になります。
クイズ3では、 main.o を見て bar が未定義なので、 bar.o をリンクします。 foo.a はスルーされるので、 main, bar, baz が定義されたバイナリになります。
クイズ4,5 は循環参照です。 4 の方は main.o と bar.o だけを取ってきてしまって foo が未定義となり、 5 では main.o => foo.o => bar.o と芋蔓式に取ってくる必要ができて、無事リンクできます。
循環参照を解決する技
普通、クイズ1-3のようなケースで悩むことはあまり多くはなくて、4-5のような循環参照で悩むことが多いのではないかと思います。これを解決する方法はいくつかあります。クイズ4のケースを例に使います。
$ nm main.o # int main() { bar(); }
U bar
0000000000000000 T main
$ nm foo.a # void foo() { bar(); }
foo.o:
U bar
0000000000000000 T foo
$ nm bar.a # void bar() { foo(); }
bar.o:
0000000000000000 T bar
U foo
$ gcc main.o foo.a bar.a
bar.a(bar.o): In function `bar':
bar.c:(.text+0xa): undefined reference to `foo'
collect2: error: ld returned 1 exit status
素人くさい方法
まず、よく使われているであろう、 undefined reference が出るまでひたすら .a を足していくという技。
$ gcc main.o foo.a bar.a foo.a
個人プロジェクトとかでは別にいいと思います。わかりやすいですし。ある程度大きい規模の開発ではこの方法ではスケールしないんでないかと思います。
-u
シンボル foo は未定義なんだよ、と明示的に教えてやる方法。リンカオプション -u でリンカに未定義なシンボルを教えてやることができます。 -Wl を使うと gcc はリンカにオプションを伝えてくれます。
$ gcc main.o -Wl,-ufoo foo.a bar.a
foo.a と bar.a をセットでライブラリとして提供してる場合で、明確に拾いたいシンボルがわかってる場合は、この方法が一番リンクにかかる時間とかが少なくて良いと思われます。例えば SDL_main のような。ライブラリとかで無い場合はシンボルの一覧を管理するのがめんどくさいと思われます。
--start-group
最初に書いたような、ひたすら .a を足していく、というのを自動的にやってくれるオプションがあります。 --start-group と --end-group がそれ。
$ gcc main.o -Wl,--start-group foo.a bar.a -Wl,--end-group
とすると、未定義シンボルがなくなるまで、 foo.a と bar.a を循環してくれます。昔は濫用すると遅かったようですが、今ではあまり気にならないのではないかな…と思います。
--whole-archive
少し毛色が違うものですが、この .a は .o みたいな感じで全部シンボル拾ってきておくれ、と指示するオプションがあります。
$ gcc main.o -Wl,--whole-archive foo.a bar.a -Wl,--no-whole-archive
ただ、あまりこの用途で使うことは無いと思います。
よくあるのは、 shared object を作る時に使うケースではないかと思います。さっきの foo.a から foo.so を作ることを考えます。
$ gcc foo.a -shared -o foo.so
$ nm -D foo.so
w _ITM_deregisterTMCloneTable
w _ITM_registerTMCloneTable
w _Jv_RegisterClasses
0000000000200830 B __bss_start
w __cxa_finalize
w __gmon_start__
0000000000200830 D _edata
0000000000200838 B _end
00000000000005e8 T _fini
00000000000004a8 T _init大変です。 foo が入ってません。これは基本ルールを思い出すと簡単で、 foo.a を眺めた時に、特に未定義なシンボルが無いので foo.a がスルーされたというだけの話です。
こういう、この .a に入ってるシンボル全部入ってる .so 作ってくれーという時に --whole-archive は便利で、
$ gcc -Wl,--whole-archive foo.a -Wl,--no-whole-archive -shared -o foo.so $ nm -D foo.so | grep foo 0000000000000685 T foo
などと。無事入ってました。
shared object
はまぁ割とみんなが想像するような挙動をするというか、リンカの段階では難しくなくて、ローダの側でやや難しい感じですね。
libc.a
libc.a に入ってる .o が、1関数につきひとつあるみたいな状態なのは、 static link した時のバイナリサイズを最小にするため、というようなことが予想できますね…
