SECCON 2013 CTFオンライン予選のWriteup 7問

SECCON CTFには去年の奈良予選から数回参戦しているのですが、あれやこれやと理由をつけてWriteupを放棄していたので流石にまずいと思いはてなを始めました。Writeupどころかブログ自体初めてのことなので読みにくいところなどあると思いますが、是非ご指摘よろしくお願いします。

 

解いた問題は以下のとおりです。

フォレンジック

  • ここはどこ?

 

プログラミング/Crypt

  • calculate it / 計算せよ
  • Cryptanalysis
  • Tic Tac Logic

 

ネットワーク Web

  • FindTheKey
  • hidden message

 

その他

  • Encode me

 

以下、解答を載せていきます。

フォレンジックス 100 ここはどこ?

 問題文にファイル[Forensicist.dat]が添付されていたので、まずは解析。

$ file Forensicist.dat

Forensicist.dat: RFC 822 mail, ASCII text, with CRLF line terminators, with escape sequences

 Forensicist.datはメールらしいのでファイル名をForensicist.emlにリネームしてメーラーで開く。

f:id:qzm4u:20140127195927p:plain

 

添付ファイルのpandaを保存。ファイル形式はtiff

$ file panda

panda: TIFF image data, little-endian

 

画像を開いてもパンダの画像でしかないので一旦詰まる。

メール内にある「答: ◯◯◯◯◯◯ ◯◯◯」から答えが◯◯◯◯◯◯ Zooではないかと当たりをつけて、Google画像検索を使うが空振り。

EXIFに答えがあるのではと思い画像のプロパティを開くとGPS情報が残っていた

 Taipei zoo(台湾市民動物園)と入力しても正解にならなかったが、公式から「惜しい解答も正解にした」とのアナウンスをうけ再度入力。点数を獲得しました。

Taipei zoo

 

プログラミング/Crypt 100 calculate it / 計算せよ

  •  問題文

nc calculateit.quals.seccon.jp 45105

 問題文のサーバにアクセスすると、以下の様な数式(?)が毎回ランダムに出てきていた。

(このサーバは現在1/27まだ稼働中でした。)

72X1/54713/3-2-3-24 = 

これは単なる数式ではないのだが、数式として解答を続けていて、かなり時間を無駄にしました。

後からヒントが4つ出てきました。

Hint1: 四則演算ではありません

Hint2: 81 9- 16 6- 4/ 15 X  3- 72 45  = 82

Hint3: G- G- G- G- G- G- G- G- G- G- = 0

Hint4: X  X  X  X  X  X  X  X  X  XXX = 300

 チームメイトが「これボウリングのスコアじゃね?」と教えてくれたので、そのままボウリングのスコアを求めるコード書き。

何回問題に答えたらフラグが出るかなどわからなかったことが多かったので、かなり適当に組んでます。絶対に異常終了する上、フラグも表示できないので、パケットキャプチャと組み合わせて利用しました。

 require 'socket'

@total = 0

@max = 0

def calScore(slow)

  score =

  bonus = 0

  slows = 0

  slow.each do |c|

    if c == "X" then

    slows = slows + 2

    else

    slows = slows + 1

    end

  end

 

  if slows > 20 then

    if slow[-2] == "/"

      last = slow[-1].to_i

      last = 10 if slow[-1] == "X"

      score = [slow[-3].to_i, 10-slow[-3].to_i, last]

    elsif slow[-1] == "/"

      score = [10, slow[-2].to_i, 10-slow[-2].to_i]

    else

    -3.upto(-1) do |i|

        if slow[i] =~ /[0-9]/ then

          score = score+[slow[i].to_i]

        elsif slow[i] == "X" then

          score = score+[10]

        end

      end

    end

  slow = slow[0..-4]

  else

    score = [slow[-2].to_i,slow[-1].to_i]

  slow = slow[0..-3]

  end

 

  9.times do

    if slow[-1] == "X" then

      bonus = bonus +score[0]+score[1]

      score = [10] + score

    slow = slow[0..-2]

    elsif slow[-1] == "/"  then

      bonus = bonus +score[0]

      score = [slow[-2].to_i, 10-slow[-2].to_i] + score

    slow = slow[0..-3]

    else

      score = [slow[-2].to_i, slow[-1].to_i] + score

    slow = slow[0..-3]

    end

  end

  return score.inject(){|sum, n| sum+n}+bonus

