newbieからバイナリアンへ

newbieからバイナリアンへ

人参の秘めたる甘さに気づいた大学生日記

【rev 1.0】 GlobalCecurityCamp2019 応募課題のwriteup - Reversing

 

 

 

 

【自動投稿 from 2019.11.27 to 2019.12.11.00:00】

本記事はTSG AdventCalender 2019のエントリとして書かれたものです

昨日(12/10)は iLiss さんによる「#sig-rhythm-game関連を1つ」でした

 

adventar.org

 

 

++++++++++++++++++++++++++

 

 

あどべんとかれんだぁを書くのは初めてで何を書けばいいのかわからないが

とりあえず予定のところに以下のように書いてしまった

 

f:id:smallkirby:20191127183341p:plain

 

 

 

というわけで

書いたものはしょうがないから上の予定のとおりに書き進めていく

 


 

 

 

 

 

 

 1: イントロ

今年の夏に一般社団法人セキュリティ・キャンプ協議会が主催したセキュリティキャンプ全国大会に参加した

その国際バージョンとしてGlobal Cecurity Camp:GCCが2020年2月に開催される

 

www.security-camp.or.jp

 

 

今年は東京で開催されることもあり参加が去年に比べて容易だし、何よりるくすさんのお話が聞けるチャンスのため参加しようと思ったが

この時期は大学の期末試験があったりとバタバタしていそうなのと

英語が全然できないため今回は参加を見送った

 

だが課題自体は面白そうだったため

提出こそしないものの自分で解いてみた

 

本記事は第三問目のReversingの問題のwriteupである

 

なお課題の提出期限は2019.12.9であり

本記事はその締切を待って予約投稿されている

ホームページを血眼で探したところ、writeupの公開を禁止する文言はどこにもなかったためこれを公開している

(締め切り前の公開を禁止している文言さえもなかったが、そこは常識的に考えた)

 

 

 

2: 問題概要

 VMGCCという名前でバイナリが渡される

バイナリの情報は以下の通り

./vmgcc: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for GNU/Linux 3.2.0, BuildID[sha1]=a19ce603ee59c9b2e72581a2441a47b2b1b8a831, stripped
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX disabled
    PIE:      PIE enabled
    RWX:      Has RWX segments
    FORTIFY:  Enabled

(別にpwnをするわけではないからセキュリティ機構とかどうでもいいといえばいいのだけれども。。。)

 

 

 

動かすと、flagの入力を求められる

 

f:id:smallkirby:20191128013101p:plain

welcome banner

 

Enter the flag: ABCDEFGHIKLMNOPQ
r0: 44434241  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 00000000  
r0: 44434241  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 41424344  
r0: 44434241  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 40424240  
r0: 41404044  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 40424240  
r0: 01020204  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 40424240  
r0: 01020204  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 45464748  
r0: 01020204  r1: 48474645  r2: 4d4c4b49  r3: 51504f4e  r4: 40464640  
r0: 01020204  r1: 41044748  r2: 4d4c4b49  r3: 51504f4e  r4: 40464640  
r0: 01020204  r1: 01420108  r2: 4d4c4b49  r3: 51504f4e  r4: 40464640  
r0: 01020204  r1: 01420108  r2: 4d4c4b49  r3: 51504f4e  r4: 494a4b4c  
r0: 01020204  r1: 01420108  r2: 4d4c4b49  r3: 51504f4e  r4: 49484b48  
r0: 01020204  r1: 01420108  r2: 494a404c  r3: 51504f4e  r4: 49484b48  
r0: 01020204  r1: 01420108  r2: 00020b04  r3: 51504f4e  r4: 49484b48  
r0: 01020204  r1: 01420108  r2: 00020b04  r3: 51504f4e  r4: 4d4e4f50  
r0: 01020204  r1: 01420108  r2: 00020b04  r3: 51504f4e  r4: 41404f40  
r0: 01020204  r1: 01420108  r2: 00020b04  r3: 4d424340  r4: 41404f40  
r0: 01020204  r1: 01420108  r2: 00020b04  r3: 0c020c00  r4: 41404f40  
r0: 01020204  r1: 01420108  r2: 0c000704  r3: 0c020c00  r4: 41404f40  
r0: 01020204  r1: 0d42060c  r2: 0c000704  r3: 0c020c00  r4: 41404f40  
r0: 0c400408  r1: 0d42060c  r2: 0c000704  r3: 0c020c00  r4: 41404f40  
Failed. Hint: https://www.youtube.com/watch?v=ZUXP9ZbPv9s

 

