Outline
Plaid CTF 2020의 MISC 500 문제인 golf.so는 일반적인 파일의 크기보다 작은 ELF를 만드는 것이 목표이다.
이를 풀기 위해 내용을 찾아보다 따라해볼만한 재밌는 포스트를 발견했고 그것을 정리하는 글이다.
http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html
한 가지 주의할 점은, 이 포스트는 32bit ELF, ET_EXEC를 대상으로 작성하였다는 것이다.
Basic
C언어로 작성하고
/* tiny.c */
int main(void) { return 42; }gcc로 컴파일한다.
root@ubuntu:/work/tmp/smal# gcc -Wall tiny.c
root@ubuntu:/work/tmp/smal# ls
a.out tiny.c
root@ubuntu:/work/tmp/smal# ./a.out; echo $?
42
root@ubuntu:/work/tmp/smal# wc -c a.out
8168 a.outecho $?는 마지막 종료된 프로그램에 리턴값($rax)을 출력하는 명령어이다.
프로그램의 크기가 8168b로 매우 크다.
Remove gcc Symbol
gcc 컴파일 옵션으로 심볼을 제거해본다.
root@ubuntu:/work/tmp/smal# gcc -Wall tiny.c -s
root@ubuntu:/work/tmp/smal# wc -c a.out
6056 a.out2000b 가까이 줄었다.
Use gcc Optimization
옵션 중 최적화 기능이 있다.
root@ubuntu:/work/tmp/smal# gcc -Wall tiny.c -s -O3
root@ubuntu:/work/tmp/smal# wc -c a.out
6056 a.out하지만 원본 글과 다르게 변화가 없다.
Use Assembler
어셈블리로 오브젝트를 직접 만들어 컴파일 한다.
이렇게 하면 C언어와 관련된 코드들을 제거할 수 있다.
; tiny.asm
BITS 32
GLOBAL main
SECTION .text
main:
mov eax, 42
retnasm으로 오브젝트 파일을 생성하고 컴파일 한 뒤, 크기를 확인한다.
root@ubuntu:/work/tmp/smal# nasm -f elf tiny.asm
root@ubuntu:/work/tmp/smal# gcc -m32 -Wall -s tiny.o
root@ubuntu:/work/tmp/smal# ls
a.out tiny.asm tiny.c tiny.o
root@ubuntu:/work/tmp/smal# wc -c a.out
5464 a.out600b가 줄어들었다.
x86_64 환경에서 32bit 오브젝트를 컴파일할 경우 오류가 날 수 있다. 관련된 라이브러리를 설치해준다.
sudo apt-get install gcc-multilib g++-multilib nasm -f elf array1.asm -o array1.o gcc -m32 array1.o -o array1.out
Use _start Symbol
main: 인터페이스를 사용하는 것은 큰 오버헤드를 발생시킨다고 한다.
_start: 심볼을 사용함으로써 그것을 방지할 수 있다.
; tiny_start2.asm
BITS 32
EXTERN _exit
GLOBAL _start
SECTION .text
_start:
push dword 42
call _exit추가로, _start는 main이 시작되기 이전에 가장 먼저 시작되는 영역이다.
main에서는 프롤로그 과정으로 리턴주소가 스택에 푸쉬되므로 ret를 마지막에 넣어줬지만 _start의 스택에는 리턴 주소가 없으므로 ret를 넣어줄 수 없다.
또한 직접 프로세스를 종료시켜야 하므로, ret 대신 call _exit를 추가했다.
어쨌든, 이렇게 해서 컴파일하면 그래도 에러가 발생한다.
root@ubuntu:/work/programming/smallestELF# nasm -f elf tiny_start2.asm
root@ubuntu:/work/programming/smallestELF# gcc -m32 -s -Wall tiny_start2.o
tiny_start2.o: In function `_start':
tiny_start2.asm:(.text+0x0): multiple definition of `_start'
/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib32/Scrt1.o:(.text+0x0): first defined here
/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib32/Scrt1.o: In function `_start':
(.text+0x28): undefined reference to `main'
collect2: error: ld returned 1 exit status
root@ubuntu:/work/programming/smallestELF# 기본 옵션으로 gcc가 컴파일할 때 스탠다드 시스템을 사용하는데 이 안에서는 main:이 존재해야 하기 때문이다.
따라서, -nostartfiles 옵션을 사용하여 스탠다드 시스템을 사용하지 않도록 만든다.
root@ubuntu:/work/programming/smallestELF# gcc -m32 -Wall -s -nostartfiles tiny_start2.o
root@ubuntu:/work/programming/smallestELF# ./a.out ; echo $?
42
root@ubuntu:/work/programming/smallestELF# wc -c a.out
4876 a.out600b만큼의 크기가 줄어들었다.
Remove Standard Libraries
앞서 스탠다드 시스템을 사용안했지만, 여전히 불필요한 관련된 심볼은 추가된다.
-nostdlib 옵션을 사용할 경우 해당 기능에 더해 스탠다드 라이브러리를 링크하지 않으므로 더 큰 오버헤드를 줄일 수 있다.
하지만 이 경우, 마지막에 호출하는 _exit도 스탠다드 라이브러리에 포함되는 함수이므로 컴파일시 다음과 같은 오류가 발생할 것이다.
tiny_start.asm:(.text+0x3): undefined reference to `_exit'따라서 _exit가 아닌 시스템 콜을 이용하여 직접 종료함수를 실행해야 한다.
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
xor eax, eax
inc eax
mov bl, 42
int 0x80eax를 exit의 시스템콜 넘버인 1로 설정하고, ebx로 반환할 에러넘버를 지정했다.
이제 gcc로 컴파일할 이유가 없으므로 ld 명령어를 이용해 Linking한다.
root@ubuntu:/work/programming/smallestELF# ld -s -m elf_i386 tiny.o
root@ubuntu:/work/programming/smallestELF# ./a.out; echo $?
42
root@ubuntu:/work/programming/smallestELF# wc -c a.out
240 a.out무려 4500b 가까이 줄었다.
Remove Section Header Table
이제 프로그램 크기를 더 줄이기 위해서는 헤더를 수정해야 한다. 간단히 헤더 테이블에 대해 이해한다.
- 헤더 테이블
- 각 컴포넌트들이 어디에 위치하는지 알려주는 정보- 섹션 헤더 테이블
- 바이너리 상에서 컴포넌트의 위치를 알려줌
- 컴파일러, 링커가 사용- 프로그램 헤더 테이블
- 메모리 상에서 컴포넌트의 위치를 알려줌
- ELF 로더가 사용
여기서 섹션 헤더 테이블을 제거해도 실행에 무관하다고 말한다. (아마 링킹까지 직접 해줘서 그런 것인가?)
어쨌든, 이것을 없애기 위해 빈 ELF의 포맷을 가져와서 nasm으로 바이너리를 생성하면 된다.(elf가 아닌)
다음을 어셈블리 소스로 작성한다.
; tiny.asm
BITS 32
org 0x08048000
ehdr: ; Elf32_Ehdr
db 0x7F, "ELF", 1, 1, 1, 0 ; e_ident
times 8 db 0
dw 2 ; e_type
dw 3 ; e_machine
dd 1 ; e_version
dd _start ; e_entry
dd phdr - $$ ; e_phoff
dd 0 ; e_shoff
dd 0 ; e_flags
dw ehdrsize ; e_ehsize
dw phdrsize ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
ehdrsize equ $ - ehdr
phdr: ; Elf32_Phdr
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesize ; p_filesz
dd filesize ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsize equ $ - phdr
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
filesize equ $ - $$바이너리를 생성 후 실행 및 크기를 확인한다.
root@ubuntu:/work/programming/smallestELF# nasm -f bin tiny.asm -o a.out
root@ubuntu:/work/programming/smallestELF# file a.out
a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, corrupted section header size
root@ubuntu:/work/programming/smallestELF# chmod o+x a.out
root@ubuntu:/work/programming/smallestELF# ./a.out; echo $?
42
root@ubuntu:/work/programming/smallestELF# wc -c a.out
91 a.out와우, 150b가 더 줄었다.
Overlap Identification
크기를 줄이기 위해 이제는 트릭을 이용해 헤더를 조작해야 한다.
먼저, 처음 시작되는 e_ident 필드를 수정할 수 있다.
16바이트로 구성되는 이 필드는 매직 넘버를 나타내는데 나중의 새로운 ELF 표준이 생겨서 매직 넘버가 확장될 수 있는 것을 대비하여 8바이트의 패딩이 추가되어 있다.
실제로 사용되는 것은 16바이트 중 8바이트 뿐이다.
예제 코드는 7바이트이므로 이 패딩 영역에 코드를 덮어쓸 수 있다.
; tiny.asm
BITS 32
org 0x08048000
ehdr: ; Elf32_Ehdr
db 0x7F, "ELF" ; e_ident
db 1, 1, 1, 0, 0
_start: mov bl, 42
xor eax, eax
inc eax
int 0x80
dw 2 ; e_type
dw 3 ; e_machine
dd 1 ; e_version
dd _start ; e_entry
dd phdr - $$ ; e_phoff
dd 0 ; e_shoff
dd 0 ; e_flags
dw ehdrsize ; e_ehsize
dw phdrsize ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
ehdrsize equ $ - ehdr
phdr: ; Elf32_Phdr
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesize ; p_filesz
dd filesize ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsize equ $ - phdr
filesize equ $ - $$확인해본다.
root@ubuntu:/work/programming/smallestELF# nasm -f bin tiny_ident.asm -o a.out
root@ubuntu:/work/programming/smallestELF# chmod +x a.out
root@ubuntu:/work/programming/smallestELF# ./a.out; echo $?
42
root@ubuntu:/work/programming/smallestELF# wc -c a.out
84 a.out7b가 줄어들었다.
Overlap Program Header
앞과 유사한 형태로, Program Header를 ELF Header의 마지막 부분과 오버랩시킬 수 있다.
Program Header의 값을 보면 4바이트의 1과 4바이트의 0으로 시작한다.
phdr: ; Elf32_Phdr
dd 1 ; p_type
dd 0
ELF Header의 마지막 8바이트 또한 4바이트의 1과 0이다.
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx따라서, Program Header의 시작부분을 8바이트 당겨서, ELF Header의 마지막 8바이트를 Program Header라고 속일 수 있다.
; tiny.asm
BITS 32
org 0x08048000
ehdr:
db 0x7F, "ELF" ; e_ident
db 1, 1, 1, 0, 0
_start: mov bl, 42
xor eax, eax
inc eax
int 0x80
dw 2 ; e_type
dw 3 ; e_machine
dd 1 ; e_version
dd _start ; e_entry
dd phdr - $$ ; e_phoff
dd 0 ; e_shoff
dd 0 ; e_flags
dw ehdrsize ; e_ehsize
dw phdrsize ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsize equ $ - ehdr
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesize ; p_filesz
dd filesize ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsize equ $ - phdr
filesize equ $ - $$확인해보면
root@ubuntu:/work/programming/smallestELF# nasm -f bin tiny_phdr.asm -o a.out
root@ubuntu:/work/programming/smallestELF# chmod +x a.out
root@ubuntu:/work/programming/smallestELF# ./a.out; echo $?
42
root@ubuntu:/work/programming/smallestELF# wc -c a.out
76 a.out8b를 또 줄였다.
