Tokyo Westerns CTF 3rd 2017 Writeup
https://tokyowesterns.github.io/ctf2017/ja/
2, 3 回目くらいの CTF。
Ofuna Gourmet Explorers で参加して 28/901 位でした。
ほとんどPPCしかやってないものの、そこそこ高得点な問題も解けたりFA取れたりしたのでよかったです。
Palindromes Pairs - Coding Phase - (PPC, Warmup, 24 pts.)
https://score.ctf.westerns.tokyo/problems/12
やるだけ。 nc ⇔ stdio 中継はちょうど少し前に ICFPC で書いていたのでそれを思い出しながら。
https://gist.github.com/logicmachine/c7a5e415edb1d8b1b2d33751b1a6ef49
Backpacker's Problem (PPC, Misc, 177 pts.)
https://score.ctf.westerns.tokyo/problems/18
ジャッジプログラムをよく見ると最後の std::accumulate の呼び出しにバグがあります。
std::accmulate() の戻り値の型は第3引数の型 (この場合int) になるので、選択した数の総和ではなく、その下位32ビットが0であればよいということになってしまいます。
候補となる数の絶対値はどれも2^32より十分に大きいので、先頭40個くらいの数の集合からいくつかを選ぶ問題としても十分高い確率で上述の条件を満たす解が見つかります。
n=40くらいなら半分全列挙で解けるので、入力を適当に捨てた後は普通に解いてしまいましょう。
https://gist.github.com/logicmachine/4b353e5dca00a5166d242f45648bff32
pplc (PPC, 31+31+30 pts.)
https://score.ctf.westerns.tokyo/problems/19
REPL 上で inspect 片手に使えそうなものを探す。
private: getattr(p,dir(p)[0])()
local: get_flag.__code__.co_consts
comment: comment_flag.__doc__
Liar's Trap (Crypto, PPC, 281 pts.)
https://score.ctf.westerns.tokyo/problems/33
x_i = i^0 a_0 + i^1 a_1 + ... + i^25 a_25 (1 <= i <= 100) と表される数列 x が与えられるので、それから a_0 を求めます。ただし、xのうち38要素はただの乱数に置き換えられてしまっています。
全員が正直な値を伝えている場合、適当に25人選んで掃き出し法などで解が求まります。
嘘つきがいるときにランダムに選んだ25人が全員正直者である確率を考えると、62C25/100C25 となるので、だいたい160万回に1回くらいは正直者のみの集合を得ることができます。
適当に選んだ25人が正直者かどうかは、適当に1人削って残っている別の人を入れるのを何回か繰り返し、最初に選んだ25人から求めた a と等しくなることがあるかどうかでそこそこ高い確度で判定できます。
正直者判定は手元の環境だと1000回/sくらい回せていたので、1時間くらい回せば十分回答が見つけられそうです。（実際には寝ている間に回して3時間強で2回くらい当たっていたので、結構運が悪かったようです。）
https://gist.github.com/logicmachine/afccaec92ffc062716458025152853b9
