RBTree's profile image

RBTree

August 19, 2019 23:59

Shellcoding and Bitflip Conjecture

shellcoding , ctf

서론

이번에 DEF CON CTF 2019에 팀 SeoulPlusBadass로 다녀왔습니다. 결과 링크

대회의 대부분의 문제가 프로그램의 취약점을 찾아서 익스플로잇하는 Pwnable 문제였는데, 그렇지 않은 문제는 ropship, DOOOM, bitflip conjecture 세 문제였습니다.

그 중에서도 Bitflip Conjecture는 흥미로운 Shellcoding 문제여서 이번에 공유하고자 합니다.

Bitflip Conjecture

Bitflip Conjecture는 X64 Assembly로 작성된 Binary를 전송하는 문제입니다. 자세한 것은 문제에 접속하면 나오는 메시지를 살펴봅시다:

===============================================================================

Definition:
  A snippet of assembly code is `N-Flip Resistant` if its output remains
  constant (i.e., it produces the same output and exits with the same
  return value) even if ANY combination of N bits are flipped. 

One-flip Conjecture:
  The x86 architecture is such that it is possible to write any arbitrary
  program (of any length) in a way that is 1-flip resistant. 
                                       - Balzaroth (Vegas 2019)

===============================================================================

It is now your turn to provide a proof for this Conjecture, which has puzzled 
hackers and security researchers for hundreds of years.
Provide a shellcode (max 200 bytes) that prints 'I am Invincible!' and
then terminates with exit code zero.

Points are assigned based on how close you are from a complete proof
(i.e., based on how many bit flip your code was able to withstand)

-------------------------------------------------------------------------------

But first, how do you want the registers initialized before executing the code?
 1. I like all my registers set to zero
 2. I want them pointing to the middle of a 64KB R/W region of memory)
 3. Dont bother. Leave them as they are

즉, 주어진 코드의 임의의 n-bit를 flip해도 원래 의도대로 돌아가는 코드를 n-flip resistant하다고 정의합니다. 그리구 문제에서는 'I am Invincible!'을 출력하는 1-flip resistant한 코드를 작성하는 것이 목표입니다.

실제 문제에서는 최대 200 bytes를 보냈을 때 모든 1 bit를 한 번 씩 flip해보고, 그 중 올바르게 작동하지 않은 경우의 수를 카운트해서 1000점에서 빼서 점수를 부여했습니다. 예를 들어, 1, 2, 3, 4번째 bit를 flip했더니 올바르게 작동하지 않았다면 1000 - 4 = 996점이 됩니다.

또한 바이너리를 읽어보면, seccomp를 통해 write, exit을 제외한 syscall을 막는 것을 알 수 있습니다.

  LODWORD(v5) = seccomp_init(0LL);
  v6 = v5;
  seccomp_rule_add(v5, 2147418112LL, 231LL, 0LL);
  seccomp_rule_add(v6, 2147418112LL, 60LL, 0LL);
  seccomp_rule_add(v6, 2147418112LL, 1LL, 0LL);
  seccomp_load(v6);
  v14 = atoi(argv[2])

X64 Assembly 코딩을 하기 위해서는 어셈블리에 대해서 잘 알고 있어야겠죠? 그리고 어셈블리로 쉽게 코딩할 수 있는 방법이 필요할 겁니다. 안타깝게도 어셈블리에 대해서 설명하는 것은 매우 시간이 오래 걸리기 때문에, 어셈블리 자체보다는 어떻게 하면 어셈블리를 CTF level에서 쉽게 코딩해보고, 어떻게 문제를 풀었는지에 초점을 맞추려고 합니다.

#Shellcoding

Shellcoding을 편하게 하는 방법은 여러 가지가 있을 수 있지만, 저는 Python의 pwntools 라이브러리를 사용하는 편입니다. pwntools에는 Shellcraft와 같은 Shellcoding 편의 기능이 있기 때문에, 익혀두면 좋을 것입니다.

우선, 'I am Invincible!'을 출력하는 어셈 코드를 작성해봅시다.

from pwn import *
context.arch = 'amd64'

base_code = """
    /* push 'I am Invincible!' */
    mov rax, 0x21656c6269636e69
    push rax
    mov rax, 0x766e49206d612049
    push rax
    /* write(fd=1, buf='rsp', n=16) */
    push 1
    pop rdi
    push 0x10
    pop rdx
    mov rsi, rsp
    /* call write() */
    push SYS_write /* 1 */
    pop rax
    syscall
    /* exit(status=0) */
    xor edi, edi /* 0 */
    /* call exit() */
    push SYS_exit /* 0x3c */
    pop rax
    syscall
"""

asm_code = asm(base_code)
print(disasm(asm_code))

