ksnctf #36 Are you ESPer?
問題
http://ksnctf.sweetduet.info/problem/36
考えたこと
リンク踏んだらぶっ壊れたファイルみたいなのでてきたけど、よくみたら一番最初にELF(Executable and Linking Format)とか書いてあったから、これは実行ファイルであるとわかる。とりあえずダウンロードしてncコマンド殴ると、数字をあてるゲームが始まる。乱数かなっておもって適当にコード書いて流し込んだら弾かれて???ってなった。困って別問題やってたときに、向こうのサーバーと時間差があることを知った。そこで、srandの初期化の時間を無効のサーバーに合わせてあげて、パイプラインで実行結果を流してあげたらフラグをとれた。
おまけというかついで
rand関数は、初期設定を行わない場合、常に同じランダムパターンを返すことになっていて、これでは乱数の意味をなさないので、srand関数を用いて初期化の時刻を自分で設定してやる。何気なくsrand(time(NULL));とか書いてたけど、改めてちゃんと理解した。
akictf #6 Game#1
問題
http://ctf.katsudon.org/problem/6
考えたこと
URLを踏むとJankenと書かれたページが出てくる。とりあえず普通にやってみたら、何を出しても負けになり、すぐにmoneyがなくなる。なんだこいつと思ったけど、10ってとこかRankingを変えてやればいいんじゃねと思い、Chromeのデベロッパーツールで編集をする。ザーッと見てやると、その中に
<input type="hidden" id="h" value="d3d9446802a44259755d38e6d163e820">
というHTML文がある。valueの中身がどういうものかよくわからなかったので、そのままググってやるとこれがMD5でエンコードされた10であるとわかった。ならこれと上の10っていう数字を書き換えたらいいんだなと思ってRankingの1位の数字(一千万)より大きい数字にしてRegisterボタンを押してやったらフラグをゲットできた。
おまけというかついで
curlコマンドでごにょごにょしてもできると思うけど、curlコマンドがいまいちよくわかってないのでアレ() デベロッパーツールは強いなあと思いました(こなみかん
akictf #21 loop
問題
http://ctf.katsudon.org/problem/21
考えたこと
とりあえずURL踏んでみたらリダイレクトが繰り返し行われた云々って出てきたから、タイトルの意味はそれかと納得した(リダイレクトループ)。じゃあどうしようとなって、まあwebページ類の問題だし常套手段としてcurlコマンド殴ったらいいんじゃね?と思って適当にオプション調べてはえ〜ってなって色々してたらX-Flagっていうのが出てきた。頭にX-ってついてるやつはHTTPのルールでオレオレフィールドらしい。Flagとも書いてあるしこれ使えばいいやんけっていうのはわかった。どうやって使うのかはわからなかったので、全部つないでncコマンドとかやってみたけどさっぱりだったのでなんじゃこりゃ〜って言って答えに投げたら通ってしまった(要するにいじらなくてよかった)。
おまけというかついで
write_upとか見てるとシェルスクリプト書いてあって、こういうことぱぱっとかける人はすごいなあと思った。私は手動で全部つないだけど、awkコマンドとか使えば勝手につないでくれるのでそっちの方が絶対楽だよね。
akictf #13 Yet Another G00913
問題
http://ctf.katsudon.org/problem/13
考えたこと
前にksnctfのG00913っていう問題について書いた時にも触れた問題だけど、PPC (Professional Programming and Coding)なので当然プログラムを自分で書く必要がある。詳しくはG00913の記事のおまけというところを参照されたい。私は1000桁調べたけど、実際は500桁も調べたら十分である。まあつまり考えたことは特になくコード書いて走らせただけって話。
おまけというかついで
このコードを書くにおいて苦労したことは、gmp_prob_prime()の第一引数が文字列っていうことを知らなかったので、integerにキャストしてそこに通していたので、1000けた回しても素数でてこないじゃんはわわ〜ってなったことぐらいですかね。
コードあげといてもいいんだけど、ぐちゃぐちゃのgitを見られるのは恥ずかしいので、あげるのはやめときます..
これのコード書いててひとつ気になったんですけど、
$num = "1234056789"
$tmp = substr($num, $i, 1);
if($tmp == 0){
continue;
}
みたいなcontinue文の使い方、例外処理(というほどでもないけど)の仕方って許されるんですかね..
ksnctf #20 G00913
問題
http://ksnctf.sweetduet.info/problem/20
考えたこと
問題文に FLAG_Q20_{first 10-digit prime found in consecutive digits of π} とあったが、そもそもG00913ってなんだよ聞いたこともないぞと思い、タイトルをググった。そうすると、下の写真が出てきた。これはgoogleの求人広告らしい。どう見てもこれをオマージュした問題である。答えそのものはググったときについでに出てきた。
おまけというかついで
これまたこいつをオマージュした問題でYet Another G00913という問題もある。
http://ctf.katsudon.org/problem/13
これの厄介なところは200桁を判定しなければならないところである。上の10桁程度ならRubyのPrimeクラスとか使えそうだが、さすがに200桁は無理なので、別の方法を考えないといけない。他のアルゴリズムとして桁が小さければエラトステネスのふるい、フェルマーの小定理(フェルマーテスト)があったりするが、それは疑素数といって素数でなくても通ってしまう数字が出てくる。それを改良しても通ってしまうカーマイケル数というものもあるが、まあ詳しくはググってください(細かく書くのが面倒)。そこで今回用いるミラーラビンテストの登場である。こいつは200桁の素数判定でも一瞬で終わる優れものである。これも確率的素数判定なので間違いが出ることはあるが、その確率は判定回数をk回とすると「4^-k」なので、kを大きくすればほぼなくなる。実装はさほど難しいわけではないが、PHPならgmp_prob_prime()という組み込み関数がミラーラビンの確率的テストによっておそらく素数であるか調べてくれる。この辺のもう少し詳しい話は気が向けばMathIについての記事を書いた時にやろうと思う。
ksnctf #10 #!
問題
http://ksnctf.sweetduet.info/problem/10
考えたこと
ただの知識問題なので特にない。知らなかったらググったら即答できるやつ。
指示に書いてある通り、最初の文字だけ大文字にすることを忘れなかったらさほど問題ないと思う。
おまけというかついで
見かけたことがあるとすれば、シェルで出てくる
#!/bin/sh
#!/usr/bin/env ~
みたいなやつだと思う。前者については、パスを直接指定するものである。後者は、Unix/Linux系の環境では、スクリプトの1行目に記載しておき、スクリプト自体を実行することで記載されたプログラム(例えばPython)を実行しそのプログラムに、スクリプトの内容を渡し動作させることができる、といったものである。例えば、sample.pyみたいなのを作ったら、$./sample.pyとかやると、#!によってプログラムが実行され、プログラムにsample.pyが渡され処理されるといった流れになる。(あいまいな知識なので、間違ってるかも)
akictf #3 cheap cipher(revenge)
問題
http://ctf.katsudon.org/problem/3
考えたこと
タイトルからして前にあったcheap cipher類の問題であろうと予想はできた。
cheap cipherでは問題の文字列の前後を逆にしてbase64でデコードすると答えが出たけど、これはちょっとひねりを加えて逆にしないといけない。逆の仕方としては、base64の変換表を逆にする。そして、逆にした後の変換表に基づいて文字列を更新する。
どういうことかというと、たとえば、A→=、B→/、C→+、D→9といった具合
こうすることでbase64でエンコードされた答えが手に入る。それで解けた。
おまけというかついで
実はこれ自分ではパッと思いつけなくて、知り合いにヒントをもらって解けたものである。まあ正直新しい知識があるかって言われたらないけど、base64のそれっぽい実装の練習というか、新しいテーブルを作って自分で変換するっていう面白さみたいなのがあった。