Tokyo Westerns CTF 3rd 2017 に Ofuna Gourmet Explorers で参加しました。
https://github.com/tomerun/CTF/tree/master/TokyoWesterns2017
Rev Rev Rev
gdbで実行しながら追っていく。main関数の中で4回サブルーチンに飛んでいる。
- 1回目は末尾の改行を除去しているだけ
- 2回目は文字列の前後をreverseしている
- 3回目は、何かビット演算を色々やっている。結果をよく見ると各バイトのビット上位下位を反転させているように見えて、きっとそうだと思う
- 4回目は、ビット単位で0-1を反転
メモリアドレス 0x8048870にあるデータを期待値として入力と比較しているので、上記の操作を逆にやるプログラムを書いてflagを得た。
3回reverseしてるからこの問題名なんですね。
BabyRSA
qがp*19くらいなことから、p,qの上位桁半分くらいは特定できる。
rsa attack ctf とかでググって http://inaz2.hatenablog.com/entry/2016/01/20/022936 にたどり着き、これの「素数pの上位bitまたは下位bitがわかっている場合」を適用して解けた。
BabyDLP
1bitずつ決めていく。
$i$ を入力したときに得られる値を $f(i)$ とする。
$f(2^{k}) = f(0) * 2^{2^{k}} \pmod{p}$ の場合、flagのkビット目は $0$ 。そうでなければ $1$。
BabyPinhole
messageの下半分のbitを求めてから上半分のbitを求める。
- 下位bitは、ciphertextに $g^{x}$ を掛けたものをデコードさせることで $message+x$ が得られるので、デコード結果から繰り上がりがあったかどうかを観測することによって上から1bitずつ決定できる
- 上位bitは、ciphertextを $2^{-k}$ 乗してデコードさせることで下から1bitずつ決定できる
- $message = 2^{k}*m^{\prime} + m^{\prime\prime} (0 \le m^{\prime\prime} \lt 2^{k})$ とする
- ciphertext を $2^{-k}$ 乗してデコードさせた結果は、 $message * 2^{-k} = (2^{k}*m^{\prime} + m^{\prime\prime}) * 2^{-k} = m^{\prime} + m^{\prime\prime} * 2^{-k}$
- で、messageの下位bitである $m^{\prime\prime}$ の値は知っているので、観測した値をもとに $m^{\prime}$ の b bit目、つまり messageの (b + k) bit目がわかる
- これを$k=1$から順に1つずつ増やしていって実行する
Palindromes Pairs - Challenge Phase -
よくわからないのでとりあえずランダム生成して投げてみたらflagが出てきて、は??!!?!? となった
サーバーに問題があったらしく、修正されてflagが追加された。それは取れず
その他
Reversing(TW interpreterとか)も少し見ようとしたけど、ほとんど進まず。
objdumpとgdbで地道に読んでいくだけだと膨大に時間がかかるので、適切にツールとか使えるようにならねば