The Teensy Executable Revisited

(or, "Thunderclouds Gather on the Horizon")

On a couple of occasions, people have responded to my original essay with the comment that what I've created by the end isn't really an ELF executable. Rather, it is a file that the Linux kernel, in its current incarnation, happens to mistake for an ELF executable.

It's a fair point. That 45-byte file clearly doesn't conform to numerous requirements of the ELF specification. But can you blame me? How could I have stopped at the point just before I tossed the ELF specification out the window, knowing what might still be possible?

But to satisfy these purists, and the puritan side in all of us, I've created this sequel.

So. We have an executable that we whittled down to 45 bytes. We now want to bring it into rigid conformance with published standards, while still keeping it as small as possible.

The point at which we strayed from straight and narrow path was when we started fiddling with "unused" fields in the ELF header. So let's back up to before that point: BITS 32 org 0x08048000 ehdr: ; Elf32_Ehdr db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsz ; e_ehsize dw phdrsz ; e_phentsize dw 1 ; e_phnum dw 0 ; e_shentsize

dw 0 ; e_shnum dw 0 ; e_shstrndx ehdrsz equ $ - ehdr phdr: ; Elf32_Phdr dd 1 ; p_type dd 0 ; p_offset dd $$ ; p_vaddr dd $$ ; p_paddr dd filesz ; p_filesz dd filesz ; p_memsz dd 5 ; p_flags dd 0x1000 ; p_align phdrsz equ $ - phdr _start: xor eax, eax inc eax mov bl, 42 int 0x80 filesz equ $ - $$

This was our ninety-one-byte version. So: are we stuck with this as our best size? No, not quite. We violated no rules when we overlapped the ELF header and the program header table by eight bytes. The ELF specification explicitly permits overlap of different data structures within the file. So let's do that here: ; tiny.asm BITS 32 org 0x08048000 ehdr: db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsz ; e_ehsize dw phdrsz ; e_phentsize phdr: dd 1 ; e_phnum ; p_type ; e_shentsize

dd 0 ; e_shnum ; p_offset ; e_shstrndx ehdrsz equ $ - ehdr dd $$ ; p_vaddr dd $$ ; p_paddr dd filesz ; p_filesz dd filesz ; p_memsz dd 5 ; p_flags dd 0x1000 ; p_align phdrsz equ $ - phdr _start: xor eax, eax inc eax mov bl, 42 int 0x80 filesz equ $ - $$

That gives us eighty-three bytes. What else can we do? Seems like there isn't much. In desperation, we might turn back to the ELF specification and read it over again, looking for something.

Are there any guarantees anything about the initial register values? Only for one register: edx. And what is says is that it will contain either zero, or the address of a final shutdown procedure. So, no guarantees at all, really. Keep looking.

A-ha: The p_paddr field of the program header table structure! Every other field of the headers which doesn't apply to to Intel architecture, or doesn't apply to an executable file — or, at least, not to our executable file — is required by the ELF specification to be set to zero. But for the p_paddr field, the specification says the field has unspecified contents. So we have four bytes that we can play with, after all.

What can we do with them? Use it to hold part of our program, naturally. Of course, we can't put the whole program there, so we'll need to waste two of the four bytes on a jmp instruction, in order to get to the rest of it. But that still leaves two bytes that we can use, and the first instruction of our program is exactly two bytes long.

; tiny.asm BITS 32 org 0x08048000 ehdr: db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsz ; e_ehsize dw phdrsz ; e_phentsize phdr: dd 1 ; e_phnum ; p_type ; e_shentsize dd 0 ; e_shnum ; p_offset ; e_shstrndx ehdrsz equ $ - ehdr dd $$ ; p_vaddr _start: xor eax, eax ; p_paddr jmp short part2 dd filesz ; p_filesz dd filesz ; p_memsz dd 5 ; p_flags dd 0x1000 ; p_align phdrsz equ $ - phdr part2: inc eax mov bl, 42 int 0x80 filesz equ $ - $$

So. Eighty-one bytes. Is that all?

The next field after the p_paddr field is the p_filesz field. If only we could overlap the jmp instruction with that, we could squeeze another instruction in there. But alas, the first byte of that field is the size of the entire file, which would be an unwise jump to make. And the remaining bytes are zeros. That approach doesn't look too promising.

What about the field before p_paddr? That's the address the program is to be loaded at.

Well, we already know we don't have to use the default value of 0x08048000. We do need to keep the address page-aligned, at the very least, but we should be able to fit a two-byte instruction into the top half of the address. However, our xor won't work for that. Remember that this is little-endian. The bytes of our program are currently: 31C0 xor eax, eax EB10 jmp short part2 40 part2: inc eax B32A mov bl, 42 CD80 int 0x80

The xor instruction would leave C0 as the top byte, which has the high bit set, and Linux doesn't appreciate us putting our code there. (As a general rule, in a 32-bit executable, the top half of memory is reserved for dynamically assigned addresses: the heap, the stack, and shared-object libraries.)

The "mov bl, 42" instruction, on the other hand, will give us a perfectly acceptable top address byte. So, we can change the load address to 0x2AB30000, and with a little rearranging we have: ; tiny.asm BITS 32 org 0x2AB30000 ehdr: db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsz ; e_ehsize dw phdrsz ; e_phentsize phdr: dd 1 ; e_phnum ; p_type ;