更新日時で差をつけろ

もはや更新日時でしか差を付けられない

34C3 CTF 「vim」のwrite-upを見た

いろいろ試したもののうまくいかなかった問題。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 @b20h... 20l... から始まることに注目すると、最終的な<Y> <Z> からの横方向の移動距離は+19 ± 20 = -1 or +39の2つだけ。
移動先の候補に*で印をつけてみると、10行目以降のlh縦方向で揃う(下画像赤色部分)。

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 # 6行目より(k, @, .といった制御文字は取り除く)
State = Struct.new :a, :flag
 
PROBLEM = File.read("vim.txt").split "\n"
 
visited = {} # それぞれの@aを生成する最短のFLAG
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@") # @c, @dへの代入を削除
  vc.lines[261] = %Q(9G@e19l@a"Byt.6Gfj"Byl6Gf2"aylF0"Ayl9G@f19l@b"Ayt.6Gfj"Ayl40|@a) # 261行目から260行目に戻らないようにする
 
  vc.call do |sc|
    # puts "#{sc[0]} #{vc.focus_line} #{vc.focus_char} #{vc.registers['b']}"
  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ヶ月ぐらい経ってしまった(白目
アルゴリズム力も足りないなあ…