[user@n0.lol ~/bp/elfbinarymangling]

ELF Binary Mangling 101

Okay, so you want to see how small you can make a 64 bit binary. In the age of giant bloated applications full of impossibly convoluted machine instructions doing who knows what, it's nice sometimes to get down to the lowest of low levels and create something so tiny, that you know what every single bit is doing and it's purpose. To do so, we need to employ some standard tricks and a little creativity to get us down there.

Let's start with a really simple program that prints a string in the terminal! I chose these smaller opcodes to save a bit more space, but we can get into assembly optimization in another post.

.global _start
.text

_start:            
        mov     $1, %al     # RAX holds Syscall 1 (write), I chose al because it's shorter than mov $1, %rax
        mov     %rax, %rdi  # RDI holds File Handle 1, STDOUT. Again, moving RAX to RDI is shorter than mov $1, %rdi
        mov     $msg, %rsi  # RSI holds the address of our string buffer. 
        mov     $11, %dl    # RDX holds the size our of string buffer. Moving into %dl to save space.
        syscall             # Invoke a syscall with these arguments.

        mov     $60, %al    # Now we are invoking syscall 60. 
        xor     %rdi, %rdi  # Zero out RDI, which holds the return value.
        syscall             # Call the system again to exit.

msg:
        .ascii "[^0^] u!!\n"

This program does the simplest form of writing to STDOUT. It invokes a raw Unix system call to the kernel, with the registers containing the arguments. Save this into a file called asm_smile.s

$ vim asm_smile.s
$ as asm_smile.s -o asm_smile.o

Now we've created an object file that can be used to create an executable. We can link it with ld, then run.

$ ld asm_smile.o -o asm_smile
$ ./asm_smile
[^0^] u!!

Okay what have we done here? Let's take a look at the raw data we generated. A good place to start is objdump.

$ objdump -d asm_smile

asm_smile:     file format elf64-x86-64


Disassembly of section .text:

0000000000400078 <_start>:
  400078:       b0 01                   mov    $0x1,%al
  40007a:       48 89 c7                mov    %rax,%rdi
  40007d:       48 c7 c6 8f 00 40 00    mov    $0x40008f,%rsi
  400084:       b2 0b                   mov    $0xb,%dl
  400086:       0f 05                   syscall
  400088:       b0 3c                   mov    $0x3c,%al
  40008a:       48 31 ff                xor    %rdi,%rdi
  40008d:       0f 05                   syscall

000000000040008f <msg>:
  40008f:       5b                      pop    %rbx
  400090:       5e                      pop    %rsi
  400091:       30 5e 5d                xor    %bl,0x5d(%rsi)
  400094:       20 75 21                and    %dh,0x21(%rbp)
  400097:       21 0a                   and    %ecx,(%rdx)

We have 33 bytes of data here, so why is our program 752 bytes? Let's take a look at a quick hex dump.

$ hexdump -C asm_smile

00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  b0 01 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 05 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|
00000060  99 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000070  00 00 20 00 00 00 00 00  b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  8f 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05 5b  |..@......<H1...[|
00000090  5e 30 5e 5d 20 75 21 21  0a 00 00 00 00 00 00 00  |^0^] u!!........|
000000a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000000b0  00 00 00 00 00 00 00 00  00 00 00 00 03 00 01 00  |................|
000000c0  78 00 40 00 00 00 00 00  00 00 00 00 00 00 00 00  |x.@.............|
000000d0  01 00 00 00 04 00 f1 ff  00 00 00 00 00 00 00 00  |................|
000000e0  00 00 00 00 00 00 00 00  0d 00 00 00 00 00 01 00  |................|
000000f0  8f 00 40 00 00 00 00 00  00 00 00 00 00 00 00 00  |..@.............|
00000100  16 00 00 00 10 00 01 00  78 00 40 00 00 00 00 00  |........x.@.....|
00000110  00 00 00 00 00 00 00 00  11 00 00 00 10 00 01 00  |................|
00000120  99 00 60 00 00 00 00 00  00 00 00 00 00 00 00 00  |..`.............|
00000130  1d 00 00 00 10 00 01 00  99 00 60 00 00 00 00 00  |..........`.....|
00000140  00 00 00 00 00 00 00 00  24 00 00 00 10 00 01 00  |........$.......|
00000150  a0 00 60 00 00 00 00 00  00 00 00 00 00 00 00 00  |..`.............|
00000160  00 61 73 6d 5f 73 6d 69  6c 65 2e 6f 00 6d 73 67  |.asm_smile.o.msg|
00000170  00 5f 5f 62 73 73 5f 73  74 61 72 74 00 5f 65 64  |.__bss_start._ed|
00000180  61 74 61 00 5f 65 6e 64  00 00 2e 73 79 6d 74 61  |ata._end...symta|
00000190  62 00 2e 73 74 72 74 61  62 00 2e 73 68 73 74 72  |b..strtab..shstr|
000001a0  74 61 62 00 2e 74 65 78  74 00 00 00 00 00 00 00  |tab..text.......|
000001b0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
000001f0  1b 00 00 00 01 00 00 00  06 00 00 00 00 00 00 00  |................|
00000200  78 00 40 00 00 00 00 00  78 00 00 00 00 00 00 00  |x.@.....x.......|
00000210  21 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |!...............|
00000220  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000230  11 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
00000240  00 00 00 00 00 00 00 00  89 01 00 00 00 00 00 00  |................|
00000250  21 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |!...............|
00000260  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000270  01 00 00 00 02 00 00 00  00 00 00 00 00 00 00 00  |................|
00000280  00 00 00 00 00 00 00 00  a0 00 00 00 00 00 00 00  |................|
00000290  c0 00 00 00 00 00 00 00  04 00 00 00 04 00 00 00  |................|
000002a0  08 00 00 00 00 00 00 00  18 00 00 00 00 00 00 00  |................|
000002b0  09 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
000002c0  00 00 00 00 00 00 00 00  60 01 00 00 00 00 00 00  |........`.......|
000002d0  29 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |)...............|
000002e0  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000002f0

