vim
CTFtime.orgにwrite-upが上がっていたので参考にしつつリベンジしてみた。とてもくわしく書かれているがややこしいので、理解するために日本語に訳しているだけみたいなところがありアレ。
Vimコマンドを読む
問題のファイル（上記URL参照）には、４行目にFLAGを入力しろと書かれている。
GY@"というコマンドは
G 最終行に飛び
Y 行全体をヤンクして（バッファにためて）
@" ヤンクした内容をコマンドとして実行する
という意味。
そこで最終行を見てみる。最終行周辺はよく見るとVimのコマンドになっている（気づくのにとても時間がかかった）。
わかりやすいようにコマンド単位に分割したのが以下。
code:263
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>などはあとで説明に使います)
code:260
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行目を見ると、
code: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本体にパッチをあてて検証したらしい。
code:registers.rb
{"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は次のループに引き継がれるので、１回のループで「与えられた@aとFLAGの文字をもとに、新たな@aを生成する」と考えることができる。
https://gyazo.com/dd2d8ad6438b9a63221bbf810826b8f4
ループの仕組み
次に@a @bの動きを理解したい。
まず、FLAGから文字を取り出して6行目で検索し<X>が決定する。
逆の言い方をすれば、FLAGで使われる文字列はすべて6行目にある。
<X> によって <Y> <Z> が確定するが、そのもととなる7,8行目をよく見ると文字種が偏っている。
code:vim
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> も絞られるので省くと、以下のようになる。
code:vim
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> からアクセスされない部分は省いてしまう。
code:vim
9 ._3d93@jA_F"H.#0GB8#c,5d#9lAaakh18ck2eGDcHlG7A21Cg8"C$3$e$"D@l.E^A6eDlbec5$D".hl
9 _ @ A " G , l h 2
また、９行目にジャンプしてからは19文字右に移動したあと @a @b のいずれかが実行される。
ここで、@a @b は20h... 20l... から始まることに注目すると、最終的な<Y> <Z> からの横方向の移動距離は+19 ± 20 = -1 or +39の2つだけ。
移動先の候補に*で印をつけてみると、10行目以降のlやhに縦方向で揃う（下画像赤色部分）。
Aの移動先の候補はズレているが、7行目に遡ると１度しか出てきていないのでおそらくダミー。排除して考える。
加えて、h lの前にある文字もただのパディングとわかる。
https://gyazo.com/4ab3b084006209e83ebb3abcd6f819b6
そのあとは@a @b の続きで赤色の列を下に移動し<P> <Q> として追記したあとはじめへ戻る。
ここで、l250. h129. といった <P> <Q> の候補は 16 * 250 = 4000個ある。
この4000個を行ったり来たりして後述する@gに飛ばすようなFLAGを見つける。
狙う場所
write-upには@g に注目したと書いてある。vimを開いて1行目で指示されるコマンドを打った後、@gを実行するとwin!と出た。
なるほどそういうことか。
code:vim
1 Enter the flag in line 4 and type GY@"
2
3 The flag is:
4 34C3_example
5 --------------------------------------------------------------------------------
6 win!
そして@gを実行している箇所は108行目行頭だけなので、ココに飛ばせばよいということになる。
code:vim.txt
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を得た場合は枝の探索を断ち切って計算量を削減する。
https://gyazo.com/fda75385402a51b9d94df724f6bc20e1
vimcommand.rbは開催中に自分で書いていたシミュレータ。
code:exploit.rb
require_relative './vimcommand'
FLAG_CHARS = "34C_W0KVmQrFpgcZy8eY7bsBSETUvwiM5LPzuNofhn6Ox1G92jdaXlDRtHqJAI".chars # 6行目より（k, @, .といった制御文字は取り除く)
State = Struct.new :a, :flag
PROBLEM = File.read("vim.txt").split "\n"
visited = {} # それぞれの@aを生成する最短のFLAG
def step_loop state, newchar
vc = VimCommand.new PROBLEM, '260GY@"'
vc.registers"a" = state.a vc.registers"d" = 'f' + newchar vc.lines260 = %Q(6G@dhj"Eylj"Fyl6Gf2"bylF0"Byl261GY@") # @c, @dへの代入を削除 vc.lines261 = %Q(9G@e19l@a"Byt.6Gfj"Byl6Gf2"aylF0"Ayl9G@f19l@b"Ayt.6Gfj"Ayl40|@a) # 261行目から260行目に戻らないようにする 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
queue << nxt
end
end
end
code:vimcommand.rb
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 || @lines0] @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/)
when sc.scan(/(\d+)j/)
when sc.scan(/(\d+)k/)
when sc.scan(/(\d+)l/)
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_char = 0
when sc.scan(/(\d+)B/)
@focus_line -= sc1.to_i - 1 @focus_line -= 1 if @focus_char == 0
when sc.scan(/(\d+)\|/)
@focus_char = sc1.to_i - 1 when sc.scan(/Y@"/)
@stack.push fli
break_loop = true
when sc.scan(/@(.)/)
@stack.push @registers[sc1] break_loop = true
when sc.scan(/f(.)/)
@focus_char = fli.index sc1, @focus_char when sc.scan(/F(.)/)
@focus_char = fli.rindex sc1, @focus_char @registers[sc1.downcase] += fch when sc.scan(/"(A-Z)y(\d+)l/) @registers[sc1.downcase] += fli[@focus_char..@focus_char + sc2.to_i] @focus_char += sc2.to_i - 1 when sc.scan(/"(A-Z)yt(.)/) @registers[sc1.downcase] += fli[@focus_char...fli.index(sc2, @focus_char)] else
end
yield sc if block_given?
break_loop
end
def fli
end
def fch
end
end
これを実行すると、数秒でFLAGを探索しエラーを出して止まる（乱暴）。前に見た通り@gを実行すると内容が書き換えられるため。
34C3_MgOSwZm9WFTRKYvCXFXXxpX9cs4 がFLAG。
code:bash
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>'
おもしろいけど、誰がこんな問題思いつくんだろうか...少しずつ理解してたら記事にするまで１ヶ月ぐらい経ってしまった（白目
アルゴリズム力も足りないなあ…