Tokyo Westerns/MMA CTF 2nd 2016にチーム NaruseJun で出ました。
メンバーは kaz, long_long_float, nari, phi16, ponya の5人です。
そのほかにも、何人かお手伝いしてくれた人たちがいます。（感謝?）
結果はScoreが2440で 22nd でした。
以下writeups
Welcome!! (nari)
フラグが置いてあるのでコピーしてペーストします
Global Page (kaz)
$_GET["page"]をいじってパストラバーサルができそうなんだけど、/と.が消されてしまうので辛い。
問題名の Global がポイント。
出力されているHTMLを注意深く観察すると、
Accept-Languageヘッダを見て対応する言語名でPHPをincludeしているのが分かる。
しかもこちらは危険な文字の除去を行っていない。
出ているエラーメッセージから、
$page = str_replace(["/", "."], "", $_GET["page"]):
foreach($_SERVER["HTTP_ACCEPT_LANGUAGE"] as $lang){
include("{$page}/{$lang}"));
}
ってやってるのがわかるので、php://filterを使って
curl http://globalpage.chal.ctf.westerns.tokyo/?page=php: -H "Accept-Language: /filter/read=convert.base64-encode/resource=****"
これで好きなPHPファイルのincludeできる。
index.phpをみるとflag.phpをincludeしているのがわかるので、このファイルを同様にincludeしておわり。
judgement (phi16)
とりあえずprintfが使われているようなのでFormatStringAttackっぽい。
何も考えず順番に%n$sしてその辺にある文字列を読みに行こうとしたらn=28であたってしまった。終了。
Make a palindrome (nari)
ただの競プロ
C++でnext_permutation回すコードを書いてrubyで鯖アクセスしてC++のプログラムを実行
Rescue Data 1: deadnas (ponya)
「ディスクを3台載せたNAS」という問題文からRAID5と予測。
disk1ファイルが壊れているのでdisk0とdisk2のXORからdisk1を復元する。
パリティの位置とデータの順番から次のようなコードを書いて全部のデータを結合する。
chunk = 512
b0 = bytearray(open('disk0', 'rb').read())
b1 = bytearray(open('disk1', 'rb').read())
b2 = bytearray(open('disk2', 'rb').read())
b = bytearray()
for i in range(int(len(b0) / chunk)):
j = i % 3
start = 0 + chunk * i
end = chunk + chunk * i
if j == 0:
b.extend(b0[start:end])
b.extend(b1[start:end])
elif j == 1:
b.extend(b0[start:end])
b.extend(b2[start:end])
else:
b.extend(b1[start:end])
b.extend(b2[start:end])
open('disk', 'wb').write(b)
出てきたファイルをマウントすると、画像ファイルにFlagが書いてある。
Twin Primes (nari)
2回RSAする、(p,q)と(p+2,q+2)が秘密鍵
なんとn=pq,m=(p+2)(q+2)からp,qが求まってしまい終了する
Reverse Box (phi16)
入力を与えると各文字毎にhexになって帰ってくる。同じ文字は同じ文字になるようなのでそれを使えばどうにかなる。
seedが256種類しかないので1秒ごとにTWCTF_ABC...789みたいな全文字列を投げるスクリプトを組むと直ぐに95eeafから始まるパターンが見つかる。
これで置換表ができたので戻せば終わり。でもハイフンの確認をしていなかったのでちょっと焦った。
Super Express (kaz)
import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'
if len(key) % 2 == 1:
print("Key Length Error")
sys.exit(1)
n = len(key) / 2
encrypted = ''
for c in flag:
c = ord(c)
for a, b in zip(key[0:n], key[n:2*n]):
c = (ord(a) * c + ord(b)) % 251
encrypted += '%02x' % c
print encrypted
こういう暗号化をしている。
forループで複雑に暗号化しているように見えるけど、これは結局 を計算してるだけ。
このは と は鍵に固有なので、フラッグの先頭がTWCTF{であることから推測できる。
251を法としているため も も で求めればよいので、全ての組み合わせで試す。
data = [0x80, ..., 0xf9]
for a in 0..250
for b in 0..250
if (0x54 * a + b) % 251 == 0x80
flag = ""
data.each do |ch|
for i in 32..126
if (i * a + b) % 251 == ch
flag += i.chr
break
end
end
end
if flag =~ /^TWCTF/
print flag, "\n"
exit
end
end
end
end
ESPer (nari)
なんか最初に全探索させられる(面倒)
特に意味はなくてそれが終わるとRSA暗号が作れる画面が出てくる
秘密鍵は接続時に毎回生成、肝心の暗号化されたフラグはExit時に出る
ので、接続中に秘密鍵を奪取しないといけない
エスパーできるのは暗号化/復号化のコードの任意の行の直前に一つ変数を2^2048までの乱数に置き換えられる
まずp,qのqを取得する
暗号化は次のようなコードで行われる
p, q, dp, dq, qinvp = read_privkey(ARGV[0])
print "Encrypted Message c: "
STDOUT.flush
c = STDIN.gets.to_i
m1 = decrypt(c, dp, p)
m2 = decrypt(c, dq, q)
m = merge(m1, m2, p, q, qinvp)
puts "Decrypted: #{m}"
STDOUT.flush
これは中国人剰余定理を用いた高速化されたRSAで、具体的には次のようなことを行っている
m1 = modpow(c,dp,p)
m2 = modpow(c,dq,q)
h = qinvp * (m1-m2+p) % p
m = m2 + q*h
ここで、m2が特定でき、h!=0であれば、m-m2=q*xのような形の数が得られる。
これを2つ用意すれば、q = gcd(m-m2, m'-m2')のようにすることでqが求まる。
ただし厳密にはqが求まるわけではないが、qが求まらない確率は低い(僕は一発だった)。
なんか多分任意の2数が互いに素になる確率みたいなやつだと思う。
qが求まってるかどうかの確認はミラーラビン素数判定で。
次にpを求める。
これはencryptで行う。
m=2とすると2^65537 mod pqが返ってくる。これをaとする。
m=3とすると3^65537 mod pqが返ってくる。これをbとする。
すると、2^65537-a = kpq, 3^65537-b = lpqとなる。
これもさっきと同じでp = gcd((2^65537-a)/q,(3^65537-b)/q)で大体求まる。
僕は一発だった。
これでp,q,n,dが求まるのでおしまい。
ちなみに仕様が分からないけど4回命令を送ると強制的に終了するらしく多分これが想定。
終了するとフラグが落ちてくるのでそれを復号化。
Backpacker's cipher - easy mode (nari)
pubkey_1023q^{-1} = 2**1023
pubkey_1022q^{-1} = 21023? + 21022
であることが容易にわかるので、?の部分を2通り試してp,qを求める。多分求まる。
今回は運良くp,qが求まる。
これで、後は暗号をqで割って上げると2進数のナップサックっぽくなって、
採用してるかどうかはビットを見ると順番に決められるようになるのでおしまい
Vigenere Cipher (nari)
Vigenere Cipherをします
文字列の感じから周期が6か12であることは大体わかります(12として差し支えないです)
フラグはTWCTF{を含むので、これを含むようなものを探します。
といっても無理なので、「どの位置にフラグを含むか」を固定して、
暗号化したらTWCTF{を含むようなキーを一部確定させます。
周期的に暗号化が解けるのでそれで文章の半分くらいの暗号が解けます。
そこで表示不可能な文字が入っていたら、それは明らかに間違っているのでこの位置のフラグを諦めます。
ということをやると大体後ろのほうでフラグが見つかります。知ってた。
後はなんか雰囲気で残り半分のキーを確定させると、なぜかSKK(入力システム)の宣伝と共に
「古典暗号は楽しい」みたいなフラグが手に入ります。
あと、この問題、base64を使ってるくせに英語小文字と英語大文字が逆転してVigenereしてます。
許さない。
rps-ng (nari)
じゃんけん50戦40勝以上する
相手が「相手の手の遷移回数を保存しておいてその遷移が多いやつで相手の次の手を予想する」AI
なんかこっちでもそれっぽい配列を持って、遷移回数の辻褄が合うように貪欲に調節
すると運が良くて49勝 悪くても勝率5割になるので後は試行回数
whiteout mathematics (nari)
whitespaceをWS2JSとかで解読すると次のようになる
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int ans = -1;
for(int i=n;i<=m;++i){
int tmp = 0;
for(int j=1;j<=i;++j){
if( i%j == 0 ){
tmp += j;
}
}
ans = max(ans,tmp);
}
printf("TWCTF{%d}\n",ans);
return 0;
}
まぁなんか数列っぽい感じを覚えるので適当に(100,1000)と(100,10000)の結果でOEISにかけると都合よく出てきてしまうので終了
https://oeis.org/A066410
Private / Local / Comment (long_long_float)
Rubyの問題
Private
publicなメソッドが全てprivateにされている(ついでにPrivateはnilにされている)のでsendすら呼べない(良い子はやってはいけない)。Rubyのprivateメソッドはレシーバ(.の左側のインスタンス)がなければ呼べるので、特異メソッドというインスタンス特有のメソッドを生やしてその中でflagを呼べばいい。
def p.s;flag;end;p.s
Local
Rubyは1.9.0から独自の仮想マシンで動くようになっており、スクリプト実行時にそのVM向けのコードにコンパイルするようになっている。そのコンパイルした関数(ここではget_flag)を逆アセンブルすればflagが見える。
RubyVM::InstructionSequence.disasm(method(:get_flag))
Comment
Ruby処理系では内部で使うデータ(例えばHash)もRubyのGCに載っけている。なのでrequire_relative 'comment_flag'するときにcomment_flagのソースコードがGCされる領域にあるはずであって、それを拾えばいい。
s='#';ObjectSpace.each_object(String){|o|o[0]==s&&puts(o)}
最初にs='#'としているのはブロックの中に'#'を書くとブロックが呼ばれた回数だけオブジェクトが生成されるらしく、出力が#だらけになったので(今思い返すとo[0]の時点で新しいオブジェクトが生成されるから意味なかった…)。この問題は試しにやったら出来てしまったので説明が正しいか自信がない。
Lights out (nari/phi16)
押した場所からマンハッタン距離2の最大8マスが反転するライツアウト
上2行を決めるとその他のボタンを押すべきかどうかが上2行で決まる
最終的に下2行が点灯しているかどうかという条件に落として、2W変数2W方程式の連立方程式を解けばOK
計算量は各マスについて2W変数の関係式を立てて、さらに2W*2Wの行列の方程式を解くのでだいたいO(W^3)ぐらい？
実はWH変数WH方程式でも結構行列が疎なのでガウスジョルダンの方法だと計算量がそこそこで数分とは言わないけど現実的な時間で解ける
追記 / 
は神 (Z/pZ上で連立方程式の解を取る方法があったのでHaskellで生成した行列を投げたら終わり)
Rotten Uploader (kaz)
/download.phpにパストラバーサル脆弱性があるのでソースコードが読める。
コレでindex.phpを読むと、どうやらfile_list.phpにフラッグが書かれたファイルのパスが格納されていることがわかる。
しかし、download.phpを読むと、
<?php
header("Content-Type: application/octet-stream");
if(stripos($_GET['f'], 'file_list') !== FALSE) die();
readfile('uploads/' . $_GET['f']); // safe_dir is enabled.
?>
file_listが弾かれてる。
ここでなんでstriposが使われてるのか？って考えると、もしや大文字小文字の区別がされないOSなのか？ってなる。
そうするとまぁWindowsかな？ってなるんですが、Winでは通常のファイル名に加えて8.3形式でファイルを表すことができる。
file_list.phpを8.3形式にするとFILE_L~1.PHPとなって、これは先ほどのstriposチェックを回避できる。
file_list.phpを読めばフラッグが書かれたファイルのパスがわかるので、あとはそれを読んでおわり。
glance (kaz)
フラッグが書かれた画像ファイルを縦に細かく分割してgifアニメにしたものが与えられる。
Imagemagickで元に戻すだけ。
magick glance.gif +append flag.png
ninth (phi16)
とりあえずimage basedじゃないらしいのでbinaryを見る。良くわからない。
PNGのヘッダーを見ながら怪しそうな場所を探すも無い。残るはメインのIDAT、これはDeflateで圧縮されているので展開する。
展開の仕方がわからないのでぐぐるとopenssl zlib -d < $IN > $OUTが見つかって大爆笑する。
出てきたbinaryを読んでみたら一番下にflagがありました。
Cocktail (phi16)
を入力信号列とする。
やっていることは という列をどっかで切って前後を交換し、それと との内積をとるということ。
切っている部分は具体的にはわからないが列のShuffleなので同じものは無い。つまりある音声の強さが分かればうまいこと切った位置を合わせて元の が復元可能。
というわけでホワイトノイズ列の強さを適当に測定する(audacityでグラフ出して自己相関の最大値を拾ってきた)と、
1 : 22.060
2 : 19.831
3 : 18.048
4 : 15.692
5 : 13.305
6 : 12.422
7 : 12.446
8 : 25.045
9 : 23.512
10 : 23.504
とかいう数値が得られるので、これを元にで行列を生成。 が分かったので と をかけて元の音声が得られる、はずだったけどどっかミスってるっぽくてノイズまみれ。でもある程度は良く聞こえる。
6と7の順序が反転しているのを無視すると更にクリアになり、かろうじて聞き取れないことはないのでこれでがんばる。
The flag of part 2 is 76655f7930755f6b
The flag of part 6 is 7274795f33666633
The flag of part 5 is 6b7434316c5f7034
The flag of part 3 is 6c30776c5f314334
The flag of part 7 is 63745f73316c6333
The flag of part 1 is 54574354467b4a34
The flag of part 4 is 5f346c645f433063
The flag of part 8 is 5f6633663072337d
それっぽいflagが生成されるも英文になってない。リスニング力がないので6Cと6Eが間違っている。
traQ(部内SNS)で集合知に掛けたらFlagが出来てしまった。
