🏌️ Binary golfing - Introduction

Table of Contents

So tmp.out - once again - got me. Especially netspooky, which wrote about golfing binaries. I was instantly caught in golfing.

Binary golfing? #

Crafting the smallest binary which does a particular task.

Why someone would do this?

Learn about binary executables and format parsers
Flex on muggles

My notes on ELF format #

It is recommanded to code in assembly in order to manage your headers as you wish.

We can handcraft binaries, because GCC is a bit messy when compiling code and linking stuff. We can then make sections or headers overlap to save more space.

In brief, the section header table is for use by the compiler and linker, while the program header table is for use by the program loader. The program header table is optionnal and never present in practice, the section header table is also optional but always present.
Brian Raiter, “A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux”

Compile #

Classic way:

1nasm -f elf32 file.s
2ld -m elf_i386 -nmagic file.o -o bin

Better:

1nasm -f bin file.s

To directly craft a binary from NASM file.

Header #

The smallest valid header I can think of might be:

7f45 4c46 01?? ???? ???? ???? ???? ????
0200 0300 0100 ???? dead beef 2c00 0000
???? ???? ???? ???? 3400 2000 0100 0000
???? ???? 0000 0008 0000 0008 !!!! !!!!
!!!! !!!! 0500 0000 0010 0000

Considering the following:

??: garbage, so you can just use those bytes for your code
!!!! !!!!: total size of the header, so it will depend on your code
dead beef: address of the entrypoint

Here is a template I modified from here, so all creds to the author:

 1bits 32
 2
 3org 0x8000000
 4
 5ehdr:                           ; Elf32_Ehdr
 6db 0x7F, "ELF", 1, 1, 1, 0      ; e_ident
 7times 8 db 0
 8dw 2                            ; e_type
 9dw 3                            ; e_machine
10dd 1                            ; e_version
11dd _start                       ; e_entry
12dd phdr-$$                      ; e_phoff
13dd 0                            ; e_shoff
14dd 0                            ; e_flags
15dw ehdrsize                     ; e_ehsize
16dw phdrsize                     ; e_phentsize
17dw 1                            ; e_phnum
18dw 0                            ; e_shentsize
19dw 0                            ; e_shnum
20dw 0                            ; e_shstrndx
21
22ehdrsize equ $-ehdr
23
24phdr:                           ; Elf32_Phdr
25dd 1                            ; p_type
26dd 0                            ; p_offset
27dd $$                           ; p_vaddr
28dd $$                           ; p_paddr
29dd filesize                     ; p_filesz
30dd filesize                     ; p_memsz
31dd 5                            ; p_flags
32dd 0x1000                       ; p_align
33
34phdrsize equ $-phdr
35
36_start:
37
38; your program here
39
40filesize equ $-$$

And the version for 64 bits (taken from here):

 1bits 64
 2org 0x8000000
 3
 4ehdr:                                ; Elf64_Ehdr
 5  db 0x7F, "ELF", 2, 1, 1, 0         ;   e_ident
 6  times 8 db  0
 7  dw 2                               ;   e_type
 8  dw 62                              ;   e_machine
 9  dd 1                               ;   e_version
10  dq _start                          ;   e_entry
11  dq phdr - $$                       ;   e_phoff
12  dq 0                               ;   e_shoff
13  dd 0                               ;   e_flags
14  dw ehdrsize                        ;   e_ehsize
15  dw phdrsize                        ;   e_phentsize
16  dw 1                               ;   e_phnum
17  dw 0                               ;   e_shentsize
18  dw 0                               ;   e_shnum
19  dw 0                               ;   e_shstrndx
20
21ehdrsize equ $-ehdr
22
23phdr:                                ; Elf64_Phdr
24  dd 1                               ;   p_type
25  dd 5                               ;   p_flags
26  dq 0                               ;   p_offset
27  dq $$                              ;   p_vaddr
28  dq $$                              ;   p_paddr
29  dq filesize                        ;   p_filesz
30  dq filesize                        ;   p_memsz
31  dq 0x1000                          ;   p_align
32
33phdrsize equ $-phdr
34
35_start:
36  ; your code here
37
38filesize equ $-$$

Unethical stuff #

Declaring variables in the wild #

🙈 Nothing forbidens to declare variables anywhere, to save some space you can skip using the .rodata section.

1section .text
2	var: db "salut", 0xa

Use header as code section #

🧠 Big brain move here: put code in the header

 1ehdr:
 2	db 0x7f, "ELF"
 3	db 1, 1, 1, 0, 0
 4_start:
 5	mov bl, 42
 6	xor eax, eax
 7	inc eax
 8	int 0x80
 9	;; continue the header
10	dw 2
11	dw 3
12	dw 1
13	;; ...

Golfing resources #

A while ago I created a repo containing some random assembly programs I did, I added my try to make a tiny Hello world binary: https://github.com/OxNinja/nasm_/tree/main/elf-golfing

https://codegolf.stackexchange.com/questions/5696/shortest-elf-for-hello-world-n

Create tiny ELF for Linux

https://www.muppetlabs.com/~breadbox/software/tiny/

Analyzing ELF with malformed headers

Draft

🔎 Creating a VM for fun - Part 1: ASM

<time datetime="2022-03-17 10:39:42 +0200 +0200">17 March 2022</time>·451 words·3 mins· 0 <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"> <path fill="currentColor" d="M288 32c-80.8 0-145.5 36.8-192.6 80.6C48.6 156 17.3 208 2.5 243.7c-3.3 7.9-3.3 16.7 0 24.6C17.3 304 48.6 356 95.4 399.4C142.5 443.2 207.2 480 288 480s145.5-36.8 192.6-80.6c46.8-43.5 78.1-95.4 93-131.1c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C433.5 68.8 368.8 32 288 32zM432 256c0 79.5-64.5 144-144 144s-144-64.5-144-144s64.5-144 144-144s144 64.5 144 144zM288 192c0 35.3-28.7 64-64 64c-11.5 0-22.3-3-31.6-8.4c-.2 2.8-.4 5.5-.4 8.4c0 53 43 96 96 96s96-43 96-96s-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6z"/></svg> · 0 <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"> <path fill="currentColor" d="M47.6 300.4L228.3 469.1c7.5 7 17.4 10.9 27.7 10.9s20.2-3.9 27.7-10.9L464.4 300.4c30.4-28.3 47.6-68 47.6-109.5v-5.8c0-69.9-50.5-129.5-119.4-141C347 36.5 300.6 51.4 268 84L256 96 244 84c-32.6-32.6-79-47.5-124.6-39.9C50.5 55.6 0 115.2 0 185.1v5.8c0 41.5 17.2 81.2 47.6 109.5z"/></svg>

Custom VM assembly low-level reverse