[CODEGATE 2019] KingMaker writeup

Index

• Summary

• Analysis

• Payload

Summary

• code obfuscation(xor)

• code patch

• find path

Analysis

m444ndu@ubuntu:~/codegate2019/king$ checksec KingMaker 
[*] '/home/m444ndu/codegate2019/king/KingMaker'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

보안기법을 살펴보았지만, 퍼너블 문제라기보단 그냥 리버싱 문제에 가까운 것 같아 딱히 도움이 되지는 않습니당.

</br>

m444ndu@ubuntu:~/codegate2019/king$ ./KingMaker 
  _  ___             __  __       _             
 | |/ (_)_ __   __ _|  \/  | __ _| | _____ _ __ 
 | ' /| | '_ \ / _` | |\/| |/ _` | |/ / _ \ '__|
 | . \| | | | | (_| | |  | | (_| |   <  __/ |   
 |_|\_\_|_| |_|\__, |_|  |_|\__,_|_|\_\___|_|   
               |___/                            
​
Once upon a time, there was a kingdom with 7 princes.
One day the king thinks to decide the who will be the next king.
So he made 5 tests for the princes.
If you pass all the tests, you can be a king!
​
**********************KING MAKER START**********************
​
...
.....
.......
Who am I...??
1> Ask to someone
2> Look around
​

대충 문제 파일을 살펴보면, 사용자는 위와 같이 각각의 선택지에 따라 게임을 진행하게 됩니다. 선택지에 따라 군주의 덕목인 brave, wise, kind, decision, sacrifice 평가가 달라지며, 최종적으로 모두 5가 되면 플래그를 얻을 수 있습니다. 약간 미연시(??) 느낌입니다.

</br>

최종점의 코드는 다음과 같습니다.

void __fastcall __noreturn final(const char *a1, __int64 a2)
{
  puts(a1);
  if ( (_DWORD)a2 == 1 )
  {
    if ( brave != 5 || wise != 5 || kind != 5 || decision != 5 || sacrifice != 5 )
    {
      print("King : But you couldn't make the points... You can't be a king.", a2);
    }
    else
    {
      print("King : Congratuations to be a king!", a2);
      system("/bin/cat ./flag");
    }
  }
  exit(-1);
}

</br>

하지만 문제는 바이너리가 실행되는 코드 부분 중 대부분이 xor 연산으로 난독화가 되어있다는 점입니다. 아래와 같이 각각의 키들로 xor 연산을 하여 코드를 되돌리고, 실행을 하는 구조로 되어있습니다.

v2 = (unsigned int)dword_6070A8;
xor(start_1, dword_6070A8, &v3);
start_1(&v3, v2);

키 비교는 다음의 함수를 통하여 진행합니다. 총 key1, key2, key3, key4, key5를 열어 비교합니다.

_BOOL8 __fastcall key_check(const char *a1, unsigned int a2, unsigned int a3)
{
  FILE *stream; // ST18_8
  int n; // ST00_4
  char s; // [rsp+20h] [rbp-30h]
  char s1; // [rsp+30h] [rbp-20h]
  unsigned __int64 v8; // [rsp+48h] [rbp-8h]
​
  v8 = __readfsqword(0x28u);
  sprintf(&s, "key%d", a2, __PAIR__(a2, a3));
  stream = fopen(&s, "r");
  fgets(&s1, n, stream);
  return strncmp(&s1, a1, n) == 0;
}

본 문제를 해결하기 위해서는 숨겨진 키들을 찾아내고, 능력치가 모두 5가 될 수 있는 루트를 찾아내야 합니다. 키는 xor 연산한 결과가 결국 함수를 만들어내는 것이므로 함수 프롤로그 부분을 참고하면 찾아낼 수 있습니다.

before
pwndbg> x/10i 0x4019f2
   0x4019f2:    adc    edi,DWORD PTR [rax-0x4]
   0x4019f5:    mov    bh,0x1b
   0x4019f7:    mov    al,0x8d
   0x4019f9:    jae    0x401a73
   0x4019fb:    out    0x3b,eax
   0x4019fd:    fcom   DWORD PTR [rcx]
   0x4019ff:    sbb    bl,al
   0x401a01:    (bad)  
   0x401a02:    rex.R jnp 0x401a35
   0x401a05:    outs   dx,BYTE PTR ds:[rsi]
​
after
pwndbg> x/10i 0x004019F2
   0x4019f2:    push   rbp
   0x4019f3:    mov    rbp,rsp
   0x4019f6:    sub    rsp,0x20
   0x4019fa:    mov    QWORD PTR [rbp-0x18],rdi
   0x4019fe:    mov    rax,QWORD PTR fs:0x28
   0x401a07:    mov    QWORD PTR [rbp-0x8],rax
...

이런식으로 예측하여 xor 연산을 진행하면, 다음과 같이 각각의 key들을 찾아낼 수 있습니다.

key1 = 'lOv3'
key2 = 'D0l1'
key3 = 'HuNgRYT1m3'
key4 = 'F0uRS3aS0n'
key5 = 'T1kT4kT0Kk'

사실 중간에 ALICEAWTQJMJXTSPPZVCIDGQYRDINMCP 이 문자열을 해독하라고 합니다. 이에 대한 check routine도 존재하여 이를 맞춰 주어야 해당 분기문을 넘어갈 수 있는데, 체크하는 함수를 보면 다음과 같습니다.

if ( (unsigned int)checkstring(&v2) )
  {
    xor(succ_4, dword_607114, a1);
    succ_4(0, 1LL, 1, 2, 0);
  }
...
​
signed __int64 __fastcall checkstring(const char *a1)
{
  int v2; // [rsp+18h] [rbp-78h]
  signed int i; // [rsp+1Ch] [rbp-74h]
  char dest[16]; // [rsp+20h] [rbp-70h]
  char v5[26]; // [rsp+30h] [rbp-60h]
  char v6[26]; // [rsp+50h] [rbp-40h]
  char v7; // [rsp+72h] [rbp-1Eh]
  unsigned __int64 v8; // [rsp+78h] [rbp-18h]
​
  v8 = __readfsqword(0x28u);
  qmemcpy(v5, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", sizeof(v5));
  strcpy(v6, "ALICEAWTQJMJXTSPPZVCIDGQYRDINMCP");
  v7 = 0;
  v2 = 0;
  strncpy(dest, a1, 5uLL);
  for ( i = 5; i < strlen(a1); ++i )
  {
    if ( v5[(a1[i] - 'A' + dest[v2] - 'A') % 26] != v6[i] )
      return 0LL;
    v2 = (v2 + 1) % 5;
  }
  return 1LL;
}

for 문을 통해 틀릴 시 0을 리턴하며 바이너리를 종료시키는 구조입니다. for 문이 핵심으로 동작하여 입력된 문자열을 비교합니다. 헌데, 입력된 문자열의 길이가 애초에 5보다 작으면 비교루틴이 동작하지 않습니다. 이를통해 해당 루틴을 쉽게 우회할 수 있습니다.

patch_king.py

#!/usr/bin/python
​
data = ''
key = ['lOv3','D0l1','HuNgRYT1m3','F0uRS3aS0n','T1kT4kT0Kk']
chunk = []
​
chunk.append([0x40341d, key[0], 0xf0])
chunk.append([0x40330f, key[0], 0xf0])
chunk.append([0x4033ff, key[0], 0x1e])
chunk.append([0x4032c0, key[0], 0x1e])
chunk.append([0x4032de, key[0], 0x31])
chunk.append([0x403197, key[0], 0x129])
chunk.append([0x4030d4, key[0], 0xc3])
​
chunk.append([0x402d55, key[1], 0xfa])
chunk.append([0x402c25, key[1], 0x112])
chunk.append([0x402d37, key[1], 0x1e])
chunk.append([0x4027e9, key[1], 0x44])
chunk.append([0x4029b9, key[1], 0xe6])
chunk.append([0x402b2b, key[1], 0xfa])
chunk.append([0x40271c, key[1], 0xcd])
chunk.append([0x4028b5, key[1], 0xe6])
chunk.append([0x40299b, key[1], 0x1e])
chunk.append([0x402a9f, key[1], 0x4e])
chunk.append([0x402aed, key[1], 0x3e])
​
chunk.append([0x40282d, key[1], 0x44])
chunk.append([0x402871, key[1], 0x44])
​
chunk.append([0x4020e2, key[2], 0x18d])
chunk.append([0x40201f, key[2], 0xc3])
​
chunk.append([0x401b0a, key[3], 0xf0])
chunk.append([0x4019f2, key[3], 0xfa])
chunk.append([0x401aec, key[3], 0x1e])
chunk.append([0x40192c, key[3], 0xa8])
chunk.append([0x4019d4, key[3], 0x1e])
chunk.append([0x4016d0, key[3], 0xc3])
​
chunk.append([0x4011bb, key[4], 0x131])
chunk.append([0x400f25, key[4], 0xdc])
chunk.append([0x40108b, key[4], 0x130])
chunk.append([0x401001, key[4], 0x1e])
chunk.append([0x40101f, key[4], 0x4e])
chunk.append([0x40106d, key[4], 0x1e])
chunk.append([0x400c8c, key[4], 0x15b])
chunk.append([0x400de7, key[4], 0x120])
chunk.append([0x400f07, key[4], 0x1e])
# chunk.append([])
​
with open('./KingMaker','r') as f1:
    data = f1.read()
    data = bytearray(data)
​
for ad, k, size in chunk:
    length = len(k)
    for i in range(0, size):
        data[ad+i-0x400000] = data[ad+i-0x400000] ^ ord(k[i%length])
​
​
with open('./patched_king','w') as f2:
    f2.write(data)
​

find_routine.py

#!/usr/bin/python
​
a = [[2,0,0,1,0],[2,0,1,0,0],[2,0,2,1,0]]
b = [[0,0,1,0,2],[0,-1,0,0,-1],[0,2,0,0,0]]
c = [[-1,0,-1,1,0],[1,1,0,0,0],[1,2,0,0,0]]
d = [[1,1,0,2,0],[1,1,1,2,0],[1,1,1,1,2],[1,2,2,1,2]]
e = [[0,0,1,1,0],[0,-1,2,0,0],[0,-1,1,1,0]]
f = [[0,0,0,0,0],[1,0,0,0,1],[1,-1,-1,2,2]]
g = [0,1,1,2,0]
h = [[0,1,1,1,0],[0,1,0,0,0]]
i = [[-1,0,0,1,1],[0,0,1,2,1],[0,0,0,2,2]]
​
def summ(a, b, c, d, e, f, g, h, i):
    k = []
    for p in range(0,5):
        res = a[p] + b[p] + c[p] + d[p] + e[p] + f[p] + g[p] + h[p] + i[p]
        k.append(res)
    return k
​
for _a in range(0,3):
    for _b in range(0,3):
        for _c in range(0,3):
            for _d in range(0,4):
                for _e in range(0,3):
                    for _f in range(0,3):
                        for _h in range(0,2):
                            for _i in range(0,3):
                                if summ(a[_a],b[_b],c[_c],d[_d],e[_e],f[_f],g,h[_h],i[_i]) == [5,5,5,5,5]:
                                    print a[_a],b[_b],c[_c],d[_d],e[_e],f[_f],g,h[_h],i[_i]
​
print 'finish'

Payload

#!/usr/bin/python
from pwn import *
​
key = ['lOv3','D0l1','HuNgRYT1m3','F0uRS3aS0n','T1kT4kT0Kk']
​
r = process('./KingMaker')
#r = remote('110.10.147.104',13152)
context.log_level = 'debug'
#gdb.attach(r, 'b* 0x00040341d')
​
'''
[2, 0, 1, 0, 0] [0, 2, 0, 0, 0] [1, 1, 0, 0, 0] [1, 1, 1, 1, 2] 
[0, -1, 2, 0, 0] [1, 0, 0, 0, 1] [0, 1, 1, 2, 0] [0, 1, 0, 0, 0] [0, 0, 0, 2, 2]
'''
​
r.sendlineafter('2> Look around\n','1')
​
r.sendlineafter('Enter the key for test 1\n',key[0])
r.sendlineafter(' not\n','1')
r.sendlineafter('leg and helmet.\n','2')
r.sendlineafter('3> Just release\n','2') # [2, 0, 1, 0, 0]
r.sendlineafter('3> Read a book in the room.\n','3') # [0, 2, 0, 0, 0]
​
r.sendlineafter('Enter the key for test 2\n',key[1])
r.sendlineafter(' not\n','1')
r.sendlineafter('discuss about this.\n','2')
r.sendlineafter(' not.\n','1')
r.sendlineafter('really cleary.\n','1') # [1, 1, 0, 0, 0]
r.sendlineafter('2> Go to persuade the brother.\n','2')
r.sendlineafter('with you.\n','1') # [1, 1, 1, 1, 2] 
​
r.sendlineafter('Enter the key for test 3\n',key[2])
r.sendlineafter('send him into exile.\n','2') # [0, -1, 2, 0, 0] 
r.sendlineafter('2> Nope!\n','2')
r.sendlineafter('eat it first.\n','3') # [1, 0, 0, 0, 1]
​
r.sendlineafter('Enter the key for test 4\n',key[3])
r.sendlineafter(' not.\n','1')
r.sendlineafter("I can't\n",'1')
r.interactive()
r.sendlineafter('1 chance.\n','1') # [0, 1, 1, 2, 0]
r.sendlineafter('Just stay in room','2') # [0, 1, 0, 0, 0]
​
r.sendlineafter('Enter the key for test 5\n',key[4])
r.sendlineafter('the other country.\n','3')
r.sendlineafter('Go home together.\n','2') # [0, 0, 0, 2, 2]
​
r.sendlineafter('Enter the room.\n','2')
r.sendlineafter("I don't.\n",'1')
​
r.interactive()
​
#He_C@N'T_see_the_f0rest_foR_TH3_TRee$