end

 

TCPSocket.open("calculateit.quals.seccon.jp", 45105) do |s|

  while true do

    line = ""

    until (c = s.readchar()) == "=" do line = line+c end

    print line[0..-2]+" ="+s.readchar

    if line =~ /The total score/ then

      print @total.to_s+"\n"

      s.puts @total.to_s"\n"

    elsif line =~ /The hi score/ then

      print @max.to_s+"\n"

      s.puts @max.to_s+"\n"

    else

      ans = calScore(line[0..-2].gsub(/[-G]/,"0").split(""))

      @total = @total + ans

      @max = ans if @max < ans

      print ans.to_s+"\n"

      s.puts ans.to_s+"\n"

    end

  end

end

何十問かボウリングのスコアを求めさせる問題が出てきた後、最後に

The total score = 11953

The hi score = 300

なんて引っ掛けを食らってニヤッとしましたが、すぐにコードを修正して回答。

Good!!

FLAG: Bowling is very fun!!

と出てきたので、入力すると正解でした。

Bowling is very fun!!

回答時間が短かったので手入力では回答できなかったと思います。

プログラミング/Crypt 300 Cryptanalysis

  • 問題文

Enjoy!

問題文に画像が一枚添付されていました。

f:id:qzm4u:20140127213558p:plain 

この画像が示しているのは、楕円曲線暗号の数式です。(楕円曲線暗号 - Wikipedia)

問題を見る限りでは楕円曲線 y^2 = x^3 +  1234577x + 3213242上の有理点plainのx,y座標の和がフラグになるようです。既知情報からplainを求めるために数式を変形すると以下の様な数式が得られます。

plain = -rand()*PublicKey  (1)

この*は整数の乗算ではなく楕円曲線上有理点のスカラー倍算ということに注意してください。 

ここで問題となるのはrand()が具体的にどんなスカラー値か?ということですが、これはECDLPといって楕円曲線暗号の安全性の根拠になる問題で数学的に困難であることが証明されています。(とはいえ、この場合はmodの値が小さすぎるので、簡単に解けてしまいますが…)

というわけで、さっさとECDLPを攻撃して、plainを求めるプログラムをコーディング。

Mod = 7654319

A = 1234577

B = 3213242

 

Base = [5234568,2287747,false]

Pub = [2366653,1424308,false]

Crypt = [[5081741,6744615,false],[610619,6218,false]]

 

def inv(a)

  return power(a,Mod-2)

end

 

def add(a,b)

  return [a[0],a[1],false] if b[2] == true

  return [b[0],b[1],false] if a[2] == true

  return [0,0,true] if a[0] == b[0] && a[1] == Mod-b[1]

  return dbl(a) if a[0] == b[0] && a[1] == b[1]

  ret = [0,0,false]

  d = (a[1]+(Mod-b[1]))*inv(a[0]+(Mod-b[0]))

  ret[0] = ((d*d) +(Mod- a[0])+(Mod- b[0]))%Mod

  ret[1] = (d*(a[0]+(Mod-ret[0]))+(Mod-a[1]))%Mod

  return ret

end

 

def dbl(a)

  return [0,0,true] if a[2] == true || a[2] == 0

  ret = [0,0,false]

  d = (((a[0]*a[0])*3+A)*inv(a[1]*2))%Mod

  ret[0] = (d*d + (Mod - a[0])*2)%Mod

  ret[1] = (d*(a[0]+(Mod-ret[0]))+(Mod-a[1]))%Mod

  return ret

end

 

def power(a,e)

  ans = 1

  tmp = a

  until e <= 0 do

  if e % 2 == 1 then

    ans = (ans*tmp)%Mod

  end

  tmp = (tmp*tmp)%Mod

  e = e/2

  end 

  return ans