見るからに32bitレジスタと思わしきr0~r3に入力値が入れられ

いくつかの演算ののちに"Failed"と表示されhintとなるyoutubeのリンクが提供される

(このリンクにも飛んでみたが、1時間超えの動画だったこともありまだ見ていない

大学の試験終わったら見てみようかな)

 

ということで正しい入力値を探すことを目的としてバイナリを読んでいく

 (入力が16byteに限られているため脳死でangrに投げてやろうと思ったが、課題の内容自体にディスアセンブラを書くことが含まれていたためちゃんと解析した)

 

 

 

 

3: VMの構造

 このバイナリ自体はおそらくC++で書かれている気がする

ファイル名が示すとおり、内部で独自レジスタや独自命令を実装したVMになっている

以下ではそれらの仕組みを明らかにしていき、pythonエミュレータを構築することを目標にする

 

 

独自レジスタについて

使用される独自レジスタは以下の通り(命名は適当)

r0~r3レジスタ

32bit型のレジスタ。主に値の保持が目的となる。最初の入力値もここに代入される

r4レジスタ

32bit型のレジスタ。殆どr0~r3と差異はないが、作業用に頻繁に利用されており、また最初の入力値はここには代入されない

textレジスタ

後述する独自命令コードを指し示すポインタが格納される。最初に初期化された後はプログラム中で変更されることはない

pcレジスタ

次に実行する命令のtextレジスタからのオフセットを示す

 

これらは単にバイナリ中で変数として定義されている

 

 

 

 

独自命令

flagの判定を行う関数の直前でmemcpy()によって、newした 領域に命令バイトコードがコピーされ

そのアドレスをtextレジスタが保持する

命令は入力値に応じて動的に生成されるのかと思っていたが、どんな入力値に対しても一定であった

 

さて、text領域が保持する独自命令コードはは以下が全てである

(改行は見やすいように入れている)

pwndbg> x/100bx 0x5555557696f0
0x5555557696f0:	0x1a	0x04	0x44	0x43	0x42	0x41	
		0x0a	0x04    0x00	
		0x1a	0x00	0x44	0x40	0x40	0x41	
		0x0b    0x00	0x04	
		0x1a	0x04	0x48	0x47	0x46	0x45
0x555555769708:	0x0a	0x04	0x01	
		0x1a	0x01	0x48	0x47	0x04	0x41	
		0x0b	0x01	0x04	
		0x1a	0x04	0x4c	0x4b	0x4a	0x49	
		0x0a	0x04	0x02	
		0x1a	0x02	0x4c	0x40	0x4a	0x49	
		0x0b	0x02	0x04	
		0x1a	0x04	0x50	0x4f	0x4e	0x4d	
		0x0a	0x04	0x03	
		0x1a	0x03	0x40	0x43	0x42	0x4d	
		0x0b	0x03	0x04
0x555555769738:	0x0b	0x02	0x03	
		0x0b	0x01	0x02	
		0x0b	0x00	0x01	
		0xff	0x00	0x00

 

登場するオペコードは4種類であり、それぞれ異なるサイズのオペランドを取るCISC的な命令セットになっている

