Tokyo Westerns/MMA CTF 2nd 2016 write-up

ちょくちょくできないなりにCTF参加してるけど、記録を残さないと自分でも忘れてしまうので。
Web系が一つもできないのはつらい。アセンブリ読むの好きといいつつPwnも全然ダメ。このあたりができればもっと楽しいのだろうなぁ。

[Misc] [Warmup] Welcome!! (10pt)

問題文に書いてあるのを入れるだけ。

[Pwn] [Warmup] judgement (50pt)

printfの第一引数に入力が渡っている。スタック上に残っているflagのポインタを読むように"%28$s"を渡してやればよい。

[PPC] [Warmup] Make a Palindrome! (20pt / 30pt)

10! = 3628800通り全部試しても3分の時間制限に間に合う。

[Crypto] [Warmup] Twin Primes (50pt)

p*qと(p+2)*(q+2)が与えられるので、p+qが求まって、解と係数の関係でpとqがわかってしまう。あとはencrypt.pyの逆の手順をたどればよい。

[Reverse] [Warmup] Reverse Box (50pt)

とりあえず動かしてみると、実行ごとに同じ入力でも出力が変わるが、一回の実行中に同じ文字には同じ出力しか出ない雰囲気。rand(3)を使っているところが初期化の一箇所だけで、しかも下位8bitしか使われない。rand(3)をLD_PRELOADでフックして256通りの値を試すと、TWCTFが問題文に書かれた出力になるのはrand(3)が214を返すとき。あとは換字表を作って変換すればよい。

[Crypto] Super Express (100pt)

ごちゃごちゃやっているけど結局入力の線形変換になるので、先頭をTWCTFとしたときの変換式を求めてデコードする。

[Crypto] Backpacker's cipher - easy mode (200pt)

pとqがわかったときにどうdecryptするか考える。mod p上でpubkeyの各要素をqで割ると、pubkeyのi番目の値は下から見てiビット目で初めて1が立つ値になる。messageをqで割ったものについて、下から順に1が立っているかどうかをチェックし、1が立っているときにpubkeyをqで割ったものを引くようにすると、DESで暗号化したビット列が得られる。
generate_keyのaの作り方から、pubkeyの最後の要素は2^1023*q%p、その一個前の要素は2^1022*q%pまたは3*2^1022*q%p。前者の場合にpが312桁の素数になってそれっぽい。2^1023の逆数を掛ければqも求まる。

[Crypto] Vigenere Cipher (200pt)

ASCIIのplain textをBase64 エンコードしているので、必ず0が来るビットがある。全文についてこの性質が成り立つことを利用すると、keyの要素は繰り返し使われるので、keyの長さや範囲を絞ることができる。
この時点でkeyの長さが12、そのうち8要素はほぼ中身が確定するので、一度元の文字列らしきものを出してみると、最後のほうにflag is TWCTF{という文字列が来そうなので、残りのkeyも確定できる。

[Reverse] [PPC] Whiteout Mathmatics (200pt)

Whitespaceのプログラムを読むと、与えられた数値の間の各数について約数の和を求め、それの最大値を出力することがわかる。要は10^12までの数で約数の和が最大になる数の、その約数の和を答えればよい。
どうせそのような概念は既にあるだろうと約数のWikipediaを眺めたら、高度過剰数という概念がありOEIS経由でテーブルにたどりつけた。あとは995886571680をfactorして約数の和を求めればよい。

[PPC] Lights Out! (100pt / 300pt)

各マスを縦に、押したときに変化するマスを横にとった行列を作って、GF(2)上でAx=bを解けばよい。normalはガウス消去で十分速い。
lunaticはできていない。O(N^3)だと死んでしまうので、疎行列であることを利用して反復法で解くのかなとか考えていた。素因数分解でblock Lanczos法を使うように。

[Misc] glance (50pt)

情弱なのでWindows上でフリーソフトでGIFを分解してBMPにしたのち、BMPのフォーマットを参考にしつつ各行を順に結合して新しいBMPを吐くプログラムを書いた。もう少し楽なやり方があったかもしれない。

[Misc] ninth (100pt)

zlibでIDATの中身をinflateすると、画像データのあとにflagが書いてあった。