なんかとても面白かった。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 スタイル。

Smart Cipher System

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

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

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

いくつかの古典暗号。3つ目はブルートフォースで、4つ目は手をつけなかった。

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 、て感じか。

2015-09-01

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

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

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

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

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

2015-08-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/

2015-06-04

Unix v6 の C コンパイラが面白かった話

Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。

読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、

http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdf

の「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。

コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。

構文木のノードの種類に対して switch してやること決める…的なものが、データドリブンな方法で書かれてます。データを保存するフォーマットは、 JSON とかではなく、時代が時代ですのでアセンブリです。こういうやつ

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/regtab.s

ちなみにこれは v6 より古い時代のコードらしく、だいぶ v6 のやつよりシンプルですが、まぁ v6 も本質的にだいたいいっしょです。

たとえば 60 番 (これは == のノード番号) を見てみると、

	60.;	cr60

となってて、 cr60 の定義は

/ relationals
cr60:
%n,n
	HC
	I	2f
	clr	R
	br	1f
2:	mov	$1,R
1:

です。

最初の %n,n みたいなやつは、構文木にぶらさがってる左右の子が何者か、を示してます。 n はなんでもいいよ、っていうやつ。例えば %n,z だと右の子が定数ゼロなのでちょっと良いコードを出力する…みたいなことができます。

そこからはちょっとした VM というかなんというかの命令列です。大文字は全部特殊な意味があって、それ以外はそのままアセンブリとして出力されます。

HC は構文木のこのノードを含めてここから下を評価して condition code に置いて、という意味です。 I は自分のノード番号に対応する命令を置いてね、という意味。対応する命令ってのは

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/c1t.s

に表になっていて、

	60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text