with open('shellcode', 'wb') as f:
    f.write(asm_code)

Stack에 'I am Invincible!' 이라는 string을 push하고, write syscall을 통해서 이를 출력시킵니다. 그 뒤 exit syscall을 통해 프로그램을 종료시킵니다.

이를 주어진 바이너리에 넣고 실행해보면, 'I am Invincible!'을 정상적으로 출력하고 끝납니다.

##1-Flip Resistant 하게 만들기 위한 아이디어

이제 이 코드를 1-flip resistant하게 만들어야 합니다. 위의 메시지를 다시 살펴보시면, 문제에서 세 가지 옵션을 줬습니다.

But first, how do you want the registers initialized before executing the code?
 1. I like all my registers set to zero
 2. I want them pointing to the middle of a 64KB R/W region of memory)
 3. Dont bother. Leave them as they are

1번은 모든 레지스터를 0으로 세팅하고, 2번은 모든 레지스터를 mmap을 통해 할당한 R/W 영역의 위치로 세팅합니다. 3번은 우리가 전송한 shellcode를 실행하기 직전의 레지스터 상태를 그대로 들고 갑니다.

그런데 shellcode를 실행하기 직전의 상태를 보면 다음과 같습니다.

───────────────────────────────────────────────────────[ registers ]────
$rax   : 0x00007ffff7ff6000  →  0x9090909090909090
$rbx   : 0x0000000000000000
$rcx   : 0x0000000000000037
$rdx   : 0x00007ffff7ff6037  →  0xb848240cfe016a03
$rsp   : 0x00007fffffffe4f0  →  0x00007ffff7ffe168  →  0x0000555555554000  →   jg 0x555555554047
$rbp   : 0x00007fffffffe540  →  0x0000555555554db0  →  <__libc_csu_init+0> push r15
$rsi   : 0x0000000040000000
$rdi   : 0x00007fffffffe89d  →  0x2f3d4c4c45485300
$rip   : 0x0000555555554d99  →  <main+655> call rax
$r8    : 0x0000000000000000
$r9    : 0x1999999999999999
$r10   : 0x0000000000000000
$r11   : 0x00007ffff76345e0  →  0x0002000200020002
$r12   : 0x0000555555554a00  →  <_start+0> xor ebp, ebp
$r13   : 0x00007fffffffe620  →  0x0000000000000005
$r14   : 0x0000000000000000
$r15   : 0x0000000000000000
$eflags: [carry PARITY adjust zero sign trap INTERRUPT direction overflow resume virtualx86 identification]
$ds: 0x0000  $ss: 0x002b  $es: 0x0000  $fs: 0x0000  $cs: 0x0033  $gs: 0x0000

각 레지스터 값을 실제로 살펴보면, rax는 쉘코드의 시작 위치를 나타냅니다. 그리고 rcx는 몇 번째 바이트의 한 비트를 뒤집을지를 나타내고, stack memory를 살펴보거나 xmm0 레지스터를 살펴보면 그 중 몇 번째 비트를 flip하는 지도 저장되어 있습니다. rdxrax+rcx 값을 가리키고 있습니다.

즉, 우리의 shellcode가 실행될 때 레지스터와 메모리 값을 통해서 어느 비트가 flip 되었는 지를 알아낼 수 있고, 곧 3번 옵션을 선택하는 것이 매우 좋은 방법인 것 같습니다. 그렇다면 어떻게 이 문제를 풀어볼 수 있을까요?

1. Flip된 bit를 다시 flip하기

어디가 flip되었는지를 알고 있기 때문에, 다시 flip할 수 있습니다.

cvttsd2si eax, xmm0
xor [rdx], al

위의 assembly code를 사용하면, 다시 flip을 할 수 있게 됩니다. 하지만 해당 instruction은 6byte입니다. 만약 이 instruction 부분이 flip되면 정상적으로 돌려놓을 수 없을 것입니다. 실제로 이를 실행해봅시다. 실행 코드는 다음과 같습니다.

import os

res = os.popen('./test shellcode 3').read()
if res != 'I am Invincible!':
    print("BASIC VERIFICATION FAIL")

cnt = 0
for byt in range(200):
    for bit in range(8):
        res = os.popen('./test shellcode 3 {} {} 2>&1'.format(byt, bit)).read()
        if res == 'I am Invincible!':
            cnt += 1
        else:
            print(byt, bit)
            print(res)

print('Result: {} / {}'.format(cnt, 200 * 8))

우선 Basic verification을 통과하지 못합니다. 아무 bit도 flip하지 않은 경우에 대해서도 동작해야하는데 동작하지 않습니다. 그리고 Result: 1574 / 1600 라는 결과가 나왔습니다. 26개의 bit에서 resistant하지 않았습니다. 이것으로는 만점과는 거리가 있어보입니다.

