ぶちのブログ

競プロとCTFが趣味なWebエンジニアのアウトプットの場

Seccon Beginners CTF 2019 write-up

はじめに

Beginners CTF 2019に出場し、2270点で32位でした。

f:id:betit0919:20190526165115p:plain f:id:betit0919:20190526165239p:plain

主に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はチームに誰も解ける人がいないので、最初からほぼ捨てていました。こちらも余裕があったら自分が担当していきたいです。