This post is the writeup of my attempt to solve Synactiv's 2025 winter challengehttps://www.synacktiv.com/publications/2025-winter-challenge-quinindrome.html .
The challenge was to produce the smallest "quinindrome" for Linux possible: an ELF file that when run, produces it's own contents, and is the same byte for byte, forwards and backwards. This is a variation on the classic ELF golf challenge, finding ways to make a binary as small as possible. I had a great time trying to solve the challenge, so thanks to the author!
I wrote this as I went, so it's pretty rough, but I think that in itself has benefits: it's the actual narrative of how I tackled the challenge, including a bunch of mistakes and things that were new to me, and doesn't present this as some perfect polished solution as if I knew this stuff all along. End to end this took ~ 8 hours, spread across a few days I'd say. However overall the post isn't very polished, and is quite long.
Most of the knowledge for this challenge I've just picked up over the years from various bits of C dev, both professional and hobbyist, as well as a bunch of time doing low level linux process & ELF manipulation. Plus a bit of research and chatbot assistance for the final pieces. If these topics aren't super familiar to you, no worries, hopefully the post makes sense, and I've put together a little reading list of blogs and stuff if you want to learn more (fair warning: some are fairly hardcore).
Reading list:
- https://github.com/tmpout/awesome-elf: a reading list of ELF resources, good starting point
- Funky file formats by Ange Albertini https://www.youtube.com/watch?v=hdCs6bPM4is, the OG polyglot researcher doing a great CCC talk on abusing file structures
- https://github.com/corkami/pics/blob/master/binary/elf101/elf101.pdf also by Ange Albertini, some lovely diagrams of file structure
- https://fasterthanli.me/series/making-our-own-executable-packer: a long but really great blog post series about writing your own ELF loader. Following this through to the end and you will understand ELF.
- https://github.com/tmpout the go-to zine on ELF infection and code golf, some insanely smart people writing here
Attempt 1
Ok, so again, the aim is to write a binary that:
- is the same back to front
- output's itself to stdout
I just started off by writing a super simple C program to solve the challenge, with no attempts at reducing size:
printself.c
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#define MAXSIZE 20000
int main(int argc, char** argv) {
int fd = open(argv[0], 0);
char buf[MAXSIZE] = {0};
read(fd, buf, MAXSIZE);
fprintf(stdout, "%s\n", buf);
}
Let's run, and use diff to check the output matches the binary
[~/synactiv]$ ./printself > out
[~/synactiv]$ diff out printself
Binary files out and printself differ
[~/synactiv]$ xxd out
00000000: 7f45 4c46 0201 010a .ELF....
Oops, because we used printf, null bytes in the file terminate the file early. So let's rework to use write and seek to determine the size of the file.
#include <stdio.h>
#include <assert.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#define MAXSIZE 20000
int main(int argc, char** argv) {
int fd = open(argv[0], 0);
off_t size = lseek(fd, 0, SEEK_END);
assert(size<MAXSIZE);
char buf[MAXSIZE] = {0};
read(fd, buf, size);
write(1, buf, size);
}
Now let's try again:
[~/synactiv]$ ./printself > out
[~/synactiv]$ cmp out printself
out printself differ: byte 1, line 1
[~/synactiv]$ xxd out | head
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
whoops that failed, since when we seek to the end, we don't return the seek head to the start, leading to printing a bunch of \x00's. We fix that by adding:
lseek(fd, 0, SEEK_SET);
Now if we try it works:
[~/synactiv]$ ./printself
@@@@�xx�� pp�-�=�=���-�=�=�888 XXXDDS�td888 P�td$ $ $ DDQ�tdR�td�-�=�=xx/lib64/ld-linux-x86-64.so.2GNU�GNU�U���z<�ͻ[����
Let's make it a palindrome and test it.
- start with a super naive palindrome tool: simply append the binary, backwards, to the existing binary. Since the ELF sections won't point into the new appended data, this won't cause any issues
- later we will see if we can shrink this down by taking advantage of the ELF header format
mirror.py:
import sys
if len(sys.argv) != 3:
print("Usage: python flip.py <input_file> <output_file>")
sys.exit(1)
input_file, output_file = sys.argv[1], sys.argv[2]
with open(input_file, 'rb') as f:
data = f.read()
with open(output_file, 'wb') as f:
f.write(data + data[::-1])
print(f"Wrote {len(data)*2} bytes to {output_file}")
[~/synactiv]$ python3 mirror.py printself printself.m
[~/synactiv]$ ./test.sh printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 34048
our first working solution! But with no attempt to reduce the binary size, our palindrome file stands at a whopping 34048 bytes :)
Attempt 2: reducing the size
At the moment our original binary size is 17024 bytes (half our naive palindrome).
Let's try some basic compiler tricks to reduce the size: optimisation and stripping. With this simple a binary it's unlikely this will really have a massive effect but it's worth a try.
# without optimisation
[~/synactiv]$ gcc printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 17024 Dec 3 00:21 printself
# using -Os to optimise for size
[~/synactiv]$ gcc -Os printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 16984 Dec 3 00:21 printself
Ok so -Os makes a bit smaller but not much.
Stripping, with strip-all makes it smaller still. it should be noted that strip-all doesnt actually strip all unnecessary data, just well known sections.
[~/synactiv]$ strip --strip-all printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 14472 Dec 3 00:21 printself
[~/synactiv]$
Just for fun, what does UPX give us? UPX is a packer that can compress binaries by reducing to just the decompression stub plus compressed binary data.
[~/synactiv]$ upx -9 printself
Ultimate Packer for eXecutables
Copyright (C) 1996 - 2018
UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018
File size Ratio Format Name
-------------------- ------ ----------- -----------
upx: printself: NotCompressibleException
Packed 1 file: 0 ok, 1 error.
[~/synactiv]$
ha, upx says the binary is so small it can't be compressed.
Ok let's try some slightly more aggressive compilation flags:
[~/synactiv]$ gcc -Os -ffunction-sections -fdata-sections -Wl,--gc-sections printself.c -o printself ; ls -l printself
-rwxrwxr-x 1 hendo hendo 16880 Dec 3 00:24 printself
These flags basically tell the compiler not to include unneeded sections of code. However they only get our size down about a hundred bytes, from 17024 to 16880., since there wasn't much slack in there.
Now let's start messing with the code. What if we remove the safety check from assert:
[~/synactiv]$ gcc printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 16928 Dec 3 00:28 printself
Ok wow we shaved off a whole 96 bytes, not very helpful.
What about other std libs? libmusl etc should be smaller than libc?
[~/synactiv]$ musl-gcc printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 19624 Dec 3 00:30 printself
[~/synactiv]$ strip --strip-all printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 13952 Dec 3 00:30 printself
Ok, yeah with musl & stripping we're down a bit more. If we also compile with -static we avoid some of the overhead of linking, so we go down even more:
[~/synactiv]$ musl-gcc -static printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 20712 Dec 3 00:30 printself
[~/synactiv]$ strip --strip-all printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 13424 Dec 3 00:30 printself
So our current best for the elf at the moment is 13424 bytes, not really that small. Let's just check it passes our test still:
[~/synactiv]$ python3 mirror.py printself printself.m
Wrote 26848 bytes to printself.m
[~/synactiv]$ ./test.sh printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 26848
Ok, so our new best score is 26848. Going further will begin to be a bit more intrusive, start going into some of the weirder compiler / ELF territory, so we'll leave this attempt here.
Attempt 3: weird compiler stuff
when an ELF starts up, it doesn't go straight to main. ELFs compiled with gcc etc will typically have a bunch of gunk before invoking main. We can actually remove that from the file and bypass it by using _start and the compiler flag -nostartfiles. However the drawback now is we lose features, for example the lovely convinient argc & argv we get with main. If we skip the libc setup, we skip the code that retrieves them from the stack.
If we want to retrieve argv ourselves we can, but it's a bit more involved. I have here a brilliant diagram of stack layouts at program startup, I can't remember where from but probably tmpout.
<HIGHEST ADDR> <BOTTOM OF STACK>
------------------------------------------------------------- 0x7fff6c845000
0x7fff6c844ff8: 0x0000000000000000
_ 4fec: './stackdump\0' <------+
env / 4fe2: 'ENVVAR2=2\0' | <----+ *environ = highest
\_ 4fd8: 'ENVVAR1=1\0' | <---+ |
/ 4fd4: 'two\0' | | | <----+
args | 4fd0: 'one\0' | | | <---+ |
\_ 4fcb: 'zero\0' | | | <--+ | |
3020: random gap padded to 16B boundary | | | | | |
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -| | | | | |
3019: 'x86_64\0' <-+ | | | | | |
auxv 3009: random data: ed99b6...2adcc7 | <-+ | | | | | |
data 3000: zero padding to align stack | | | | | | | |
. . . . . . . . . . . . . . . . . . . . . . . . . . .|. .|. .| | | | | |
2ff0: AT_NULL(0)=0 | | | | | | | |
2fe0: AT_PLATFORM(15)=0x7fff6c843019 --+ | | | | | | |
ELF AUXV ...
2ee0: AT_HWCAP(16)=0xbfebfbff | | | | |
2ed0: AT_SYSINFO_EHDR(33)=0x7fff6c86b000 | | | | |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | | | | |
2ec8: environ[2]=(nil) | | | | |
2ec0: environ[1]=0x7fff6c844fe2 ------------------|-+ | | |
2eb8: environ[0]=0x7fff6c844fd8 ------------------+ | | | environ
2eb0: argv[3]=(nil) | | |
2ea8: argv[2]=0x7fff6c844fd4 ---------------------------|-|-+
2ea0: argv[1]=0x7fff6c844fd0 ---------------------------|-+
2e98: argv[0]=0x7fff6c844fcb ---------------------------+
0x7fff6c842e90: argc=3 environ - argv - argc
<LOWEST ADDR> <TOP OF STACK>
||
STACK GROWS ||
\/
------------------ see https://www.sco.com/developers/devspecs/abi386-4.pdf pg 36 for why:
MAIN STACK FRAME argc=3 argc (8 bytes)
argv[2]=...
argv[1]=...
argv[0]=... argv (each ptr 8 bytes)
------------------
<RSP register> asm %RSP
So typically the main function is passed argv & argc on the stack as arguments, and can also use environ. So we could attempt to find argv / argc if we had the environ symbol:
void* env_minus = environ - ((sizeof(char*) * (argc+1)));
printf("environ -argv - argc: %p\n", env_minus);
printf(" argc: %d\n", *(int*)env_minus);
But with nostartfiles we don't have environ either, so this won't work. Instead we'll have to manually reference the RSP.
we can try ad do that by declaring a local var, then grabbing it's address with & to get the current RSP. Then we can skip backwards to find argv in the stack. Based on he above diagram, argv[0] should be rsp+0x08, after argc
int dummy;
long *sp = (long *)&dummy;
char* argv0 = sp+0x08;
printf("%s\n", argv0);
If run this quicky segfaults:
[~/synactiv]$ ./printself
[1] 30320 segmentation fault (core dumped) ./printself
Let's run in GDB to analyse:
$ gdb -ex run ./printself
breakpoint encountered:
0x401023 <_start+4>: sub rsp,0x28
=> 0x401027 <_start+8>: mov rax,QWORD PTR fs:0x28
0x401030 <_start+17>: mov QWORD PTR [rsp+0x18],rax
This shows our crash occurs here. My memory's rusty and I'm not immediately familiar with this instruction, so I turn to an LLM. Turns out this is a common function prologue instruction that saves the stack canary! (https://cseweb.ucsd.edu/~efernandes/teaching/res/how-canaries-work.pdf) It's clearly been a while since I did any binary challenges or I would have recognised it.
Basically this code grabs a 64 bit value from the Thread Local Storage area, denoted by "FS". The TLS holds some per-thread global variables, basically a space separate from the stack for consistently needed variables that are tied to each stack. This includes stack canaries! So whenever a function starts, it grabs the stack canary from TLS+0x28, and places it on the stack.
But because we're skipping the standard ELF startup with nostartfiles we're skipping the part that initialises the TLS. So the code is trying to de-reference a non existent TLS. The simplest way to fix this error is to compile without stack canaries. So we add -fno-stack-protector to our compiler flags, to remove this. This will have the added bonus of removing some more code we don't need, hopefully making the binary even smaller.
# With stack canary
$ musl-gcc -g3 -O0 -static -nostartfiles -static printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 36344 Dec 6 18:21 printself
# Without stack canary
$ musl-gcc -fno-stack-protector -fomit-frame-pointer -g3 -O0 -static -nostartfiles -static printself.c -o printself; ls -l printself
-rwxrwxr-x 1 hendo hendo 36320 Dec 6 18:22 printself
note that here I'm not using Os or stripping, and I'm adding debug data with g3, so sizes are big, but we can still see the difference between with and without the stack canary
So by omitting the canary we save another... 24 bytes xD basically nothign. Now if we disassemble the start of _start, we no longer see the canary initialisation :)
0x000000000040101f <+0>: endbr64
0x0000000000401023 <+4>: sub rsp,0x18
0x0000000000401027 <+8>: mov QWORD PTR [rsp+0x8],0x0
0x0000000000401030 <+17>: lea rax,[rsp+0x4]
0x0000000000401035 <+22>: mov QWORD PTR [rsp+0x8],rax
0x000000000040103a <+27>: mov edi,0x0
However, we still segfault. And in GDB we see it's the exact same instruction (placing the stack canary) that crashes, but this time it's in the open64 function.
[-------------------------------------code-------------------------------------]
0x4011c7 <open64+7>: mov r10,rdi
0x4011ca <open64+10>: sub rsp,0x50
0x4011ce <open64+14>: mov QWORD PTR [rsp+0x30],rdx
=> 0x4011d3 <open64+19>: mov rax,QWORD PTR fs:0x28
0x4011dc <open64+28>: mov QWORD PTR [rsp+0x18],rax
0x4011e1 <open64+33>: xor eax,eax
0x4011e3 <open64+35>: and esi,0x40
0x4011e6 <open64+38>: jne 0x401240 <open64+128>
[------------------------------------stack-------------------------------------]
So although our function works fine, the musl libc functions still expect TLS to be initialised correctly. This is a pretty heavy hint from the compiler that it doesn't like what we're doing. This basically means that if we want to continue along this path: using standard libraries & nostartfiles we're just going to have to fight the compiler more and more. We'll start really pushing the boundaries of what's supported. Now this is what this challenge is about, but from experience this is going to be problematic.
So instead of trying to hack musl-libc into working without a startup routine, it's better to actually write code that doesn't use the library functions at all. This isn't going to be super straightforward, but is pretty doable. Let's think about what our code does:
- reads an address from the stack, this is our filename
- opens a file using the filename
- reads the file
- prints the file to stdout
These are actually quite simple UNIX / x86 operations, pretty much the most common syscalls: open and write. So writing this in assembly isn't going to be as easy as the library functions, but is fairly simple.
So we'll call this the end of attempt 3, and start a new approach.
Attempt 4
Right, so our new attempt is going to perform the same functions, but in assembly, without the use of any library functions.
The code we're looking to emulate is:
void _start() {
int dummy;
long *sp = (long*) &dummy;
char* argv0 = sp+0x08;
int fd = open(argv0, 0);
write(1, argv0, strlen(argv0));
write(1, "\n", 1);
off_t size = lseek(fd, 0, SEEK_END);
lseek(fd, 0, SEEK_SET);
// assert(size<MAXSIZE);
char buf[MAXSIZE] = {0};
read(fd, buf, size);
write(1, buf, size);
exit(0);
As a reminder of what this does:
- read argv0 from stack, a char* pointing to our filename
- open the file and measure it's size with lseek
- read the file contents to buf
- print buf to stdout
- exit with error code 0
It's possible to embed assembly in C and compile with gcc etc, but tbh if we're writing in asm might as well skip the middle man and use the low level compilers. This has the added benefit of stripping away all the gunk the compilers add, when we're done we're going to be working with some real tiny binaries.
Let's write a super simple hello world asm and compile it
code:
section .data
msg db "Hello, World!", 10 ; string + newline (10 = '\n')
len equ $ - msg ; length = current position - start of msg
section .text
global _start
_start:
; sys_write(fd, buf, count)
mov rax, 1 ; syscall number: write
mov rdi, 1 ; fd: stdout
mov rsi, msg ; buf: pointer to string
mov rdx, len ; count: string length
syscall
; sys_exit(code)
mov rax, 60 ; syscall number: exit
xor rdi, rdi ; exit code: 0
syscall
Compile:
nasm -f elf64 printself.asm -o printself.o
ld printself.o -o printself
rm printself.o
ls -l printself
./printself
-rwxrwxr-x 1 hendo hendo 8920 Dec 6 18:46 printself
Hello, World!
Ok, so our previous smallest ELF was 26848, and an example nasm program stands at 8920 bytes, so this is a good indication this is the right path to go down.
Now let's write our full asm for printself. I'm going to "cheat" and use an LLM to do this, as I feel I've spent enough of life writing assembly code.
section .bss
buf resb 10000 ; buffer for file contents
section .text
global _start
_start:
; argv[0] is at [rsp+8] after argc at [rsp]
mov rdi, [rsp+8] ; rdi = argv[0] (filename)
; sys_open(filename, O_RDONLY, 0)
mov rax, 2 ; syscall: open
xor rsi, rsi ; flags: O_RDONLY = 0
xor rdx, rdx ; mode: 0
syscall
mov r12, rax ; save fd in r12
; sys_lseek(fd, 0, SEEK_END) to get file size
mov rax, 8 ; syscall: lseek
mov rdi, r12 ; fd
xor rsi, rsi ; offset: 0
mov rdx, 2 ; whence: SEEK_END
syscall
mov r13, rax ; save file size in r13
; sys_lseek(fd, 0, SEEK_SET) to rewind to start
mov rax, 8 ; syscall: lseek
mov rdi, r12 ; fd
xor rsi, rsi ; offset: 0
xor rdx, rdx ; whence: SEEK_SET
syscall
; sys_read(fd, buf, size)
mov rax, 0 ; syscall: read
mov rdi, r12 ; fd
mov rsi, buf ; buffer
mov rdx, r13 ; count: file size
syscall
; sys_close(fd)
mov rax, 3 ; syscall: close
mov rdi, r12 ; fd
syscall
; sys_write(stdout, buf, size)
mov rax, 1 ; syscall: write
mov rdi, 1 ; fd: stdout
mov rsi, buf ; buffer
mov rdx, r13 ; count: file size
syscall
; sys_exit(0)
mov rax, 60 ; syscall: exit
xor rdi, rdi ; code: 0
syscall
In fact this has an even smaller footprint than the previous asm. Not super sure why but maybe the absence of any strings.
ls -l printself
-rwxrwxr-x 1 hendo hendo 4912 Dec 6 18:50 printself
Now let's see if it actually works:
[~/synactiv]$ ./printself > out; cmp printself out
[~/synactiv]$ echo $?
0
Nice! a ~5kb binary that prints itself. Now let's play around with strip to see if we can shave any more bytes out of it:
[~/synactiv]$ strip --strip-all printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 4504 Dec 6 18:53 printself
Okay, yep, strip managed to find a couple of hundred redundant bytes somewhere xD. This is faaairly small. Not really competitive level, but probably as nice as we're going to get without manually carving up the file.
Now let's use mirror.py again, and check if it passes the tests:
[~/synactiv]$ python3 mirror.py printself printself.m
Wrote 9008 bytes to printself.m
[~/synactiv]$ ./test.sh printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 9008
This is the first solution I submitted to the challenge, although I know we can do much, much better :)
At this point I looked at the leaderboard on the synactiv blog site, and there are some pretty hardcore binary CTF people up there, so chances are they've already gone a lot further than me.
#1 ioonag - 05/12/2025 12 :52 AM
#2 doegox - 05/12/2025 12:16 AM
#3 itszn - 03/12/2025 1 :28 PM
#4 Leon - 05/12/2025 4:47 PM
#5 Cortex - 02/12/2025 8:45 PM
#6 CupOfCoffee - 05/12/2025 8:01 AM
#7 Nicolas - 04/12/2025 4:28 PM
#8 Youssef - 04/12/2025 8:57PM
#9 Swissky - 05/12/2025 2:54PM
Attempt 5
Now we've gone about as far as I think standard tools and the naive byte mirror strategy will take us, so let's go deeper. First off, let's just take a look at the binary we've written, as hex:
[~/synactiv]$ xxd printself
00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 3e00 0100 0000 0010 4000 0000 0000 ..>.......@.....
00000020: 4000 0000 0000 0000 9810 0000 0000 0000 @...............
00000030: 0000 0000 4000 3800 0300 4000 0400 0300 ....@.8...@.....
00000040: 0100 0000 0400 0000 0000 0000 0000 0000 ................
00000050: 0000 4000 0000 0000 0000 4000 0000 0000 ..@.......@.....
00000060: e800 0000 0000 0000 e800 0000 0000 0000 ................
00000070: 0010 0000 0000 0000 0100 0000 0500 0000 ................
00000080: 0010 0000 0000 0000 0010 4000 0000 0000 ..........@.....
00000090: 0010 4000 0000 0000 7e00 0000 0000 0000 ..@.....~.......
000000a0: 7e00 0000 0000 0000 0010 0000 0000 0000 ~...............
000000b0: 0100 0000 0600 0000 0000 0000 0000 0000 ................
000000c0: 0020 4000 0000 0000 0020 4000 0000 0000 . @...... @.....
000000d0: 0000 0000 0000 0000 1027 0000 0000 0000 .........'......
000000e0: 0010 0000 0000 0000 0000 0000 0000 0000 ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000100: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000120: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000140: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000150: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000160: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000170: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000190: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000200: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000210: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000220: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000230: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000250: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000260: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000270: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000280: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000290: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000002f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000310: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000320: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000330: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000340: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000360: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000370: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000380: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000390: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000003f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000400: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000410: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000420: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000470: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000480: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000490: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000500: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000510: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000520: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000570: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000580: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000590: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000005f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000600: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000610: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000620: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000630: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000640: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000650: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000660: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000670: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000680: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000690: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000006f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000700: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000710: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000720: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000730: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000740: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000750: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000760: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000770: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000780: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000790: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000007f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000800: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000810: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000820: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000830: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000840: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000850: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000860: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000870: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000880: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000890: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000008f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000900: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000910: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000920: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000930: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000940: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000950: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000960: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000970: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000980: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000990: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000009f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000a90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000aa0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ab0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ac0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ad0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ae0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000af0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000b90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ba0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000bb0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000bc0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000bd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000be0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000bf0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000c90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ca0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000cb0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000cc0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000cd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ce0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000cf0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000d90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000da0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000db0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000dc0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000dd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000de0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000df0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000e90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ea0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000eb0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ec0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ed0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ee0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ef0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f10: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f20: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f30: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f40: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f50: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f60: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f70: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f80: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000f90: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000fa0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000fb0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000fc0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000fd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000fe0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000ff0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00001000: 488b 7c24 08b8 0200 0000 4831 f648 31d2 H.|\$......H1.H1.
00001010: 0f05 4989 c4b8 0800 0000 4c89 e748 31f6 ..I.......L..H1.
00001020: ba02 0000 000f 0549 89c5 b808 0000 004c .......I.......L
00001030: 89e7 4831 f648 31d2 0f05 b800 0000 004c ..H1.H1........L
00001040: 89e7 48be 0020 4000 0000 0000 4c89 ea0f ..H.. @.....L...
00001050: 05b8 0300 0000 4c89 e70f 05b8 0100 0000 ......L.........
00001060: bf01 0000 0048 be00 2040 0000 0000 004c .....H.. @.....L
00001070: 89ea 0f05 b83c 0000 0048 31ff 0f05 002e .....<...H1.....
00001080: 7368 7374 7274 6162 002e 7465 7874 002e shstrtab..text..
00001090: 6273 7300 0000 0000 0000 0000 0000 0000 bss.............
000010a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000010b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000010c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000010d0: 0000 0000 0000 0000 0b00 0000 0100 0000 ................
000010e0: 0600 0000 0000 0000 0010 4000 0000 0000 ..........@.....
000010f0: 0010 0000 0000 0000 7e00 0000 0000 0000 ........~.......
00001100: 0000 0000 0000 0000 1000 0000 0000 0000 ................
00001110: 0000 0000 0000 0000 1100 0000 0800 0000 ................
00001120: 0300 0000 0000 0000 0020 4000 0000 0000 ......... @.....
00001130: 0020 0000 0000 0000 1027 0000 0000 0000 . .......'......
00001140: 0000 0000 0000 0000 0400 0000 0000 0000 ................
00001150: 0000 0000 0000 0000 0100 0000 0300 0000 ................
00001160: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00001170: 7e10 0000 0000 0000 1600 0000 0000 0000 ~...............
00001180: 0000 0000 0000 0000 0100 0000 0000 0000 ................
00001190: 0000 0000 0000 0000 ........
wow that's an awful lot of 0x00's (96% of the binary is 0x00). THat just feels like wasted space...
But we can't just naively start removing it, can we?
~/synactiv]$ cat printself | head -c4000 > b2; chmod +x b2; ./b2
[1] 73595 bus error (core dumped) ./b2
yeah that won't work. To actually see what each byte of data in the file is linked to, we need to start looking at the sections. Sections are how Linux translates from ELF-> program memory, as per this diagram:
ELF FILE (on disk) MEMORY (at runtime)
───────────────── ───────────────────
┌──────────────────┐
│ ELF Header │
├──────────────────┤
│ Program Headers │──────────────────────────┐
│ (segments) │ │
├──────────────────┤ ▼
│ Section Headers │ ┌─────────────────────┐
│ (optional) │ │ Segment 1 (PT_LOAD) │
├──────────────────┤ │ r-x (executable) │
│ │ │ │
│ .text │─────────────▶│ .text │
│ │ │ .rodata │
│ .rodata │─────────────▶│ │
│ │ ├─────────────────────┤
├──────────────────┤ │ Segment 2 (PT_LOAD) │
│ │ │ rw- (read/write) │
│ .data │─────────────▶│ │
│ │ │ .data │
├──────────────────┤ │ .bss (zeroed) │◀─┐
│ .bss │ │ │ │
│ (size only, │──────────────┴─────────────────────┘ │
│ no bytes) │ │
└──────────────────┘ memsz > filesz = bss ─────────┘
Readelf will show us the program headers, that define binary sections:
[~/synactiv]$ readelf -eW printself
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: 0x401000
Start of program headers: 64 (bytes into file)
Start of section headers: 4536 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 3
Size of section headers: 64 (bytes)
Number of section headers: 6
Section header string table index: 5
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 0000000000000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 0000000000401000 001000 000088 00 AX 0 0 16
[ 2] .bss NOBITS 0000000000402000 002000 002710 00 WA 0 0 4
[ 3] .symtab SYMTAB 0000000000000000 001088 0000d8 18 4 5 8
[ 4] .strtab STRTAB 0000000000000000 001160 00002b 00 0 0 1
[ 5] .shstrtab STRTAB 0000000000000000 00118b 000026 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x000000 0x0000000000400000 0x0000000000400000 0x0000e8 0x0000e8 R 0x1000
LOAD 0x001000 0x0000000000401000 0x0000000000401000 0x000088 0x000088 R E 0x1000
LOAD 0x000000 0x0000000000402000 0x0000000000402000 0x000000 0x002710 RW 0x1000
Section to Segment mapping:
Segment Sections...
00
01 .text
02 .bss
This tells us there are 4 sections, but it's a bit clear where the space in our ELF comes from. If we look at the FileSiz volumes, the ELF is saying there's only (0x88 + 0xe8 + the header size) of useful data here (that's a bit of an oversimplifcation). So this confirms: our code is very minimal, but there's a lot of bloat in the file from somewhere else. So let's find where that comes from.
I'll use hobbits https://github.com/Mahlet-Inc/hobbits/releases, a nice program for visualising binary data. Specifically it supports kitai structs, https://doc.kaitai.io/, including a definition for ELF. if you want a simpler online version https://elfy.io/ has a nice elf analyser, but isn't as good at visualisation. This kind of confirms what we knew: there's a relatively small amount of useful data in the binary, and most of the data is blank space between sections:
So why is there a bunch of space?? well one thing that jumps out is that the space looks very similar to 4096 bytes long, that's a common value in ELF, as it's the standard pagesize. That means an awful lot of stuff that involves memory / file reading aligns chunks of data with page boundaries for convinience, I think it has something to do with quick memory operations or something. But that's actively hurting us by artificially bulking the file size, so let's see if we can ditch it. again, this was new to me, but we can instruct ld to not page align the ELF sections with the -n flag.
[~/synactiv]$ nasm -f elf64 printself.asm -o printself.o
[~/synactiv]$ ld -n printself.o -o printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 944 Dec 6 19:56 printself
[~/synactiv]$ strip --strip-all printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 536 Dec 6 19:58 printself
Boom, we're down to almost half a KB!
now let's take a look at the binary again:
[~/synactiv]$ readelf -eW printself
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: 280 (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: 4
Section header string table index: 3
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 0000000000000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 0000000000400078 000078 000088 00 AX 0 0 1
[ 2] .bss NOBITS 0000000000401100 000100 002710 00 WA 0 0 4
[ 3] .shstrtab STRTAB 0000000000000000 000100 000016 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x000078 0x0000000000400078 0x0000000000400078 0x000088 0x003798 RWE 0x4
[~/synactiv]$ xxd printself
00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 3e00 0100 0000 7800 4000 0000 0000 ..>.....x.@.....
00000020: 4000 0000 0000 0000 1801 0000 0000 0000 @...............
00000030: 0000 0000 4000 3800 0100 4000 0400 0300 ....@.8...@.....
00000040: 0100 0000 0700 0000 7800 0000 0000 0000 ........x.......
00000050: 7800 4000 0000 0000 7800 4000 0000 0000 x.@.....x.@.....
00000060: 8800 0000 0000 0000 9837 0000 0000 0000 .........7......
00000070: 0400 0000 0000 0000 488b 7c24 0848 81ec ........H.|$.H..
00000080: 1027 0000 4989 e7b8 0200 0000 4831 f648 .'..I.......H1.H
00000090: 31d2 0f05 4989 c4b8 0800 0000 4c89 e748 1...I.......L..H
000000a0: 31f6 ba02 0000 000f 0549 89c5 b808 0000 1........I......
000000b0: 004c 89e7 4831 f648 31d2 0f05 b800 0000 .L..H1.H1.......
000000c0: 004c 89e7 48be 0011 4000 0000 0000 4c89 .L..H...@.....L.
000000d0: ea0f 05b8 0300 0000 4c89 e70f 05b8 0100 ........L.......
000000e0: 0000 bf01 0000 0048 be00 1140 0000 0000 .......H...@....
000000f0: 004c 89ea 0f05 b83c 0000 0048 31ff 0f05 .L.....<...H1...
00000100: 002e 7368 7374 7274 6162 002e 7465 7874 ..shstrtab..text
00000110: 002e 6273 7300 0000 0000 0000 0000 0000 ..bss...........
00000120: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000140: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000150: 0000 0000 0000 0000 0b00 0000 0100 0000 ................
00000160: 0600 0000 0000 0000 7800 4000 0000 0000 ........x.@.....
00000170: 7800 0000 0000 0000 8800 0000 0000 0000 x...............
00000180: 0000 0000 0000 0000 0100 0000 0000 0000 ................
00000190: 0000 0000 0000 0000 1100 0000 0800 0000 ................
000001a0: 0300 0000 0000 0000 0011 4000 0000 0000 ..........@.....
000001b0: 0001 0000 0000 0000 1027 0000 0000 0000 .........'......
000001c0: 0000 0000 0000 0000 0400 0000 0000 0000 ................
000001d0: 0000 0000 0000 0000 0100 0000 0300 0000 ................
000001e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000001f0: 0001 0000 0000 0000 1600 0000 0000 0000 ................
00000200: 0000 0000 0000 0000 0100 0000 0000 0000 ................
00000210: 0000 0000 0000 0000 ........
Hmm, while we're pretty minimal, I still see a lot of 0's in there. But let's leave that for later. This can be the end of our attempt 5, we'll just quickly use the mirror tool and test:
$ python3 mirror.py printself printself.m; ./test.sh printself.m
Wrote 1072 bytes to printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 1072
Attempt 6
Okay, so our current attempt is nice and minimal, but I reckon there's more we can do :)
Specifically, there are still a bunch of 0x00 buffers with "dead space" in them. But now these are within legitimate sections and not after them. Let's take a look at where they are in hobbits:
- 7 bytes of 0x00 before the header.header_offset, and after header.entry_point.
- 4 bytes in the lower bits of program_headers[0].filesize
an entire 64 bytes of 0x00 in section header 0
8 bytes of 0x00 in each section header flags, addr (16 bytes x )
What immediately jumps out is that a bunch of space is being taken up in the lower bits of longs etc. So what about if we compile as a 32 bit ELF, reducing the sizes. lets change the x64 code to x86 and then comile as an x86 binary:
nasm -f elf32 printself.asm -o printself.o
ld -m elf_i386 -n printself.o -o printself
[~/synactiv]$ ./compile.sh
-rwxrwxr-x 1 hendo hendo 336 Dec 6 20:22 printself
Nice! a couple hundred bytes shaved off.
We also noticed that section[0] appeared to be a bunch of 0's:
Can we just get rid of this? This showed up in readelf -SW output as a "NULL" section, which is a bit odd:
[ 0] NULL 0000000000000000 000000 000000 00 0 0 0
well attempting to remove with various strip / objcopy cmds doesn't work:
[~/synactiv]$ readelf -SW printself
There are 3 section headers, starting at offset 0xd8:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 08048060 000060 000067 00 AX 0 0 16
[ 2] .shstrtab STRTAB 00000000 0000c7 000011 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
p (processor specific)
[~/synactiv]$ strip -R .NULL printself
[~/synactiv]$ strip -R "" printself
[~/synactiv]$ strip -R "." printself
[~/synactiv]$ strip -R NULL printself
[~/synactiv]$ objcopy --remove-section=.null printself
[~/synactiv]$ objcopy --remove-section=.NULL printself
[~/synactiv]$ objcopy --remove-section=. printself
[~/synactiv]$ objcopy --remove-section='' printself
[~/synactiv]$ readelf -SW printself
There are 3 section headers, starting at offset 0xd8:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 08048060 000060 000067 00 AX 0 0 16
[ 2] .shstrtab STRTAB 00000000 0000c7 000011 00 0 0 1
Key to Flags:
Upon further researching what a NULL section is, turns out it's required by the ELF spec: https://stackoverflow.com/questions/26812142/what-is-the-use-of-the-sht-null-section-in-elf Huh. That spec is here: the ABI, https://www.sco.com/developers/devspecs/abi386-4.pdf. I thought we'd get round to including it in this post eventually. I had a brief rattle through but couldn't pin down the section it mandates the null section header, but apparently the info is in a separate addendum: https://www.sco.com/developers/gabi/2003-12-17/ch4.sheader.html.
Either way it's not a normal section. We can try and remove it, and one way of doing so would be to either manually carve the file (ew), or use a library like https://github.com/eliben/pyelftools to parse and dynamically alter the file. But turns out there's actually a pre-existing tool that does this: sstrip from ElfKickers: https://github.com/BR903/ELFkickers/tree/master/sstrip. This is in fact made for exactly this scenario, weird spec-breaking challenges. sstrip is like strip, but goes even further in editing the file to reduce size while technically being runnable. sstrip removes the entire section header table, which isn't actually used by the loader (the loader only uses the program headers, as that's where the info on runtime memory is found). So let's use sstrip to remove the unneeded section headers:
[~/synactiv]$ ./ELFkickers/sstrip/sstrip printself
[~/synactiv]$ ls -l printself
-rwxrwxr-x 1 hendo hendo 199 Dec 6 23:52 printself
[~/synactiv]$ ./printself
ELF`44 (```gg�\$��'��1�1�̀�Ƹ��1ɺ̀�Ÿ��1�1�̀������̀���̀������̀�1�̀%
Ok, now we're down to 199 bytes!
Let's dbl check it still passes tests, and sstrip hasn't broken anything:
$ python3 mirror.py printself printself.m; ./test.sh printself.m
Wrote 398 bytes to printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 398
Okay, I think that's good enough for this attempt :). We went from a start of 536 bytes to 199, so a hlaving in size. Remember that the original size was 29000 bytes!
Attempt 7
Right, let's take another look at our binary from attempt 6:
$ readelf -eW printself
ELF Header:
Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Intel 80386
Version: 0x1
Entry point address: 0x8048060
Start of program headers: 52 (bytes into file)
Start of section headers: 0 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 1
Size of section headers: 40 (bytes)
Number of section headers: 0
Section header string table index: 0
There are no sections in this file.
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x000060 0x08048060 0x08048060 0x00067 0x00067 R E 0x10
$ xxd printself
00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 0300 0100 0000 6080 0408 3400 0000 ........`...4...
00000020: 0000 0000 0000 0000 3400 2000 0100 2800 ........4. ...(.
00000030: 0000 0000 0100 0000 6000 0000 6080 0408 ........`...`...
00000040: 6080 0408 6700 0000 6700 0000 0500 0000 `...g...g.......
00000050: 1000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 8b5c 2404 81ec 1027 0000 89e7 b805 0000 .\$....'........
00000070: 0031 c931 d2cd 8089 c6b8 1300 0000 89f3 .1.1............
00000080: 31c9 ba02 0000 00cd 8089 c5b8 1300 0000 1...............
00000090: 89f3 31c9 31d2 cd80 b803 0000 0089 f389 ..1.1...........
000000a0: f989 eacd 80b8 0600 0000 89f3 cd80 b804 ................
000000b0: 0000 00bb 0100 0000 89f9 89ea cd80 b801 ................
000000c0: 0000 0031 dbcd 80 ...1...
So all those wasteful 0's from previous attempts are gone, and readelf doesn't see the section headers, just the 1 load program header. is there even anything else we can do???
Well we've now made the binary very small. There are probably ways to make it even smaller, by doing crazy stuff like putting code inside fields of the header (which won't work here bc our code is longer). So there are 2 things that occur to me:
- make the code more efficient
- make the mirroring algorithm more efficient.
Let's start by looking at the code:
- we run some instructions to measure the filesize with lseek, how about we just hard-code that size.
- we can cheat and not close the file, this won't cause segfaults or a non0 exit code, it's just a bit rude to the OS
-
mov REG VALcan be changed topush VAL;pop REG, saving a byte (5 bytes -> 4)
Annoyingly we now have to hardcode the file size, which we dont know in advance. This is fine, it'll compile fine with the wrong value, we just need to fix it before running for a test.
With our edits, here is the new code, and the new size:
BITS 32
%define FILESIZE 330
section .text
global _start
_start:
; argv[0] is at [esp+4] after argc at [esp]
mov ebx, [esp+4] ; ebx = argv[0] (filename)
sub esp, 10000 ; allocate buffer on stack
mov edi, esp ; edi = pointer to buffer (was r15)
; sys_open(filename, O_RDONLY, 0)
push 5
pop eax ; syscall: open (5 on x86, not 2)
xor ecx, ecx ; flags: O_RDONLY = 0
xor edx, edx ; mode: 0
int 0x80
mov esi, eax ; save fd in esi (was r12)
; sys_read(fd, buf, size)
mov eax, 3 ; syscall: read (3 on x86, not 0)
mov ebx, esi ; fd
mov ecx, edi ; buffer
push FILESIZE
pop edx ; count: file size
int 0x80
; sys_write(stdout, buf, size)
mov eax, 4 ; syscall: write (4 on x86, not 1)
mov ebx, 1 ; fd: stdout
int 0x80
; sys_exit(0)
mov eax, 1 ; syscall: exit (1 on x86, not 60)
dec ebx ; code: 0
int 0x80
[~/synactiv]$ ./compile.sh
-rwxrwxr-x 1 hendo hendo 156 Dec 7 00:23 printself
So we've managed to take off about 40 bytes :)
In fact we can also live dangerously, and save another 4 bytes, by assuming that registers will be 0'd and removing the xor instructions:
push 5
pop eax ; syscall: open (5 on x86, not 2)
; xor ecx, ecx # We don't need this
; xor edx, edx # We don't need this
int 0x80
mov esi, eax
let's check again that this works:
[~/synactiv]$ python3 mirror.py printself printself.m; ./test.sh printself.m
Wrote 300 bytes to printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 300
cool, it does, and here's our final asm, standing at 150 bytes for our single binary:
BITS 32
%define FILESIZE 300
section .text
global _start
_start:
; argv[0] is at [esp+4] after argc at [esp]
pop eax ; 1 byte - discard argc
pop ebx ; 1 byte - get argv[0]
sub esp, 10000 ; allocate buffer on stack
mov edi, esp ; edi = pointer to buffer (was r15)
; sys_open(filename, O_RDONLY, 0)
push 5
pop eax ; syscall: open (5 on x86, not 2)
; xor ecx, ecx ; flags: O_RDONLY = 0
; xor edx, edx ; mode: 0
int 0x80
mov esi, eax ; save fd in esi (was r12)
; sys_read(fd, buf, size)
mov eax, 3 ; syscall: read (3 on x86, not 0)
mov ebx, esi ; fd
mov ecx, edi ; buffer
push FILESIZE
pop edx ; count: file size
int 0x80
; sys_write(stdout, buf, size)
mov eax, 4 ; syscall: write (4 on x86, not 1)
mov ebx, 1 ; fd: stdout
int 0x80
; sys_exit(0)
mov eax, 1 ; syscall: exit (1 on x86, not 60)
dec ebx ; code: 0
int 0x80
Attempt 8: making mirror more efficient
Now we've really really shaved as much as I think we can from the ELF file itself, it's time to shift focus onto our palindrome algorithm. At the moment we're doing the most naive thing and just appending the reversed binary to the end.
But depending on the structure of the binary we can find more efficient solutions. For example consider these 2 words: both are length 7, but the shortest palindrome you can make is dependent on the overlap between the end of the word:
Can we harness this with our palindrome algorithm?
looking at the last 31 bytes of the file, is it a palindrome?
\[~/synactiv]\$ tail -c 32 printself | xxd
00000000: 89f3 89f9 682c 0100 005a cd80 b804 0000 ....h,...Z......
00000010: 00bb 0100 0000 cd80 b801 0000 004b cd80 .............K..
err no not really sadly. Could we make it one?? also not really: this is our actual code, so modifying this is going to go badly, as we'll effectively be inserting junk CPU instructions. Let's look in hobbits again to see if there are any patterns we can take advantage of:
Hmmm not really, we're down to a super simple ELF, literally just a header and the code. But I do see a sneaky remaining bunch of 0's just before the code. Now this is probably because ELF doesn't want to be anything less than 16 byte aligned, but lets hav a go anyway. The following python script will manually carve that padding out of the file, and fix the entry point & program headers:
#!/usr/bin/env python3
import sys
with open(sys.argv[1], 'rb') as f:
data = f.read(150)
head = data[:84]
tail = data[96:]
print(tail)
with open(sys.argv[2], 'wb') as f:
f.write(head + tail)
SHIFT = 12
with open(sys.argv[2], 'rb') as f:
data = bytearray(f.read())
entry = int.from_bytes(data[0x18:0x1c], 'little')
entry -= SHIFT
data[0x18:0x1c] = entry.to_bytes(4, 'little')
# Program headers start at e_phoff (offset 0x1c)
phoff = int.from_bytes(data[0x1c:0x20], 'little')
phentsize = int.from_bytes(data[0x2a:0x2c], 'little')
phnum = int.from_bytes(data[0x2c:0x2e], 'little')
for i in range(phnum):
ph = phoff + i * phentsize
p_type = int.from_bytes(data[ph:ph+4], 'little')
if p_type == 1: # PT_LOAD
# p_offset at ph+0x04 (4 bytes)
p_offset = int.from_bytes(data[ph+0x04:ph+0x08], 'little')
p_offset -= SHIFT
data[ph+0x04:ph+0x08] = p_offset.to_bytes(4, 'little')
# p_vaddr at ph+0x08
p_vaddr = int.from_bytes(data[ph+0x08:ph+0x0c], 'little')
p_vaddr -= SHIFT
data[ph+0x08:ph+0x0c] = p_vaddr.to_bytes(4, 'little')
# p_align at ph+0x1c
data[ph+0x1c:ph+0x20] = (1).to_bytes(4, 'little')
with open(sys.argv[2], 'wb') as f:
f.write(data)
print("Done")
[~/synactiv]$ python3 snip.py printself printself2
b"X[\x81\xec\x10'\x00\x00\x89\xe7j\x05X\xcd\x80\x89\xc6\xb8\x03\x00\x00\x00\x89\xf3\x89\xf9h,\x01\x00\x00Z\xcd\x80\xb8\x04\x00\x00\x00\xbb\x01\x00\x00\x00\xcd\x80\xb8\x01\x00\x00\x00K\xcd\x80"
Done
[~/synactiv]$ ./printself2
ELFT44 (TT`66X[��'��jX̀�Ƹ���h,Z̀��̀�K̀%
[~/synactiv]$ ls -l printself2
-rwxrwxr-x 1 hendo hendo 138 Dec 7 01:24 printself2
[~/synactiv]$ xxd printself2
00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 0300 0100 0000 5480 0408 3400 0000 ........T...4...
00000020: 0000 0000 0000 0000 3400 2000 0100 2800 ........4. ...(.
00000030: 0000 0000 0100 0000 5400 0000 5480 0408 ........T...T...
00000040: 6080 0408 3600 0000 3600 0000 0500 0000 `...6...6.......
00000050: 0100 0000 585b 81ec 1027 0000 89e7 6a05 ....X[...'....j.
00000060: 58cd 8089 c6b8 0300 0000 89f3 89f9 682c X.............h,
00000070: 0100 005a cd80 b804 0000 00bb 0100 0000 ...Z............
00000080: cd80 b801 0000 004b cd80 .......K..
Still passes the test!
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 276
Now let's make 1 little update to our mirror.py, just to not duplicate the very last byte (see the wabbajack example earlier)
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 275
haha we've shaved off exactly 1 byte xD still it's something. I'm now thinking this is as good as this will get, so time for another submission to the challenge authors :)
Attempt 8.5: Going lower
I submitted my solution of 275 bytes on Sunday afternoon. On Monday I checked the Synactiv challenge website, and found that I was on the leaderboard, in last place xD This inspired (read: annoyed) me to try and do even better. So I read some of the classic ELF GOLF posts (something I originally aimed to avoid as I wanted to learn from scratch), and found some other ways to reduce the size. Specifically I found some ways to optimize the code:
- this blog post: https://www.nathanotterness.com/2021/10/tiny_elf_modernized.html points out some more saving we can do, specifically using x86 short registers that just target lower bits (ie
alvseax) results in shorter assembly instuctions. Most of our variables are < 255, so this works for everything except the pointer to our buf - we can drop
sub esp, 10000entirely, we overwrite the stack but doesnt matter :) -
mov al, 3can bcomedec alsince we know al will be 4, saving exactly 1 byte
With these tricks our asm is now this:
BITS 32
%define FILESIZE 237
section .text
global _start
_start:
; argv[0] is at [esp+4] after argc at [esp]
pop eax ; 1 byte - discard argc
pop ebx ; 1 byte - get argv[0]
; sub esp, 10000 ; allocate buffer on stack
mov edi, esp ; edi = pointer to buffer (was r15)
; sys_open(filename, O_RDONLY, 0)
mov al, 5 ; syscall: open (5 on x86, not 2)
; xor ecx, ecx ; flags: O_RDONLY = 0
; xor edx, edx ; mode: 0
int 0x80
mov dl, al ; save fd in esi (was r12)
; sys_read(fd, buf, size)
mov al, 3
mov ebx, edx ; fd
mov ecx, edi ; buffer
push FILESIZE
pop edx ; count: file size
int 0x80
; sys_write(stdout, buf, size)
mov al, 4 ; syscall: write (4 on x86, not 1)
mov bl, 1 ; fd: stdout
int 0x80
; sys_exit(0)
mov al, 1 ; syscall: exit (1 on x86, not 60)
dec ebx ; code: 0
int 0x80
and our file size is 119, becoming a palindrome of length 237. That's 38 bytes saved (approximately 1/7th)
[~/synactiv]$ xxd printself
00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 0300 0100 0000 5480 0408 3400 0000 ........T...4...
00000020: 0000 0000 0000 0000 3400 2000 0100 2800 ........4. ...(.
00000030: 0000 0000 0100 0000 5400 0000 5480 0408 ........T...T...
00000040: 6080 0408 2300 0000 2300 0000 0500 0000 `...#...#.......
00000050: 0100 0000 585b 89e7 b005 cd80 88c2 b003 ....X[..........
00000060: 89d3 89f9 68ed 0000 005a cd80 b004 b301 ....h....Z......
00000070: cd80 b001 4bcd 80 ....K..
But can we go any further??
I read the OG blog post in this area: https://www.muppetlabs.com/~breadbox/software/tiny/teensy.html, that revealed how you can fold the ELF header in on itself. This requires modifying the asm to hardcode the ELF header, which has the added benefit of us not needing to do the snip.py step. I took most of the template from part of the teensy blog post:
BITS 32
; file_load_va: equ 4096 * 40
org 0x00010000
db 0x7F, "ELF" ; e_ident
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dw 2 ; e_type ; p_paddr
dw 3 ; e_machine
dd _start ; e_version ; p_filesz
dd _start ; e_entry ; p_memsz
dd 4 ; e_phoff ; p_flags
mov bl, 42 ; e_shoff ; p_align
xor eax, eax
inc eax ; e_flags
int 0x80
db 0
dw 0x34 ; e_ehsize
dw 0x20 ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
_start:
pop eax ; 1 byte - discard argc
pop ebx ; 1 byte - get argv[0]
mov edi, esp ; 2 bytes edi = pointer to buffer (was r15)
; sys_OPEN
mov al, 5 ; 2 byte
int 0x80 ; 2 bytes
; sys_read(fd, buf, size)
dec al ; 2 bytes
push 4 ; 2 byte
pop ebx ; 1 byte EBX <- fd = 4
mov ecx, edi ; 2 bytes = ECX <- buffer
mov edx, filesize ; 5 bytes count: file size
int 0x80 ; 2 bytes SYSCALL
; sys_write(stdout, buf, size)
mov al, 4 ; 2 bytes syscall: write (4 on x86, not 1)
mov bl, 1 ; 2 bytes fd: stdout
int 0x80 ; 2 bytes
; sys_exit(0)
mov al, 1 ; 2 bytes syscall: exit (1 on x86, not 60)
dec ebx ; 1 byte: EBX <- code: 0
int 0x80
filesize equ $ - $$
I also hard-coded the file descriptor for the read operation to 4, to skip a register read.
Now we're down to a tidy 85 bytes for our binary! and 169 for the palindrome.
$ nasm -f bin printself.asm -o printself; python3 mirror.py printself printself.m; ./test.sh printself.m
Wrote 169 bytes to printself.m
Wrote to flipped.elf
[+] First check passed: binary is a byte-wise palindrome.
[+] Second check passed: binary is a true quine, its output matches itself.
[+] Both checks passed: your binary is a very nice quinindrome!
[+] Your score: 169
I was very happy with this, so made it my next submission.
But then I got an email from the challenge author, saying my submission didn't run correctly? This was odd as it definitely passed tests on my machine. I spent ages trying to debug this, and I realised that the difference between my machine and the official test script, is that the test script uses podman to run the binary, and my script doesn't (I'd skipped his as I figured it didn't make a difference and was an extra barrier to debugging).
So I re-ran the test with podman and got the same result. Still pretty weird, but at least I can reproduce the issue. This was annoying to debug, as I had to get the podman img to install and setup GDB to even get round to debugging. I eventually sorted this and worked to find the issue:
────────────────────────────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────────────────────────────
*EAX 3
EBX 0xffffd7eb ◂— '/app/binary'
ECX 0
EDX 0
EDI 0xffffd2f0 ◂— 0
ESI 0
EBP 0
ESP 0xffffd2f0 ◂— 0
*EIP 0x8048062 ◂— dec al
──────────────────────────────────────────────────────────────────────────────[ DISASM / i386 / set emulate on ]───────────────────────────────────────────────────────────────────────────────
0x8048055 pop ebx EBX => 0xffffd7eb
0x8048056 sub esp, 0x3e8 ESP => 0xffffd2f0 (0xffffd6d8 - 0x3e8)
0x804805c mov edi, esp EDI => 0xffffd2f0 ◂— 0
0x804805e mov al, 5 AL => 5
0x8048060 int 0x80 <SYS_open>
► 0x8048062 dec al AL => 2
0x8048064 push 4
0x8048066 pop ebx EBX => 4
0x8048067 mov ecx, edi ECX => 0xffffd2f0 ◂— 0
0x8048069 mov edx, 0xb5 EDX => 0xb5
0x804806e int 0x80 <SYS_fork>
The FD is wrong xD This shows that EAX: he return of syscall open, is 3, and I'd assumed it was 4.
When I hard-coded the file descriptor, this worked on my native machine, but not in podman. in podman the file-descriptor was 3, not 4. I'm not entirely sure why, but by default file descriptors are inherited from forked process parents, so presumably the podman entrypoint works a bit differently in terms of FDs.
So I fixed this and submitted my solution, with a final quinindrome size of 169.
The end
To track the attempts I made some tables and graphs:
| Attempt no | Palindrome Size (bytes) |
|---|---|
| 1 | 34048 |
| 2 | 26848 |
| 3 | N/A |
| 4 | 9008 |
| 5 | 1072 |
| 6 | 398 |
| 7 | 300 |
| 8 | 169 |
I missed out 8 and 8.5 and couln't be bothered to remake the graph so I collapsed them
The final scoreboard, on 01 Janurary, was this: I came in 21st place out of 25, so not great, but I'm still super happy I gave it a go xD
#1 ioonagioonag - 08/12/2025 10:21 PM
#2 XeR - 17/12/2025 1:58 PM
#3 toby - 12/29/2025 11:41 PM
#4 00BL1X - 30/12/2025 1:02 AM
#5 Leon Noel - 27/12/2025 12:30 AM
#6 doegox - 07/12/2025 2:37 AM
#7 Lion - 12/12/2025 6:41 PM
#8 Swissky - 08/12/2025 6:13 PM
#9 alph4kam - 11/12/2025 7:47 PM
#10 3akev3akev - 19/12/2025 8:43 AM
#11 Nicolas - 12/23/2025 10:16 AM
#12 itszn - 03/12/2025 1 :28 PM
#13 matt - 28/12/2025 11:45 PM
#14 Sk4r - 12/12/2025 12:26 AM
#15 mirism - 12/12/2025 7:46 PM
#16 rick - 29/12/2025 6:02 PM
#17 rl0x01 - 12/16/2025 4:58 PM
#18 Gerfaut - 27/12/2025 10:58 AM
#19 Cortex - 02/12/2025 8:45 PM
#20 Aker - 22/12/2025 7:33 AM
#21 hendo - 09/12/2025 5:49 PM < woooo
#22 n0x - 12/14/2025 2:46 PM
#23 Youssef - 28/12/2025 3:16 PM
#24 CupOfCofffee - 05/12/2025 8:01 AM
#25 Noah - 12/13/2025 5:11 PM
I'm genuinely interested in how the other solutions did better, as I don't see much space in the binary. I suspect they may actually have used 64 bit ELF headers and this trick: https://www.nathanotterness.com/2021/10/tiny_elf_modernized.html, which despite using a larger header, makes binaries smaller by leveraging the gaps in the header to store code. Or maybe there's a clever way to make the mirroring more efficient?