2. Flip된 위치에 따라서 Branch code를 사용하기

정상적인 코드를 2개를 붙여놓아봅시다.

─────────────────────────────────────────────────
Printing 'I am Invincible!'
─────────────────────────────────────────────────
Printing 'I am Invincible!'
─────────────────────────────────────────────────

한 bit만 flip되기 때문에, 앞 코드가 비정상이 되거나 뒷 코드가 비정상이 되거나 둘 중 하나입니다. 만약 두 코드 중 정상적인 코드를 하나 선택해서 그 쪽으로 jump할 수 있다면 좋을 것입니다.

─────────────────────────────────────────────────
If flip pos is A:
    Jump to B
else:
    continue (Jump to A)
─────────────────────────────────────────────────
[A] Printing 'I am Invincible!'
─────────────────────────────────────────────────
[B] Printing 'I am Invincible!'
─────────────────────────────────────────────────

이를 작성해보면 다음과 같습니다.

from pwn import *

context.arch = 'amd64'
base_code = """
    /* push 'I am Invincible!\x00' */
    mov rax, 0x21656c6269636e69
    push rax
    mov rax, 0x766e49206d612049
    push rax
    /* write(fd=1, buf='rsp', n=16) */
    push 1
    pop rdi
    push 0x10
    pop rdx
    mov rsi, rsp
    /* call write() */
    push SYS_write /* 1 */
    pop rax
    syscall
    /* exit(status=0) */
    xor edi, edi /* 0 */
    /* call exit() */
    push SYS_exit /* 0x3c */
    pop rax
    syscall
"""

len_base_code = len(asm(base_code))

branch_code = """
    cmp cl, {}
    jb LABEL
""".format(len_base_code + 5 + 50)
# 5: len(branch_code)
# 50: offset

code = branch_code + base_code
code += "LABEL:"
code += base_code

code = asm(code)

with open('shellcode', 'wb') as f:
    f.write(code)

이를 테스트해보면 Result: 1579 / 1600가 나옵니다. 이 쪽이 좀 더 안정성이 있고, jump하는 코드 (branch_code)를 잘 고치기만 한다면 점수를 더 높일 수 있을 것 같습니다. 실제로 대회에서는 이 방법으로 계속 진행했습니다.

3. 1-flip Resistant한 코드 찾기

만약 A라는 코드가 있을 때, A의 임의의 1-bit를 flip했을 때 Invalid Instruction이나 Segmentation Fault와 같은 오류 없이 정상적으로 실행이 되기는 한다고 해봅시다. 그러면 이런 코드를 2개 연달아 붙여놓으면 둘 중 하나는 정상적으로 실행이 되어서 원래 의도대로 실행이 될 것입니다.

이런 아이디어를 사용한다면 문제에서 준 3개의 옵션 중 2번: 모든 레지스터를 mmap을 통해 할당한 R/W 영역의 위치로 세팅한다. 를 응용할 방법이 있을 지도 모릅니다.

하지만 대회가 끝날 때까지 쉽게 생각하지 못했습니다. 이에 대해서 참고할만한 흥미로운 17년도 BlackHat PPT가 있습니다. 나중에 시간날 때 한 번 체크해보세요.

1-Flip Resistant한 코드 작성하기

앞에서 살펴본 코드를 다시 봅시다.

    cmp cl, offset
    jb LABEL

cmp cl, offsetoffset이라는 immediate value와 cl register를 비교하는 instruction으로 4 byte를 차지합니다. 1-bit flip 된다고 하면 offset 값이 크게 변하거나 하면서 취약해질 수도 있고, 경우에 따라서 [register + offset] memory 위치를 참조하는 코드로 바뀌면서 segmentation fault로 변할 가능성도 있습니다.

그리고 X64 Assembly의 opcode를 볼 수 있는 사이트도 참조를 해봅시다. jb instruction은 opcode가 72인데, 당장 1-bit flip하면 나올 수 있는 62 opcode가 invalid opcode입니다. 즉 더 좋은 jump instruction을 사용할 필요성이 있습니다.

해당 사이트를 참조해서 살펴보면, 78부터 7D 까지의 opcode를 사용할 수 있는 것으로 보입니다. 적어도, 1-bit flip 했을 때 invalid opcode가 되지는 않습니다. 그런데 jp/jnp instruction은 parity flag에 따라 jump하는 instruction입니다. Parity flag는 instruction을 수행하고 나온 결과가 짝수냐 홀수냐에 따라서 set되는 flag이기 때문에 사용하는 것은 어려워보입니다. 곧 js/jns/jl/jnl이 현실적으로 사용 가능한 instruction입니다.

