LINUX] Smallest ELF

노션으로 옮김·2020년 5월 20일
1

Study

목록 보기
27/33
post-thumbnail

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.out

echo $?는 마지막 종료된 프로그램에 리턴값($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.out

2000b 가까이 줄었다.

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
              ret

nasm으로 오브젝트 파일을 생성하고 컴파일 한 뒤, 크기를 확인한다.

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.out

600b가 줄어들었다.

https://stackoverflow.com/questions/31369916/unable-to-compile-assembly-usr-bin-ld-i386-architecture-of-input-file-array1

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

추가로, _startmain이 시작되기 이전에 가장 먼저 시작되는 영역이다.
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.out

600b만큼의 크기가 줄어들었다.

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     0x80

eaxexit의 시스템콜 넘버인 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.out

7b가 줄어들었다.

Overlap Program Header

앞과 유사한 형태로, Program HeaderELF Header의 마지막 부분과 오버랩시킬 수 있다.

Program Header의 값을 보면 4바이트의 14바이트의 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.out

8b를 또 줄였다.

0개의 댓글