いろいろ試したもののうまくいかなかった問題。Easyとは...(m0rphしか解けなかった人の顔
CTFtime.orgにwrite-upが上がっていたので参考にしつつリベンジしてみた。とてもくわしく書かれているがややこしいので、理解するために日本語に訳しているだけみたいなところがありアレ。
https://blog.rpis.ec/2017/12/34c3ctf-vim.html
Vimコマンドを読む
問題のファイル(上記URL参照)には、4行目にFLAGを入力しろと書かれている。
GY@"
というコマンドは
G
最終行に飛び
Y
行全体をヤンクして(バッファにためて)
@"
ヤンクした内容をコマンドとして実行する
という意味。
そこで最終行を見てみる。最終行周辺はよく見るとVimのコマンドになっている(気づくのにとても時間がかかった)。
わかりやすいようにコマンド単位に分割したのが以下。
6G (6行目行頭へ)
f2 "ayl (レジスタa = '2')
^ f0 "cyl "Ayl (レジスタc = '0', レジスタa += '0')
^ fh "Ayl (レジスタa += 'h')
^ fj "Ayl (レジスタa += 'j')
^ fG "gyl (レジスタg = 'G')
^ fk "Gyl (レジスタg += 'k')
G $ FY "Gy3l (レジスタg += 'Y@"')
$ F@ "hyl (レジスタh = '@')
Fh "Hyl (レジスタh += 'h')
260G Y @" (260行目を実行)
F10H (実行されない)
いろいろ実行したあと260G Y @"
でジャンプしている。(<X>
<Y>
などはあとで説明に使います)
1G ff "dyl "eyl "fyl (レジスタd, e, f = 'f')
4G @c "Dyl (レジスタd += レジスタcが指すFLAGの文字<X>)
6G @d h j "Eyl j "Fyl (6行目から<X>を探し、レジスタe += その左下の文字<Y>, レジスタf += さらにその1行下の文字<Z>)
1G fl "Cyl (レジスタc += 'l')
6G f2 "byl F0 "Byl (レジスタb = '20')
261G Y @" (261行目を実行)
(3c043Bh4Hf5#)
261行目を見ると、
9G @e 19l @a "Byt. (9行目の文字<Y>にジャンプし、19文字右に移動、レジスタaを実行してカーソルから右に辿って'.'の直前までの文字列<P>をレジスタbに追記)
6G fj "Byl (レジスタb += 'j')
6G f2 "ayl F0 "Ayl (レジスタa = '20')
9G @f 19l @b "Ayt. (9行目の文字<Z>にジャンプし、19文字右に移動、レジスタbを実行して、カーソルから'.'直前までの文字列<Q>をレジスタaに追記)
6G fj "Ayl (レジスタa += 'j')
40| @a (適当に移動、またすぐ移動するので意味はない)
260G Y @" (260行目を実行)
(@1fBkya5B^)
あれ、これ無限ループでは…と思ったが、そうはならない。
自作のシミュレータに与えてみると、4行目に書いたFLAGの文字が終わるとエラーを出して終了した。末尾の()
で囲んだ部分は実行されない。
実行中のレジスタの中身を吐かせてみるとこのようになる。write-upではVim本体にパッチをあてて検証したらしい。
{"a"=>"20hj", "c"=>"0l", "g"=>"GkY@\"F", "h"=>"@h", "d"=>"f3", "e"=>"f,", "f"=>"fG", "b"=>"20h33j"}
...
{"a"=>"20h169j", "c"=>"0llllllllllllll", "g"=>"GkY@\"F", "h"=>"@h", "d"=>"ff", "e"=>"f2", "f"=>"f2", "b"=>"20l72j"}
...
{"a"=>"20h192j", "c"=>"0lllllllllllllllll", "g"=>"GkY@\"F", "h"=>"@h", "d"=>"f", "e"=>"f", "f"=>"f", "b"=>"20l78j"}
これと260・261行目からわかる内容をまとめると、
@a
@b
を実行するとたくさん移動する
- 4行目で実行される
@c
には、l
がどんどん後ろに連なっていくので、4行目のFLAGの文字を順番にフォーカスしている
@d
@e
@f
は @c
に応じて変化
@h
は自分を呼び出す(そして全体を通じてレジスタの中身が変化しない)
@g
は下から2番目の行を実行する(そして全体を通じてレジスタの中身が変化しない)
このあと処理を逐次追ってみたけど頭が爆発しそうになったので諦めて本番はここで終わり。
依存関係を図にしてみたりした。ちょっとはわかりやすい…?
@b
が決定したあとに@a
が決定され、@a
は次のループに引き継がれるので、1回のループで「与えられた@aとFLAGの文字をもとに、新たな@aを生成する」と考えることができる。
ループの仕組み
次に@a
@b
の動きを理解したい。
まず、FLAGから文字を取り出して6行目で検索し<X>
が決定する。
逆の言い方をすれば、FLAGで使われる文字列はすべて6行目にある。
<X>
によって <Y>
<Z>
が確定するが、そのもととなる7,8行目をよく見ると文字種が偏っている。
6 @Wk0KVmQ3rFpgcZy.C8eY7b_sBSETUvwiM5LPzuNofhn6Ox1G942jdaXlDRtHqJAI6HntUkUZmdU".i"
7 @,hhGGl,"_Gl@l,l2"""@l,2G_22h_@2Glh2"@@,2__G2@hGh,l_l_"hGh,_,""@H1"jDA"h"53AA6.d -> <Y>
8 22l,2_lG,@l_,,@Ghl"2h"l@@h,_@l_lG2h"h@l,2,"hGGG,"_hG@2@2"_"_h_G""@Bd@#$BEj_GG5,B -> <Z>
6行目で、重複しているために<X>
にならない文字を省く(fG
というようにアクセスされるので、同じ文字が2つあると右側にあるものにはたどり着かないことに注意)。
それによって<Y>
<Z>
も絞られるので省くと、以下のようになる。
6 @Wk0KVmQ3rFpgcZy.C8eY7b_sBSETUvwiM5LPzuNofhn6Ox1G942jdaXlDRtHqJAI "
7 @,hhGGl,"_Gl@l,l2"""@l,2G_22h_@2Glh2"@@,2__G2@hGh,l_l_"hGh,_,""@ A -> <Y>
8 22l,2_lG,@l_,,@Ghl"2h"l@@h,_@l_lG2h"h@l,2,"hGGG,"_hG@2@2"_"_h_G" G -> <Z>
このように見ていくと、<Y>
<Z>
になる文字は@ , h G A l " _ 2
だけだとわかる。
そして、<Y>
<Z>
は9行目でのジャンプにのみ使われている。ここも <Y>
<Z>
からアクセスされない部分は省いてしまう。
9 ._3d93@jA_F"H.#0GB8#c,5d#9lAaakh18ck2eGDcHlG7A21Cg8"C$3$e$"D@l.E^A6eDlbec5$D".hl
9 _ @ A " G , l h 2
また、9行目にジャンプしてからは19文字右に移動したあと @a
@b
のいずれかが実行される。
ここで、@a
@b
は20h...
20l...
から始まることに注目すると、最終的な<Y>
<Z>
からの横方向の移動距離は+19 ± 20 = -1 or +39の2つだけ。
移動先の候補に*
で印をつけてみると、10行目以降のl
やh
に縦方向で揃う(下画像赤色部分)。
A
の移動先の候補はズレているが、7行目に遡ると1度しか出てきていないのでおそらくダミー。排除して考える。
加えて、h
l
の前にある文字もただのパディングとわかる。
そのあとは@a
@b
の続きで赤色の列を下に移動し<P>
<Q>
として追記したあとはじめへ戻る。
ここで、l250.
h129.
といった <P>
<Q>
の候補は 16 * 250 = 4000個ある。
この4000個を行ったり来たりして後述する@g
に飛ばすようなFLAGを見つける。
狙う場所
write-upには@g
に注目したと書いてある。vimを開いて1行目で指示されるコマンドを打った後、@g
を実行するとwin!
と出た。
なるほどそういうことか。
1 Enter the flag in line 4 and type GY@"
2
3 The flag is:
4 34C3_example
5 --------------------------------------------------------------------------------
6 win!
そして@g
を実行している箇所は108行目行頭だけなので、ココに飛ばせばよいということになる。
108 @g.ABh175.l220.l245.l159.h61.7h45.^h122.h23.2l176.l86.9l146.h5.EGl143.l168.h222.
Exploit
@g
にたどり着くようなFLAGを探すにはどうすればいいんだろう? @g
から逆順にたどるのもキツそう。
write-upではBFS(幅優先探索)なbrute forceで解いたようなのでそれを真似してみる。
このように、@a
(初期値は20hj
)とFLAG文字列全体を持つようにすると経路復元の必要がなくなりラク。
また、同じ@a
を得た場合は枝の探索を断ち切って計算量を削減する。
vimcommand.rb
は開催中に自分で書いていたシミュレータ。
require_relative './vimcommand'
FLAG_CHARS = "34C_W0KVmQrFpgcZy8eY7bsBSETUvwiM5LPzuNofhn6Ox1G92jdaXlDRtHqJAI".chars
State = Struct.new :a, :flag
PROBLEM = File.read("vim.txt").split "\n"
visited = {}
queue = [State.new("20hj", "")]
def step_loop state, newchar
vc = VimCommand.new PROBLEM, '260GY@"'
vc.registers["a"] = state.a
vc.registers["d"] = 'f' + newchar
vc.registers["e"] = 'f'
vc.registers["f"] = 'f'
vc.lines[260] = %Q(6G@dhj"Eylj"Fyl6Gf2"bylF0"Byl261GY@")
vc.lines[261] = %Q(9G@e19l@a"Byt.6Gfj"Byl6Gf2"aylF0"Ayl9G@f19l@b"Ayt.6Gfj"Ayl40|@a)
vc.call do |sc|
end
State.new vc.registers["a"], state.flag + newchar
end
until queue.empty?
cur = queue.pop
FLAG_CHARS.each do |ch|
puts cur.flag + ch
nxt = step_loop cur, ch
unless visited[nxt.a]
queue << nxt
visited[nxt.a] = true
end
end
end
require 'strscan'
class VimCommand
attr_reader :lines, :focus_line, :focus_char, :stack, :registers
def initialize lines, init_cmd
@lines = ['', lines].flatten
@focus_line = 0
@focus_char = 0
@stack = [init_cmd || @lines[0]]
@registers = {}
end
def call &block
while @stack.any?
execute &block
end
end
def execute &block
return if @stack.empty?
@sc = StringScanner.new @stack.pop
until @sc.eos?
break if step &block
end
end
def step
sc = @sc
break_loop = false
case
when sc.scan(/(\^|0)/)
@focus_char = 0
when sc.scan(/\$/)
@focus_char = fli.size - 1
when sc.scan(/(\d+)h/)
@focus_char -= sc[1].to_i
when sc.scan(/(\d+)j/)
@focus_line += sc[1].to_i
when sc.scan(/(\d+)k/)
@focus_line -= sc[1].to_i
when sc.scan(/(\d+)l/)
@focus_char += sc[1].to_i
when sc.scan(/h/)
@focus_char -= 1
when sc.scan(/j/)
@focus_line += 1
when sc.scan(/k/)
@focus_line -= 1
when sc.scan(/l/)
@focus_char += 1
when sc.scan(/G/)
@focus_line = @lines.size - 1
when sc.scan(/(\d+)G/)
@focus_line = sc[1].to_i
@focus_char = 0
when sc.scan(/(\d+)B/)
@focus_line -= sc[1].to_i - 1
@focus_line -= 1 if @focus_char == 0
when sc.scan(/(\d+)\|/)
@focus_char = sc[1].to_i - 1
when sc.scan(/Y@"/)
@stack.push sc.string[sc.charpos..-1]
@stack.push fli
break_loop = true
when sc.scan(/@(.)/)
@stack.push sc.string[sc.charpos..-1]
@stack.push @registers[sc[1]]
break_loop = true
when sc.scan(/f(.)/)
@focus_char = fli.index sc[1], @focus_char
when sc.scan(/F(.)/)
@focus_char = fli.rindex sc[1], @focus_char
when sc.scan(/"([A-Z])yl/)
@registers[sc[1].downcase] += fch
when sc.scan(/"([A-Z])y(\d+)l/)
@registers[sc[1].downcase] += fli[@focus_char..@focus_char + sc[2].to_i]
@focus_char += sc[2].to_i - 1
when sc.scan(/"([A-Z])yt(.)/)
@registers[sc[1].downcase] += fli[@focus_char...fli.index(sc[2], @focus_char)]
when sc.scan(/"([a-z])yl/)
@registers[sc[1]] = fch
else
raise "Parse Error: #{sc.charpos} #{sc.string[sc.charpos..-1]}"
end
yield sc if block_given?
break_loop
end
def fli
@lines[@focus_line]
end
def fch
fli[@focus_char]
end
end
これを実行すると、数秒でFLAGを探索しエラーを出して止まる(乱暴)。前に見た通り@g
を実行すると内容が書き換えられるため。
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cs4
がFLAG。
34C3_MgOSwZm9WFTRKYvCXFXXxpX9ct
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cH
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cq
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cJ
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cA
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cI
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cs3
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cs4
/home/sei0o/ctf/34c3ctf/vim/vimcommand.rb:86:in `step': Parse Error: 0 20@gj (RuntimeError)
from /home/sei0o/ctf/34c3ctf/vim/vimcommand.rb:25:in `execute'
from /home/sei0o/ctf/34c3ctf/vim/vimcommand.rb:16:in `call'
from exploit.rb:21:in `step_loop'
from exploit.rb:32:in `block in <main>'
from exploit.rb:30:in `each'
from exploit.rb:30:in `<main>'
おもしろいけど、誰がこんな問題思いつくんだろうか...少しずつ理解してたら記事にするまで1ヶ月ぐらい経ってしまった(白目
アルゴリズム力も足りないなあ…