Seccon Beginners CTF 2019 write-up
はじめに
Beginners CTF 2019に出場し、2270点で32位でした。
主にweb問を担当し、自分が解いた問題はRamen, Katsudon, Sliding puzzle, BitFlipの4問で773点分でした。
以下各問題の振り返りをします。
解けた問題
Ramen
SQL injectionの問題
UNION SELECT null, table_name FROM INFORMATION_SCHEMA.COLUMNS; #
とすれば、テーブル名が判明。flagテーブルがあることがわかるので、
’UNION SELECT flag, 1 from flag #
でflagが出力される。
Katsudon
Base64でエンコードされたFlagが渡されるのでデコードするだけ。
Sliding puzzle
TCPサーバーに接続して問題を解くやつ。問題文は以下の通り。
スライドパズルを解いてください。すべてのパズルを解き終わったとき FLAG が表示されます。 スライドパズルは以下のように表示されます。 ---------------- | 0 | 2 | 3 | | 6 | 7 | 1 | | 8 | 4 | 5 | ---------------- 0 はブランクで動かすことが可能です。操作方法は以下のとおりです。 0 : 上 1 : 右 2 : 下 3 : 左 最終的に以下の形になるように操作してください。 ---------------- | 0 | 1 | 2 | | 3 | 4 | 5 | | 6 | 7 | 8 | ---------------- 操作手順は以下の形式で送信してください。
自分で実装するのは辛いので、gemを探す。こちらのgemが見つかったので使わせてもらう。
require './lib/sliding_puzzle/base.rb' require './lib/sliding_puzzle/oracle.rb' require 'socket' require 'json' require 'zlib' $sockin = TCPSocket.open("133.242.50.201","24912") $sockout = $sockin goal_state = SlidingPuzzle.new( [0, 1, 2], [3, 4, 5], [6, 7, 8], ) oracle = SlidingPuzzle.oracle(goal_state) move_mapper = {up: 2, right: 3, down: 0, left: 1} loop do response = $sockin.gets response2 = $sockin.gets response3 = $sockin.gets response4 = $sockin.gets response5 = $sockin.gets response6 = $sockin.gets start_state = SlidingPuzzle.new( response2.split("|")[1..3].map(&:to_i), response3.split("|")[1..3].map(&:to_i), response4.split("|")[1..3].map(&:to_i) ) ans = oracle.solve(start_state).map do |move| move_mapper[move] end $sockout.write("#{ans.join(',')}\n") end
ところでRubyでctfやる人少ないですよね、悲しい。
文字列操作がめっちゃ使いやすいので、こういう問題は非常に強いと思います！
BitFlip
平文の下位1/4bitのうちいずれか1bitがbitflipして、RSA暗号で暗号化された暗号文と、e, Nの値が与えられる。
e=3と非常に小さいが、平文が長いためLow Public Exponent Attackはできなかった。
2つの平文は、せいぜい2bitの差しかないので、Coppersmith's attackというものが使えそう。
調べると、こちらの記事に実装があったため、パラメータだけ変更して、Web上の実行環境で実行。
def short_pad_attack(c1, c2, e, n): PRxy.<x,y> = PolynomialRing(Zmod(n)) PRx.<xn> = PolynomialRing(Zmod(n)) PRZZ.<xz,yz> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (x+y)^e - c2 q1 = g1.change_ring(PRZZ) q2 = g2.change_ring(PRZZ) h = q2.resultant(q1) h = h.univariate_polynomial() h = h.change_ring(PRx).subs(y=xn) h = h.monic() kbits = n.nbits()//(2*e*e) diff = h.small_roots(X=2^kbits, beta=0.5)[0] # find root < 2^kbits with factor >= n^0.5 return diff def related_message_attack(c1, c2, diff, e, n): PRx.<x> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (x+diff)^e - c2 def gcd(g1, g2): while g2: g1, g2 = g2, g1 % g2 return g1.monic() return -gcd(g1, g2)[0] if __name__ == '__main__': n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331 e = 3 nbits = n.nbits() kbits = nbits//(2*e*e) print "upper %d bits (of %d bits) is same" % (nbits-kbits, nbits) c1 = 17064899494441977212945778822277102194860171782716080075116921978781725209255015259797432419355057358298782672107926674543506738681734060023808502046773189018615578241400253812426697228534365048518460871450026705380627127787726515448840930941656639083802204638137009428447037972953410618005481423180056328761 c2 = 33893222841569544976871226031983864631572239420135160076162607527334273371650057864337452438746273882876526128833452607084243001144677634648193276986049173372493292389392399425003019337406148751412276057861283195535860724056529276627862326221442439730175004422889331768541502470681387822497019333670888778582 diff = short_pad_attack(c1, c2, e, n) print "difference of two messages is %d" % diff m1 = related_message_attack(c1, c2, diff, e, n) print m1 print m1 + diff
c1,c2のフリップされる位置が、それぞれ下位1/9bit以内である必要があるため、何度か試行する必要があった。
得られた2つの平文のXorを取ったりして、BitFlip前の平文を得られる。
感想
とても楽しかったです。運営の方ありがとうございました！！！！
チームメンバーに助けられて良い順位でしたが、担当のweb問が2つしか解けなかったので、かなり実力不足を感じました。他の方のwrite-upを読んでいると、あと少しで解けた問題もあったなと感じるので、特にweb問題の経験値をためていこうと思います。
ちなみにpwnはチームに誰も解ける人がいないので、最初からほぼ捨てていました。こちらも余裕があったら自分が担当していきたいです。