이러한 결론에 따라서 다음과 같이 코드를 작성해볼 수 있습니다.

from pwn import *
context.arch = 'amd64'

base_code = """
    /* push 'I am Invincible!' */
    mov rax, 0x21656c6269636e69
    push rax
    mov rax, 0x766e49206d612049
    push rax
    /* write(fd=1, buf='rsp', n=16) */
    push 1
    pop rdi
    push 0x10
    pop rdx
    mov rsi, rsp
    /* call write() */
    push SYS_write /* 1 */
    pop rax
    syscall
    /* exit(status=0) */
    xor edi, edi /* 0 */
    /* call exit() */
    push SYS_exit /* 0x3c */
    pop rax
    syscall
"""

len_base_code = len(asm(base_code))

branch_code = """
branch_start:
    mov bl, branch_end - branch_start + 50
    sub cl, bl
    jge branch_start + 0x80
branch_end:
"""

code = branch_code
code += 'nop\n' * 10
code += base_code
code += 'nop\n' * 98
code += base_code
asm_code = asm(code)

with open('shellcode', 'wb') as f:
    f.write(asm_code)

이제 이를 통해서 Result: 1594 / 1600까지 줄일 수 있었습니다.

그리고 여기에서 계속 하나씩 깎고, 깎고, 깎다보면, 다음과 같은 code까지 올 수 있습니다.

from pwn import *
context.arch = 'amd64'

base_code = """
    /* push 'I am Invincible!' */
    mov rax, 0x21656c6269636e69
    push rax
    mov rax, 0x766e49206d612049
    push rax
    /* write(fd=1, buf='rsp', n=16) */
    push 1
    pop rdi
    push 0x10
    pop rdx
    mov rsi, rsp
    /* call write() */
    push SYS_write /* 1 */
    pop rax
    syscall
    /* exit(status=0) */
    xor edi, edi /* 0 */
    /* call exit() */
    push SYS_exit /* 0x3c */
    pop rax
    syscall
"""

len_base_code = len(asm(base_code))

branch_code = """
branch_start:
    xor al, branch_end - branch_start + 119
    cmp al, cl
    jns branch_end + 119
branch_end:
"""

code = branch_code
code += 'push rax\n'
code += 'nop\n' * 9
code += base_code
code += 'nop\n' * 98
code += base_code
asm_code = asm(code)
print(len(asm_code))
print(asm_code.encode('hex'))
print(disasm(asm_code))

with open('shellcode', 'wb') as f:
    f.write(asm_code)

이는 경험적으로 나온 부분인데, 어떻게 코드가 나왔는지를 요약하면 다음과 같습니다.

  • js/jns를 사용하면 jl/jnl을 사용할 때보다 jump instruction의 bit flip이 일어날 때 좀 더 잘 버팁니다.
  • cmp의 opcode가 80이여서 처음에는 사용하지 못한다고 생각했는데, register끼리 비교하는 cmp의 경우 38~3D 로 사용이 가능합니다. 이 중에서도 cmp bl, cl을 쓸 지, cmp cl, bl을 쓸지 등등 다양하게 try해보면 그 중에서도 cmp al, cl이 안정적이라는 것을 알 수 있었습니다.
  • 또한 mov의 경우 bitflip을 하다보면 illegal instruction이 무조건 한 번 나오는데, al이 0이기 때문에 xor을 통해서 초기화가 가능한데 이 경우 illegal instruction을 아예 없앨 수 있습니다.

마무리

결과적으로 한 bit에 대해서만 동작하지 않는 코드가 완성되어서 999점을 받을 수 있었습니다. 대회가 끝난 뒤 찾아보니, 한 팀이 1000점을 받는데 성공했고 저희를 포함해 3~4팀이 999점을 받은 것으로 보입니다.

해당 점수를 따라서 등수를 나누고, 등수에 따라서 5등까지 5분마다 점수가 들어오는 방식이였기 때문에 999점 코드를 만들고 당분간 점수를 받을 수 있었습니다. 이를 통해 얻은 점수가 대략적으로 KoTH 장르 점수에서 300점이었는데, KoTH 장르는 전체 점수의 20%로 합산이 되기 때문에 대략 60점 정도를 팀에 기여할 수 있었습니다. 999점 미만의 점수를 받았다면 5등 이내에 들지 못해 점수를 받지 못했을 것이고, 결과를 보다시피 이 60점이 없었으면 12등까지 내려가는 참사가 벌어졌기 때문에 정말 다행이라고 생각하고 있습니다.

Shellcoding을 한지 몹시 오래 되었는데 이번 기회에 다시 연습해볼 수 있어서 좋았다고 생각합니다.