makelisp.mk
https://github.com/shinh/makelisp
Lisp インタプリタを書きました。 GNU make で。
https://github.com/shinh/makelisp/blob/master/makelisp.mk
もちろん $(shell) や $(guile) は使わない縛りです。
だいたい sedlisp や beflisp と似たようなことができます。
最近作ってる 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 スタイル。
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 もやれば良い気がするので解ける気がする。
これ一般的に解くことできるのかなぁ…というのがわからない。
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 嫌いになったんだ。。
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を参照のこと
人狼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くらいでした。
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' で出力できます)。
余談ですが 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 で書くより、こういうデータドリブンぽいやりかたでやった方がサイズ節約になる気がします。まあでも間違ってるかもしれません。
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 に足りない文字があったりすりがたいしたことでもなく
まとめるとねむくてだるい
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 に新しい置き場を作ってみました。
思いついた時に適当に色々足していこうかと思います。
