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にリネームしてメーラーで開く。
添付ファイルのpandaを保存。ファイル形式はtiff。
$ file panda
画像を開いてもパンダの画像でしかないので一旦詰まる。
メール内にある「答: ◯◯◯◯◯◯ ◯◯◯」から答えが◯◯◯◯◯◯ 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!
問題文に画像が一枚添付されていました。
この画像が示しているのは、楕円曲線暗号の数式です。(楕円曲線暗号 - 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!
問題文に以下のようなファイルが添付されていました。
とりあえず、pcapはWiresharkで開きます。
一見したところping中のパケットをキャプチャしているようにみえますが、よく見るとLengthが異常に長いパケットが複数個含まれていることに気が付きます。パケットのデータ部をパッと見てみるとPNGという文字が見えますが、これはPNG画像形式のヘッダの一部です。
というわけで、データ部をバイナリエディタに投入したのち、不要な部分をカットして保存し開きますと、中途半端に下2/3以上が真っ黒な画像が出てきます。後はそこから連続するパケット(画像で言うと70に対して71以降のパケット)のデータ部からPNGのデータ部を取り出して付け足して保存して開きます。
deadbeeffeedbad
フラグを作った人はゾンビか何かなんですかね?
ネットワーク・Web 300 Hidden Message?
問題文に以下のような画像が添付されていました。
やる夫ですかお?
とりあえず、これもネットワーク問題なのでこれで終わりというわけはないでしょう。というわけで、バイナリエディタで開いてバイナリを見ます。するとバイナリが本来締められているはずのjpgの終了コードの後にいくらかバイナリが続いていることが確認できます。
該当部分を抜き出して別のファイルとして保存したのち、fileコマンドでファイル形式を判定するとパケットキャプチャファイルという判定が得られたので、Wiresharkで開きます。
非常にシンプルな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には参加し続けたいと思います。