Hrm... There's quite a bit of extra data in there! We can see our program begin at 0x78 and end at 0x98. How can you make a binary smaller right off the bat? We can use strip!

$ strip asm_smile

What strip does is take a binary file, and remove a lot of the extra debug and compiler info that isn't needed. So what does our binary look like now?

$ hexdump -C asm_smile
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  b0 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|
00000060  99 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000070  00 00 20 00 00 00 00 00  b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  8f 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05 5b  |..@......<H1...[|
00000090  5e 30 5e 5d 20 75 21 21  0a 00 2e 73 68 73 74 72  |^0^] u!!...shstr|
000000a0  74 61 62 00 2e 74 65 78  74 00 00 00 00 00 00 00  |tab..text.......|
000000b0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
000000f0  0b 00 00 00 01 00 00 00  06 00 00 00 00 00 00 00  |................|
00000100  78 00 40 00 00 00 00 00  78 00 00 00 00 00 00 00  |x.@.....x.......|
00000110  21 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |!...............|
00000120  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000130  01 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
00000140  00 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000150  11 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000160  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000170

Now we are down to 368 bytes! That's a pretty small program. But remember, our machine instructions were just 33 bytes, so what's up with all this overhead?

Let's break down the sections of an ELF binary real quick. If you're not used to looking at hex dumps and hand modifying data, this is a great place to start. It's not that scary!

All ELF binaries need to have a few things in place in order for them to be interpreted by the Linux kernel properly. As with Windows EXEs, there's a structure to the header that defines the overall layout of the binary.

This example is using x86_64 assembly, so the ELF binaries I am describing here are the 64 bit version. The 32 bit version is slightly different.

We can also use another program called readelf to help us follow along!

$ readelf -a asm_smile
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x400078
  Start of program headers:          64 (bytes into file)
  Start of section headers:          176 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         1
  Size of section headers:           64 (bytes)
  Number of section headers:         3
  Section header string table index: 2

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000400078  00000078
       0000000000000021  0000000000000000  AX       0     0     1
  [ 2] .shstrtab         STRTAB           0000000000000000  00000099
       0000000000000011  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000000099 0x0000000000000099  R E    200000

ELF & Program Headers

This section defines the file as an ELF binary. In the hex dump it looks like this:

00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  b0 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 03 00 02 00  |....@.8...@.....|

Each one of these bytes has a specific purpose. Take a look at this table, adapted from http://wiki.osdev.org/ELF

Position   Value
0-3        Magic number - 0x7F, then 'ELF' in ASCII
4          1 = 32 bit, 2 = 64 bit
5          1 = little endian, 2 = big endian
6          ELF Version
7          OS ABI - usually 0 for System V
8-15       Unused/padding
16-17      1 = relocatable, 2 = executable, 3 = shared, 4 = core
18-19      Instruction set - see table below
20-23      ELF Version
24-31      Program entry position
32-39      Program header table position
40-47      Section header table position
48-51      Flags - architecture dependent; see note below
52-53      Header size
54-55      Size of an entry in the program header table
56-57      Number of entries in the program header table
58-59      Size of an entry in the section header table
60-61      Number of entries in the section header table
62-63      Index in section header table with the section name

Next up is the program header.

00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|
00000060  99 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000070  00 00 20 00 00 00 00 00                           |.. .....        |

From the output of readelf, we can see that it matches up with the hex dump.

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000000099 0x0000000000000099  R E    200000

          Section Metadata, flags etc --->           
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
          Virtual Address          Physical Address
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|

          File Size                Memsize
00000060  99 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
          Alignment
00000070  00 00 20 00 00 00 00 00                           |.. .....        |

Next up is the machine instructions themselves. We saw these earlier when we used objdump, but in their raw form they look like this.

00000078                           b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  8f 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05 5b  |..@.......H1...[|
00000090  5e 30 5e 5d 20 75 21 21  0a 00                    |^0^] u!!.

Section Headers

What is all this stuff after this point?