とあるので 60 番は beq です(2番目のエントリは bne ですがこれはちょっと特殊な用途や、命令 I' で出力できます)。は当時のアセンブラの記法で、 .ascii と同じ意味と思ってください。

余談ですが 61 は != で、これの定義のしかたとかはちょっと素敵です。

	60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text
	61.; 1b; 0b

1b は後ろにある最初にある 1: ってラベル、ってやつなんで、 1b; 0b だと bne beq となって、なるほどひっくりかえってるんですね。この c1t.s を見てやると、同じ定数文字列を意地でも二度出現させない、という気遣いが見てとれるかと思います。

話を戻して、 R は今使ってるレジスタです。というわけで元のコードは、 == が成り立ってれば beq 2f で 2: に飛ぶので R=1 、そうでなければ R=0 、という感じのコードを吐く…という雰囲気がわかるんでないかと思います。

今は regtab.s というファイルを見ていて、 regtab がデフォルトのコード生成戦略なんですが、他にもスタックに置きたいときの sptab 、 condition code をいじりたい時の cctab 、副作用が欲しいだけなので式を評価した値はいらない時の efftab 、の4つの戦略があって、さっきの HC だと cctab を参照するように変化してたわけですけど、これが例えば HS だと sptab を見るようになるはずです。

てーいうことで HC は regtab を使ってたのを cctab に切り替える効果があり、その実体は

https://github.com/mortdeus/legacy-cc/blob/master/last1120c/cctab.s

の

/ relationals
cc60:
%a,z
	tstB1	A1

...

%n,z
	F
	tst	R

...

%n,n
	FS
	S
	cmp	(sp)+,R

にあります。これは長いので少しだけ見てみると、 %a,z は片方が既に addressible (つまり operand にそのまま来れるってことですな)で、かつ片方がゼロの時。こういう時は tst 命令一発、と。 B1 は A1 に対応する物体が byte か word かで b がついたりつかなかったりするだけ。

%n,z の場合は一旦レジスタ R に来てもらって…みたいな感じ。

一番一般的なケースの %n,n は、 FS は左辺をスタックに置いてね、 S は右辺をレジスタに置いてね、という意味で、最後の cmp はスタックを pop しつつレジスタと比較してる感じ。そのまんまですな。

なんというか、言語処理系の実装って、作る人の好みもあってか、メタな感じの実装になりがちだよねえと思ってたんですが、最初のコンパイラからしてこういうメタな作りかたしてたんだなぁと思いました。あと DSL って、こんな超初期の C コンパイラの時代からあったんだなあと。アセンブラ使ってるあたりは時代を感じさせますけど。

こんな作りになってる理由については、特に書いてなかったように思うんですが、コンパイラ自体のサイズの節約ではないかな…と思ってます。 == と != なら上記のようなことをして…みたいなのを C で書くより、こういうデータドリブンぽいやりかたでやった方がサイズ節約になる気がします。まあでも間違ってるかもしれません。

2015-06-03

ppencode2

Shibuya.pm で ppencode 2 についての話をしてきました。

http://shinh.skr.jp/slide/ppencode2/000.html

つうてもしかしはてなんの話したらいいんだっけ感があって、なんの話をしたんだっけ。。

しっかしまあ、できたんだなーよかったねー感はありますね。

おまけというかなふたつ

http://shinh.skr.jp/obf/yuine_kw.pl

http://shinh.skr.jp/obf/yuine_sym.pl

はまあなんかそれなりに面白い気がしないでもないが…

これはまあ通常、通常てのが何かは知らんが通常、よりは少し大変で。

なんだか quote に足りない文字があったりすりがたいしたことでもなく

まとめるとねむくてだるい

2015-05-31

Python 2/3 で小文字アルファベットと丸括弧だけで Quine を書く

http://shinh.hatenablog.com/entries/2015/05/11

の続き。 @mametter が next(reversed(range(i))) で i-1 ができるということと、 @phoenixstarhiro が unichr(x)in(list(unichr(y))) で x==y ができるということを発見してくれたため、現実的なサイズで Quine が書けました。

https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py

https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py3

今までいろいろクソコードを書いてきて、 http://shinh.skr.jp/obf/ にある程度まとめてたりしたんですが、最近全然アップデートしてないので、 github に新しい置き場を作ってみました。

https://github.com/shinh/hack

思いついた時に適当に色々足していこうかと思います。

2015-05-11

Python 2/3 で小文字アルファベットと丸括弧だけでプログラムを書く

http://d.hatena.ne.jp/nishiohirokazu/20120906/1346938523

を読んで、なるほどー、でもカンマが必要というのは説得力が弱いな、と思ったので頑張ってみました。任意の Python コードを小文字アルファベットと丸括弧だけに変換できます。

http://shinh.skr.jp/obf/ppencode_py.html

根っこの部分

は西尾さんのコードと同じ、つまり

print(bytearray((XXX)for(x)in(YYY)))

です。これ正直私の Python 力では自力では出てこないと思いますね。。

西尾さんは YYY の部分が大雑把に ASCII コードに対応する物体の tuple になってます。ここに tuple が必要だというのが、西尾さんの「カンマを使わずにイテレート可能なオブジェクトを作ろうとすると…」の元だと思うのですが、まぁ range/xrange はカンマ使わないわけです。

任意の数字を作る

さて、 range 使うとなると文字列長をあらわす数字が必要です。特に 256 までは任意の文字を表現するために必須と言えます。

西尾さんはタプルの長さを使ったりして、適切なサイズの文字列を作って len してました。カンマが無いと、単項演算しか無いわけで、だいぶやれることが減るのですが、いろいろ考えてると、数値を引数として数値をいじってかえす関数をいくつか作ることができます。例えば

len(repr(zip(bytearray(i))))

は i に入ってる数値を 6 倍する関数です。こういう感じで、 3 倍するであるとか、 4 倍して 14 足すであるとか、微妙な材料が色々得られます。 2 倍とか +X とか便利なものはありません。要は repr で文字列を伸ばしていて、その前にした演算によって伸びる率が違う、って感じです。あとは数値を減らす手段としては bin, oct, str, hex を使って、 len(oct(i)) などとするのが唯一だと思います。これらは底を 2, 8, 10, 16 とした log_k(i)+1 として機能します。

まあそんな連中でも 1000 程度までの数字なら作れてたみたいです。残念ながら 256 文字も使えば既にすごく遅いので、 JavaScript でのエンコーダでは 255 文字までしかサポートされてません。できあがったテーブルは

http://shinh.skr.jp/obf/alpha_paren_py2_data.js

にあります。

これで、大元の for の右っかわができそうな気配です

print(bytearray((XXX)for(i)in(range(YYY))))

YYY にこの方法で生成した数字をあらわす式を入れれば文字列長だけのループが回せるのです。

テーブルをひきたい

さて XXX の部分です。連番の数字を入力として、テーブル引きをしないといけないです。普通のテーブル引きは [] とか , を使う必要があると思うので、ダメです。唯一考えられたのはクソ遅い条件分岐の連打です。こういうやつ

if i == 0:
  return XXX0
if i <= 1:
  return XXX1
if i <= 2:
  return XXX2
...

こういう形なら、 Python の3項演算子で表現できます。 i == 0 はすごく簡単です…

i <= 1 をしたい

が、 i <= 1 から先は簡単でないです。数値 i を受け取って、 i が k 以下なら 0 、そうでなければ非ゼロを返す関数を作りたいわけですが…難しいです。手持ちの材料にあるのは定数かけ算と log(i)+1 です。そしてどっちも絶対に 0 を返しません。

なんかゼロになるもの…なるもの…と考えたところ、 48 がありました。 48 は '0' の ASCII code なので、 int(chr(48)) は 0 になるのです。というわけで、 1 を受け取ると 48 になって、 2 を受け取ると 49 から 57 の数字になる(Python の int 関数は数値じゃないもの受けると例外投げます)関数を探せば良いです。ありました。

len(repr(zip(bytearray(len(bin(len(repr(list(bytearray(len(repr(zip(str(bytearray(i)))))))))))))))

長いです。

比較をしたい

i <= 1 的なものができました。文字列長256までをサポートするとして、 256 個の i <= k 的な条件が並ぶので、残りの 254 個の k をどうにかしないといけないです。これは i が k 以下なら 1 、 k 以上なら 2 になるような関数をプログラムで探索すれば良いです。

0 を作るのと違って、これは割と現実的な話です。ひたすらかけ算を繰り返していくと、どこかでケタ上がりするわけで、 k 以下ならまだケタ上がりしてないけど、 k 以上ならケタ上がりしている、みたいな関数を探索すれば良いのです。 bin, oct, str, hex の 4 種類が使えるので、 2, 8, 10, 16 進数のどれかでケタ上がりしてれば OK です。

例えば、 i <= 3 は、 3 倍する材料は発見されているので、 len(str(i*3)) で良いです。 i == 3 の時は i * 3 = 9 はまだ 10 進数で一桁で、 i == 4 なら二桁になってるわけです。

この探索は、適当に総当たりをしたので、かなり時間がかかりました。

1, 2 だけにしたい

上記みたいな方法で作ると、 k より大幅におおきな数字に対して、 3 よりおおきな数字を返すことがあります。例えばさっきの len(str(i*3)) は i == 34 あたりから 3 を返しはじめちゃいます。

これの対処は簡単で、 len(str(i*6)) を繰り返せば良いです。 1 を 6 倍すると 6 なので 1 ケタですが、それよりおおきな数字はいずれ 2 に収束します。というかこれは log ですごく高速に収束するので、小さいプログラムの範囲では 1 回以上必要ないです。

これでできた比較用のテーブルは

http://shinh.skr.jp/obf/alpha_paren_py2_data.js

を CMPS2 で検索すると出てきます。

おまけ

なんのこっちゃですがだいたいこれ組み合わせるとできます。

str(bytearray()) の結果が全然違うため、 Python2 と Python3 両方で動くコードを作るのはどうも至難の技ぽかったので、しょうがないので別々にジェネレータを作りました。

あと、なんか Python3 のバグ踏んだ気がするので回避しておきました。暇な時に本当にバグか見ておこうと思っています。