読者です 読者をやめる 読者になる 読者になる

きゅうり。

主にCTF関係のことを書いていく気がします

0CTF 2017 writeup

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

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

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

 

integrity (crypto 75pt)

・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}

oneTimePad (crypto 114pt)

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問も解けてないので精進💪