These next chunks of information are known as the section headers. They are used to describe the layout of the sections in the binary. You can see in the section header output of readelf that we have descriptions of the .text and .shstrtab sections. The .text section is what we just saw above, at offset 0x00000078, containing the machine instructions. The section after that is .shstrtab, which is the table of addresses where strings are located in the file.

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000400078  00000078
       0000000000000021  0000000000000000  AX       0     0     1
  [ 2] .shstrtab         STRTAB           0000000000000000  00000099
       0000000000000011  0000000000000000           0     0     1

000000f0  0b 00 00 00 01 00 00 00  06 00 00 00 00 00 00 00  |................|
00000100  78 00 40 00 00 00 00 00  78 00 00 00 00 00 00 00  |x.@.....x.......|
00000110  21 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |!...............|
00000120  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000130  01 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
00000140  00 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000150  11 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000160  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000170

.shstrtab is funny to me because in binaries this small, it's really only describing the string that describes itself, as well as the .text section. It's kind of a recursive loop of self reference. "Q: Why are you here? A: To tell you about me being here!" In any case, these are totally unnecessary unless you are actively debugging the program. All we need are the machine instructions, so we can get rid of this big bulk of the .shstrtab and the section headers by hand with your hex editor of choice. Delete everything from 0x99 on!

The resulting binary looks like this:

00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  b0 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|
00000060  99 00 00 00 00 00 00 00  99 00 00 00 00 00 00 00  |................|
00000070  00 00 20 00 00 00 00 00  b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  8f 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05 5b  |..@......<H1...[|
00000090  5e 30 5e 5d 20 75 21 21  0a                       |^0^] u!!

We keep the 0a byte at the end just so the terminal knows that the string is over and we need a new line.

So we see in the objdump from before that we MOV 0x40008f into %rsi, which is a virtual address pointing to our string 0x5b5e305e5d207521210a.

0000000000400078 <_start>:
  400078:       b0 01                   mov    $0x1,%al
  40007a:       48 89 c7                mov    %rax,%rdi
  40007d:       48 c7 c6 8f 00 40 00    mov    $0x40008f,%rsi  <--- Right here!
  400084:       b2 0b                   mov    $0xb,%dl
  400086:       0f 05                   syscall
  400088:       b0 3c                   mov    $0x3c,%al
  40008a:       48 31 ff                xor    %rdi,%rdi
  40008d:       0f 05                   syscall

000000000040008f <msg>:
  40008f:       5b                      pop    %rbx           <--- Points to right here.
  400090:       5e                      pop    %rsi
  400091:       30 5e 5d                xor    %bl,0x5d(%rsi)
  400094:       20 75 21                and    %dh,0x21(%rbp)
  400097:       21 0a                   and    %ecx,(%rdx)

If the binary is pointing to the absolute address of the string at 0x40008f, and that maps out to 0x00008f in our binary, what if we save even more space (10 whole bytes!) by moving our string somewhere else? But where else? At first glance it looks like all the bytes up top are accounted for. x86_64's structure is a bit more rigid than x86, because of the amount of space needed to hold addresses in such a large memory space. But there are still some spots that we can hide some data.

The ELF header from above contains a bit of padding at 0x08 - 0x015. It also contains some bytes that are pretty much stuck at a value at this point. The ELF version (which is 1 for version 1) at 0x06, and the OS Application Binary Interface at 0x07. These can be overwritten and still run on most Unix based systems, and are a perfect location to begin our code insertion.

We can move our string up into the header like this

Original Header:
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
New Header:
00000000  7f 45 4c 46 02 01 5b 5e  30 5e 5d 20 75 21 21 0a  |.ELF..[^0^] u!!.|

Now before we run this, we have to make sure our machine code is pointing to where our new string is. Previously we were at 0x40008f, which is referenced in the binary at 0x00000080.

48 c7 c6 8f 00 40 00    mov    $0x40008f,%rsi 

Since our string is now at 0x00000006 in our binary, we change the address at 0x00000080 as such. Note: Addresses are little endian, so 0x0040008f is represented as 0x8f004000.

Original: 
00000078                           b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  8f 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05     |..@.......H1... |

Changed:
00000078                           b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  06 00 40 00 b2 0b 0f 05  b0 3c 48 31 ff 0f 05     |..@.......H1... |

And there you have it. We have successfully rearranged this binary by hand to hide code in the header, and have removed debugging capabilities. Our binary should do the same thing as it did when we first compiled it, but now at a lean 143 bytes. Much more interesting effects can be achieved with similar techniques, so go explore!

Final output:

00000000  7f 45 4c 46 02 01 5b 5e  30 5e 5d 20 75 21 21 0a  |.ELF..[^0^] u!!.|
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  01 00 00 00 00 00 00 00  |....@.8.........|
00000040  01 00 00 00 05 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 00 40 00 00 00 00 00  |..@.......@.....|
00000060  8f 00 00 00 00 00 00 00  9e 00 00 00 00 00 00 00  |................|
00000070  00 00 20 00 00 00 00 00  b0 01 48 89 c7 48 c7 c6  |.. .......H..H..|
00000080  06 00 40 00 b2 0a 0f 05  b0 3c 48 31 ff 0f 05     |..@......<H1...|

$ ./asm_smile
[^0^] u!!