(懸念材料として、バイナリ中では5つのオペコードの処理を定義していたのだが、生成される命令列にはそのうちの一つが現れていなかった

 

以下では各種命令の説明を行う

0x1a 命令: copy immediate value

0a <代入先rレジスタのindex> <代入する即値4byte>

指定したrレジスタに4byteの即値を代入する命令

オペコード・ランド含めて6byteあるため実行後にpcを6インクリする

 

0x0a 命令: and

0a <andの相手兼代入先rレジスタのindex> <and元のrレジスタのindex>

2つのrレジスタ論理積をとって代入する

pcを3インクリする

 

0x0b 命令: xor

0b <xorの相手兼代入先rレジスタのindex> <xor元のrレジスタのindex>

2つのrレジスタ排他的論理和をとって代入する

pcを3インクリする

 

0x1b 命令: レジスタ代入

命令バイト中には現れていない

 

0xff 命令: authentication

シングルバイト命令

r0レジスタが32bitとも0であればr0レジスタに1を代入する

 

 

以上の命令はauth()関数の中で実行される

その周辺のデコンパイルコードは以下の通り

        init(l392_regs._0_24_,l392_regs.unk_addr);
        memcpy(l392_regs.unk_addr[0],3020a0_inst_ptr,3020a8_inst_bytenum);
        uVar3 = auth(&l392_regs,l128_inp);
        if ((char)uVar3 == '\0') {
            puts("Failed. Hint: https://www.youtube.com/watch?v=ZUXP9ZbPv9s");
        }
        else {
            puts("Success! You made it!");
        }

 

つまりauth()が1を返せば認証成功である

すなわち0xff命令の直前にr0レジスタが0になっていればよいということがわかった

 

 

 

 

 

4: エミュレータ

以上を踏まえてpythonで実装したこのVMエミュレータが以下である

 

# interpreter.py
#!/usr/bin/env python                                                                       
# -*- coding: utf-8 -*-
    
text = [
0x1a,0x04,0x44,0x43,0x42,0x41,
0x0a,0x4,0x0,
0x1a,0x0,0x44,0x40,0x40,0x41,
0x0b,0x00,0x04,
0x1a,0x04,0x48,0x47,0x46,0x45,
0xa,0x4,0x1,
0x1a,0x01,0x48,0x47,0x04,0x41,
0x0b,0x1,0x4,
0x1a,0x04,0x4c,0x4b,0x4a,0x49,
0x0a,0x4,0x2,
0x1a,0x02,0x4c,0x40,0x4a,0x49,
0xb,0x02,0x04,
0x1a,0x04,0x50,0x4f,0x4e,0x4d,
0xa,0x4,0x3,
0x1a,0x03,0x40,0x43,0x42,0x4d,
0xb,0x3,0x4,
0xb,0x2,0x3,
0xb,0x1,0x2,
0xb,0x0,0x1,
0xff]
counter = 0

def si(regs):
  global counter
  inst = text[counter]
  
  if inst==0x1a:
    rix = text[counter+1]
    a = ""
    for j in range(4):
      a += hex(text[counter+2 + (3-j)])[2:].rjust(2,'0')
    regs[rix] = int(a,16)
    
    counter += 6
    return regs

  if inst==0x0a:
    rdix = text[counter+1]
    rsix = text[counter+2]
    regs[rdix] = regs[rdix]&regs[rsix]

    counter += 3
    return regs

  if inst==0xb:
    rdix = text[counter+1]
    rsix = text[counter+2]
    regs[rdix] = regs[rdix]^regs[rsix]

    counter += 3
    return regs

  if inst==0xff:
    if regs[0]==0:
      return 1
    else:
      return 0

  print("inst "+hex(inst)+" is not implemented")
  return -1


def print_allregs(regs):
  for i in range(5):
    print("r"+str(i)+": "+hex(regs[i])[2:].rjust(8,"0"),end=" ")
  print()


print("input> ",end="")
inp = input()
regs = [0,0,0,0,0]
for i in range(4):
  if len(inp)<4:
    print("too few input")
    exit()
  a = ""
  for j in range(4):
    a += hex(ord(inp[3-j]))[2:]
  regs[i] = int(a,16)
  inp = inp[4:]



print_allregs(regs)
while True:
  a = si(regs)
  if type(regs)==type(a):
    print_allregs(regs)
  else:
    if(a==1):
      print("SUCCESS!!!")
      exit()
    else:
      print("FAIL")
      exit()



実際にフラグを流してみると以下のようになる

$ python3 ./interpreter.py 
input> ABCDEFGHIKLMNOPQ
r0: 44434241 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 00000000 
r0: 44434241 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 41424344 
r0: 44434241 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 40424240 
r0: 41404044 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 40424240 
r0: 01020204 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 40424240 
r0: 01020204 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 45464748 
r0: 01020204 r1: 48474645 r2: 4d4c4b49 r3: 51504f4e r4: 40464640 
r0: 01020204 r1: 41044748 r2: 4d4c4b49 r3: 51504f4e r4: 40464640 
r0: 01020204 r1: 01420108 r2: 4d4c4b49 r3: 51504f4e r4: 40464640 
r0: 01020204 r1: 01420108 r2: 4d4c4b49 r3: 51504f4e r4: 494a4b4c 
r0: 01020204 r1: 01420108 r2: 4d4c4b49 r3: 51504f4e r4: 49484b48 
r0: 01020204 r1: 01420108 r2: 494a404c r3: 51504f4e r4: 49484b48 
r0: 01020204 r1: 01420108 r2: 00020b04 r3: 51504f4e r4: 49484b48 
r0: 01020204 r1: 01420108 r2: 00020b04 r3: 51504f4e r4: 4d4e4f50 
r0: 01020204 r1: 01420108 r2: 00020b04 r3: 51504f4e r4: 41404f40 
r0: 01020204 r1: 01420108 r2: 00020b04 r3: 4d424340 r4: 41404f40 
r0: 01020204 r1: 01420108 r2: 00020b04 r3: 0c020c00 r4: 41404f40 
r0: 01020204 r1: 01420108 r2: 0c000704 r3: 0c020c00 r4: 41404f40 
r0: 01020204 r1: 0d42060c r2: 0c000704 r3: 0c020c00 r4: 41404f40 
r0: 0c400408 r1: 0d42060c r2: 0c000704 r3: 0c020c00 r4: 41404f40 
FAIL



もとのVMと全く同じ挙動をしていることがわかる

 


 

 

5: solverを考える

式を簡単にする

さて、入力値を求めることに話を戻そう

まず与えられた命令列を立式すると以下のようになる

r0=0x41404044^(inp0&inp0_rev)
r0=0x41404044^(0x41424344&inp0)
r1=0x41044748^(0x45464748&inp1)
r2=0x494a404c^(0x494a4b4c&inp2)
r3=0x4d424340^(0x4d4e4f50&inp3)
r0==(r1^r2^r3)

 

最後の式に全て代入すると以下のようになる

0x41404044^(0x41424344&inp0) == 450C4444^(0x41044748^(0x45464748&inp1) ^ 0x494a404c^(0x494a4b4c&inp2) ^ 0x4d424340^(0x4d4e4f50&inp3))

 

ここで排他的論理和には交換則が成り立つことを用いると以下のようになる

(0x41424344&inp0) == 044C0400^(0x45464748&inp1)^(0x494a4b4c&inp2)^(0x4d4e4f50&inp3)



結局はこの条件式を満たすinp0~inp3を考えるというつまらない問題に帰着した




solverの方針

以上を満たすsolverを考える

残っているのは全てbit演算であり、他のbitに対して何も影響しないため難しい話ではない

 

まずinp0は全て0xFFFFFFFFとしておき

inp1~inp3で条件式を満たすようなものがあるか考える

これで条件を満たすようなものがない場合にはinp0で調整していくこととする

 

inp0=0xFFFFFFFFと仮定したため、上の式は以下のようになる

0x450E4744 == (0x45464748&inp1)^(0x494a4b4c&inp2)^(0x4d4e4f50&inp3)

 

以下では右辺inpと論理積を取っている即値のことをim1~3と呼ぶ

右辺では入力値との論理積をとっていることから、bitを降ろすことは容易にできる

それからひとつの immediate value ^ inp においてとあるbitが立っていれば、他の項の対応するbitを降ろせば、三項の排他的論理和はONになる

 

よって、左辺の1つ1つのbitに対して

・bitが0なら、対応するinp1~3のbitを0にする

・bitが1なら、対応するinp1~3のbitの中で1のものをinp1から順に探していき、見つかったらそのimを1、他のimを0にする

という操作をしていけば良いことがわかる

 

但し左辺で立っているbitに対して、imd1~3のいずれも立っていない場合もあり得るため

その際にはinp0を調整していく必要がある

 

 

 

 

6: solver

以上の考えに基づいてpythonで書いたsolverが以下の通り

 

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def rb(imd):
  return bin(imd)[2:].rjust(32,'0')

def pb(imd):
  print(rb(imd))

def hoge(n,m):
  a = ""
  b = ""
  ns = bin(n)[2:].rjust(32,'0')
  ms = bin(m)[2:].rjust(32,'0')
  for i in range(32):
    if ms[i]=='1' and ns[i]=='0':
      a += "1"
    else:
      a += "0"

    if ms[i]=='0' and ns[i]=='1':
      b += "0"
    else:
      b += "1"
  return int(a,2),int(b,2)


iml = 0x41424344
imr = 0x044c0400
imls = rb(iml)
imrs = rb(imr)
im = [0x45464748,0x494a4b4c,0x4d4e4f50]
ims = ["","",""]
for i in range(3):
  ims[i] = rb(im[i])
inp = [0xffffffff,0,0,0]
inps = ["","","",""]
for i in range(4):
  inps[i] = rb(inp[i])

imt = iml^imr
imts = rb(imt)
print("imts",imts)

for i in range(32):
  found = False
  if imts[i]=='0':
    for j in range(3):
      inps[j+1] = inps[j+1][:i]+'0'+inps[j+1][i+1:]
  else:
    for j in range(3):
      if ims[j][i]=='1': #該当するinpのbitだけをonにして他の2つをoffに
        found = True
        for k in range(3):
          if k==j:
            inps[k+1] = inps[k+1][:i]+'1'+inps[k+1][i+1:]
          else:
            inps[k+1] = inps[k+1][:i]+'0'+inps[k+1][i+1:]
        break
    if found==False:
      print("Not found: "+hex(i))
      exit()


print(inps)

#check
for i in range(3):
  inp[i+1] = int(inps[i+1],2)
print(inp)
if iml&int(inps[0],2) == imr ^ (im[0]&inp[1]) ^ (im[1]&inp[2]) ^ (im[2]&inp[3]):
  print("OK!!!!!!!")
else:
  print("fail")

 

 

実際に動かすと以下のようになる

$ python3 ./bool_solver.py 
inputs in bin
['11111111111111111111111111111111', '01000101000001100100011101000000', '00000000000010000000000000000100', '00000000000000000000000000000000']
inputs in dec
[4294967295, 1158039360, 524292, 0]
OK!!!!!!!






7: VMにflagを食わせる

さて、以上で条件を満たすであろう入力値を求められた

ただ懸念材料として、この入力は当然ASCIIコード範囲に収まっていない

flagと言うくらいだからASCII表示できるやつが正解だと思うのだが。。。

まぁ上のソルバを少しいじればASCII内に収まるやつを見つけることもできるし

なにより、VMが正解といえばそれが正解だ

 

というわけで表示不能文字を入力する必要があり

以下のいつもpwnで使うスクリプトでflagを食わせた

 

# exploit.py
#!/usr/bin/env python
#encoding: utf-8;

from pwn import *
import sys

FILENAME = "vmgcc"

rhp2 = {'host':"localhost",'port':30000}
context(os='linux',arch='amd64')
binf = ELF(FILENAME)

def exploit(conn):
  inps = ['11111111111111111111111111111111', '01000101000001100100011101000000', '00000000000010000000000000000100', '00000000000000000000000000000000']

  inp = [0,0,0,0]
  for i in range(4):
    inp[i] = int(inps[i],2)

  inj = ""
  for i in range(4):
    inj += p32(inp[i])
  conn.recvuntil("flag: ")
  conn.sendline(inj)
  


if len(sys.argv)>1:
  if sys.argv[1][0]=="d":
    cmd = """
      set follow-fork-mode parent
    """
    conn = gdb.debug(FILENAME,cmd)
  elif sys.argv[1][0]=="r":
    conn = remote(rhp1["host"],rhp1["port"])
else:
    conn = remote(rhp2['host'],rhp2['port'])
exploit(conn)
conn.interactive()




実際に動かすとこのようになる

r0: ffffffff  r1: 45064740  r2: 00080004  r3: 00000000  r4: 00000000  
r0: ffffffff  r1: 45064740  r2: 00080004  r3: 00000000  r4: 41424344  
r0: ffffffff  r1: 45064740  r2: 00080004  r3: 00000000  r4: 41424344  
r0: 41404044  r1: 45064740  r2: 00080004  r3: 00000000  r4: 41424344  
r0: 00020300  r1: 45064740  r2: 00080004  r3: 00000000  r4: 41424344  
r0: 00020300  r1: 45064740  r2: 00080004  r3: 00000000  r4: 45464748  
r0: 00020300  r1: 45064740  r2: 00080004  r3: 00000000  r4: 45064740  
r0: 00020300  r1: 41044748  r2: 00080004  r3: 00000000  r4: 45064740  
r0: 00020300  r1: 04020008  r2: 00080004  r3: 00000000  r4: 45064740  
r0: 00020300  r1: 04020008  r2: 00080004  r3: 00000000  r4: 494a4b4c  
r0: 00020300  r1: 04020008  r2: 00080004  r3: 00000000  r4: 00080004  
r0: 00020300  r1: 04020008  r2: 494a404c  r3: 00000000  r4: 00080004  
r0: 00020300  r1: 04020008  r2: 49424048  r3: 00000000  r4: 00080004  
r0: 00020300  r1: 04020008  r2: 49424048  r3: 00000000  r4: 4d4e4f50  
r0: 00020300  r1: 04020008  r2: 49424048  r3: 00000000  r4: 00000000  
r0: 00020300  r1: 04020008  r2: 49424048  r3: 4d424340  r4: 00000000  
r0: 00020300  r1: 04020008  r2: 49424048  r3: 4d424340  r4: 00000000  
r0: 00020300  r1: 04020008  r2: 04000308  r3: 4d424340  r4: 00000000  
r0: 00020300  r1: 00020300  r2: 04000308  r3: 4d424340  r4: 00000000  
r0: 00000000  r1: 00020300  r2: 04000308  r3: 4d424340  r4: 00000000  
Success! You made it!

 

 

はい、できた!!!

 






8: アウトロ

Revの問題を解くのはほぼ初めてであり、コードも少し読み慣れなかった

結果として試験前の2日間3時間の計6時間を費やしてしまった

別にangrに投げても良かったかなぁ

 

VMの内部構造を明らかにしていく過程はとても面白かった

ただ、そのあとの単なるソルバを書くところはつまらなかった

 

来年はGCC出れるといいなぁ。。。

 

 

 ++++++++++++++++++++++++++++++

 

 

明日のTSGアドベントカレンダー

hakatashiさんによる「 TSG LIVE! を支える技術 その2 ~tsg-live-controller~」の予定です

 

 

 

 

 

9: 発狂して空き缶を4個食べて翼を生やしネコになる予定

 うわああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああいいいいいいい。

げろげろげろげろげろげろげろげろげろげろくえっくえっくえっくえっぽんぽんこつこんぽんぽんこつこつけろけろぐえっ

 うわああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああいいいいいいい。

げろげろげろげろげろげろげろげろげろげろくえっくえっくえっくえっぽんぽんこつこんぽんぽんこつこつけろけろぐえっ

 

 

バリバリッ

バリバリッバリバリッ

むしゃむしゃ

バリむしゃっ

バリバリむしゃっむしゃっ

 

 

 

ばさっ

 

 

 

 

 

 

にゃ〜〜〜〜〜〜〜〜ん

 

 






続く