0CTF 2017 writeup - きゅうり。

0CTF 2017にm1z0r3として参加しました。

266ptで111位でした。WelcomeとServeyを除いた222ptのうち189ptを入れました。

cryptoのintegrityとoneTimePadを解いたのでそのwriteupです。

その他writeup

・register

こちらからnameを送信すると、

md5(pad(name))+pad(name)

をAES-CBCで暗号化して、IVと暗号文が送られてくる。

ただしpad(name) == pad("admin")は弾かれる。

・login

こちらからIVと暗号文を送信すると、それを復号してmd5チェックをした後unpadして出てきたnameとしてログインする。

nameがadminならフラグ。

name = md5(pad("admin")) + pad("admin")としてregisterして、返ってきた暗号文からIVを除いてそのままloginに送信すればフラグ。

flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}

keygenという自作PRNGから乱数を生成しOTPにより暗号化したもの。keygenでは乱数をseedとしてprocess関数から乱数を生成しているので、process関数が鍵になってくる。

process関数は $GF(2^{256})$ の元で $tmp^2$ を返しているだけ。なお生成多項式はP。また、すべての演算は $GF(2)$ 上で行われるのでxorと+は等価。

これを数式で表すと、

$process(m,k) = p(m) + p(k) = m^2 + k^2$

ただし $p(x) = process(x,0)$ とする。

これを利用して与えられた暗号文を変形していく。ただし、fake_secretからkey2,3は既に計算済みとする。

$ctxt1 = true\_secret + key1$

$key2 = process(key1,seed) = key1^2 + seed^2$

$key3 = process(key2,seed) = key2^2 + seed^2$

$p(key2) + key3 = key2^2 + key2^2 + seed^2 = seed^2$

$key2 + seed^2 = key1^2 + seed^2 + seed^2 = key1^2$

$p(ctxt1) + key1^2 = true\_secret^2 + key1^2 + key1^2 = true\_secret1^2$

したがって、あとは $true\_secret1^2$ の平方根をとればよい。

一般に $GF(2^n)$ の元で平方根をとるには、n-1回平方をとればよい。

flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

oneTimePadは最初見たときに数学系の問題かな〜と思いつつxorこねくり回したり1bitずつ求めようとしたりして時間を浪費したのがもったいなかった。さらに、平方根とるだけって気づいてからn-1回平方すればいいことを知るまでに無駄に時間を使った。

ので、この2問は瞬殺できるぐらいにはなりたい。ただ無駄に苦戦したおかげでoneTimePad解けたときはうれしかった（こなみ）。

oneTimePad2も解きたかったけど式がより複雑になってて断念しました。

今回はほぼソロ参加みたいな状況でpwnが手付かずで残ってたのに1問も解けてないので精進💪