end

 

def scm(a, e)

  ans = [0,0,true]

  tmp = a

  until e <= 0 do

  if e % 2 == 1 then

    ans = add(ans, tmp)

  end

  tmp = dbl(tmp)

  e = e/2

  end 

  return ans

end

 

rand = 0

puts "Base = "+Base.to_s

puts "Crypt = "+Crypt[0].to_s

tmp = dbl(Base)

 

puts "Solving ECDLP"

2.upto(2*Mod) do |i|

  puts i if i%300000 == 0

  #ECDLPの総当り法による解答 rand()*Base = Crypt[0] よりrandを導出

  if tmp[0] == Crypt[0][0] && tmp[1] == Crypt[0][1] then

    rand = i #Rand = 2002115

    puts "Solved!!!"

    puts "Rand = " + i.to_s

    break

  end

  tmp = add(tmp, Base)

end

 

 

tmp = scm(Pub, rand) #rand()*PublicKey

tmp[1] = Mod- tmp[1]# - rand()*PublicKey

puts "-rand()*PublicKey = "+tmp.to_s

tmp = add(Crypt[1], tmp) #plain + rand()*PublicKey - rand()*PublicKey

puts "Plain =  "+tmp.to_s

 

puts "Flag = "+(tmp[0]+tmp[1]).to_s

 ECDLPの攻撃は単純に総当り法で行っています。ちなみに、今のところ効率的に多くのECDLPを攻撃できる方法としてはPollardのrho法が有名です。(http://www.academia.edu/2105476/Proposed_Development_for_Solving_ECDL)

 

というわけで、フラグは以下のとおりです。

5720914

プログラミング/Crypt 400 Tic Tac Logic

  •  問題文

133.242.18.173:12321 

例のごとくtelnetで該当サーバにアクセスしてみました。文字コードが特殊で一旦文字化けしましたが、Puttyの設定でUTF-8をターミナル文字コードに指定したら正常に見えました。

ルール:
タテヨコ同じ数の○と×が入るように○と×をインプットしていくパズルです。
○と×は2つまで連続してインプットできますが3つ連続してはいけません。
又、同じ行のパターン、または同じ列のパターンがあってはいけません。

サンプル
Question 0 [6,6]
.o.xxo
x..oox
.xoo.x
o..xxo
xo....
oxx.o.

次のように回答してください
xooxxo
xoxoox
oxooxx
oxoxxo
xoxxoo
oxxoox

それでは、スタート!

Question 1 [6,6]
......
..o...
...x.o
..x...
x....x
..x.o.

Too slow

私は知らなかったんですが、チクタクロジックというのは世界的に有名なパズルだったそうです。とりあえず、答えさえ分かればいいようだったので、例のごとく回答を送るプログラムをコーディング。

require 'socket'

 

@size = 6

@tab = ""

@rows =

@cols =

@rowNcNx =

@colNcNx =

 

def printTab

  open("answer.txt","w") do |file|

    @size.times do |i|

      puts @tab[i*@size, @size]

      file.puts @tab[i*@size, @size]

    end

  end

end

 

def getNextIndex(now)

  nextIndex = now

  until @tab[nextIndex] == "." || nextIndex >= @tab.length do

    nextIndex = nextIndex + 1

  end

  return nextIndex

end

 

def getNcNx

  @size.times do |i|

    return @rowNcNx[i][0..1] if @rowNcNx[i][2] == 0

    return @colNcNx[i][0..1]  if @colNcNx[i][2] == 0

  end

  return nil

end

 

def checkNcNx(ncnx)

  @size.times do |i|

    return false if ncnx != @rowNcNx[i][0..1] if  @rowNcNx[i][2] == 0

    return false if ncnx != @colNcNx[i][0..1] if @colNcNx[i][2] == 0

  end

  return true

end

 

def valid(index)

  return false if checkNcNx(getNcNx) == false

 

  (@size-1).times do |i|

    next if @rowNcNx[i][2] != 0

    (i+1).upto(@size-1) do |j|

      return false if @cols[i] == @cols[j] && @colNcNx[j][2] == 0

    end

  end

 

  (@size-1).times do |i|

    next if @rowNcNx[i][2] != 0

    (i+1).upto(@size-1) do |j|

      return false if @rows[i] == @rows[j]  && @rowNcNx[j][2] == 0

    end

  end

 

  row = index/@size

  col = index%@size

 

  min = col -2

  min = 0 if min < 0

  tmpR = @rows[row][min, 5]

  #puts tmpR

  min = row -2

  min = 0 if min < 0

  tmpC = @cols[col][min, 5]

  #puts tmpC

 

  lastC = "."

  count = 0

  tmpR.each_char do |c|

    if c == lastC && c != "." then

    count = count + 1

    return false if count >= 2

    else

    count = 0

    lastC = c

    end

  end

  lastC = "."

  count = 0

  tmpC.each_char do |c|

    if c == lastC && c != "." then

    count = count + 1

    return false if count >= 2

    else

    count = 0

    lastC = c

    end

  end

  return true

end

 

def solve(i)

  #puts "i = "+i.to_s

  if i >= @tab.length then

  #printTab()

  return true

  end

  nextIndex = getNextIndex(i+1) 

  @rowNcNx[i/@size][2] = @rowNcNx[i/@size][2]-1

  @colNcNx[i%@size][2] = @colNcNx[i%@size][2]-1

 

  @tab[i] = "o"

  @rows[i/@size][i%@size] = "o"

  @cols[i%@size][i/@size] = "o"

  @rowNcNx[i/@size][0] = @rowNcNx[i/@size][0]+1

  @colNcNx[i%@size][0] = @colNcNx[i%@size][0]+1

  if valid(i) == true then

    #puts i.to_s+" <- m"

    return true if solve(nextIndex)  == true

  end

  @rowNcNx[i/@size][0] = @rowNcNx[i/@size][0]-1

  @colNcNx[i%@size][0] = @colNcNx[i%@size][0]-1

 

  @tab[i] = "x"

  @rows[i/@size][i%@size] = "x"

  @cols[i%@size][i/@size] = "x"

  @rowNcNx[i/@size][1] = @rowNcNx[i/@size][1]+1

  @colNcNx[i%@size][1] = @colNcNx[i%@size][1]+1

  if valid(i)  == true then

    return true if solve(nextIndex)  == true

  end

  @rowNcNx[i/@size][1] = @rowNcNx[i/@size][1]-1

  @colNcNx[i%@size][1] = @colNcNx[i%@size][1]-1

  @tab[i] = "."

  @rows[i/@size][i%@size] = "."

  @cols[i%@size][i/@size] = "."

  @rowNcNx[i/@size][2] = @rowNcNx[i/@size][2]+1

  @colNcNx[i%@size][2] = @colNcNx[i%@size][2]+1

  #printTab

  return false

end

 

def init

  @rows =

  @cols =

  @rowNcNx =

  @colNcNx = []

  @size.times do |i|

    row = @tab[@size*i,@size]

    col = ""

    @size.times do |j|

      col = col + @tab[i+@size*j]

    end

    @rows.push row

    @cols.push col

    @rowNcNx.push [row.count("o"),row.count("x"),row.count(".")]

    @colNcNx.push [col.count("o"),col.count("x"),col.count(".")]

  end

end

 

TCPSocket.open("133.242.18.173", 12321) do |s|

  readQuestionFlag = false

  readLines = 0

  s.each_line do |line|

    line.encode!("UTF-8","UTF-8",:universal_newline => true)

    puts line

    break if line =~ /スタート/

  end

 

  while true do

    s.each_line do |line|

      line.encode!("UTF-8","UTF-8",:universal_newline => true)

      puts line

      if line =~ /^Question/ then

        #line =~ /,[0-9]{0..}\]$/

        @size = line[-3].to_i

        puts "SIZE = "+@size.to_s

      break

      end

    end

 

    @tab = ""

    @size.times do |i|

      line = s.gets

      line.encode!("UTF-8","UTF-8",:universal_newline => true)

      puts line

      @tab = @tab+line.chomp

    end

    init

    puts "SOLVE START"

    solve(getNextIndex(0))

    puts "SOLVE END"

 

    @size.times do |i|

      puts @tab[i*@size, @size]

      s.puts @tab[i*@size, @size].encode("ASCII-8BIT","UTF-8")

    end

    puts "ANS TRANSMITTED"

  end

end

 本番では20連続でパズルを正しく解く必要があったのですが、結構回答時間が短く(しかも、10~20問は8x8に問題のサイズが大きくなります)高速化のために2回ぐらい手を入れました書き直しました。上のプログラムはかなり遅い方なのでフラグを取るまでに何回かチャレンジしました。

20問正しく回答を送ると以下の様な表示がでました。

Congratulation!!
Flag is 10982341089327510896

というわけで、以下がフラグです。

10982341089327510896

 

ネットワーク・Web 200 Find the key!

問題文に以下のようなファイルが添付されていました。

seccon_q1_pcap.pcap

とりあえず、pcapはWiresharkで開きます。

f:id:qzm4u:20140127222630p:plain

一見したところping中のパケットをキャプチャしているようにみえますが、よく見るとLengthが異常に長いパケットが複数個含まれていることに気が付きます。パケットのデータ部をパッと見てみるとPNGという文字が見えますが、これはPNG画像形式のヘッダの一部です。

というわけで、データ部をバイナリエディタに投入したのち、不要な部分をカットして保存し開きますと、中途半端に下2/3以上が真っ黒な画像が出てきます。後はそこから連続するパケット(画像で言うと70に対して71以降のパケット)のデータ部からPNGのデータ部を取り出して付け足して保存して開きます。

 

f:id:qzm4u:20140127224449p:plain

 deadbeeffeedbad

フラグを作った人はゾンビか何かなんですかね?

ネットワーク・Web 300 Hidden Message?

問題文に以下のような画像が添付されていました。

f:id:qzm4u:20140127224644j:plain

やる夫ですかお?

 

とりあえず、これもネットワーク問題なのでこれで終わりというわけはないでしょう。というわけで、バイナリエディタで開いてバイナリを見ます。するとバイナリが本来締められているはずのjpgの終了コードの後にいくらかバイナリが続いていることが確認できます。

該当部分を抜き出して別のファイルとして保存したのち、fileコマンドでファイル形式を判定するとパケットキャプチャファイルという判定が得られたので、Wiresharkで開きます。

f:id:qzm4u:20140127225108p:plain

 

非常にシンプルなDNSリクエストパケットのキャプチャです。送信先アドレスがグローバルアドレスなので、こちらからもnslookupコマンドを使って情報を同じクエリを投げてみました。

$ nslookup

 

> server 133.242.55.252

既定のサーバー:  [133.242.55.252]

Address:  133.242.55.252

 

> 10.95.133.134

サーバー:  [133.242.55.252]

Address:  133.242.55.252

 

名前:    You.G0t.a.H1dd3n.m3ss4g3.1n.Th15.DNS

 

Address:  10.95.133.134

このドメイン名がフラグです。

You.G0t.a.H1dd3n.m3ss4g3.1n.Th15.DNS.

ドメイン名には最後にピリオドをつけるのをお忘れなく!

その他 200 Encode me.

問題文にファイルが添付されていました。encode_me_91

 encode_meというぐらいなので、base64なりなんなりのエンコーディングを施せばフラグが得られるということなのでしょうがファイルに91と名前がついているので91 エンコーディングでぐぐってみました。

するとbasE91というbase64の拡張のようなバイナリをASCIIテキストにエンコードするメソッドがあるようなので、コマンドをインストールしてファイルをエンコードしました。

$ base91 encode_me_91

PASSWORD/IS/WHICH+ENCODING+DO+YOU+LIKE

これがフラグです。

WHICH+ENCODING+DO+YOU+LIKE

 

来年度から大学出るんで同じチームで参戦することは難しくなると思うけど、これからもいろいろと勉強するトリガーになったり、上を見て絶望できるいい機会なのでCTFには参加し続けたいと思います。