2025 winter challenge writeup

Classement final

Voici le classement définitif des personnes ayant réussi à valider au moins une solution. Les cas d'égalité sont départagés en fonction de la date de réception du binaire :

• #1 - 81 - ioonag - 2025/12/08 10:21 PM (write-up)
• #2 - 81 - XeR - 2025/12/17 1:58 PM (solution)
• #3 - 81 - toby - 2025/12/29 11:41 PM (write-up)
• #4 - 81 - 00BL1X - 2025/12/30 1:02 AM
• #5 - 83 - Leon Noel - 2025/12/27 12:30 AM
• #6 - 89 - doegox - 2025/12/07 2:37 AM
• #7 - 89 - Lion - 2025/12/12 6:41 PM
• #8 - 95 - Swissky - 2025/12/08 6:13 PM
• #9 - 99 - alph4kam - 2025/12/11 7:47 PM
• #10 - 101 - 3akev - 2025/12/19 8:43 AM
• #11 - 103 - Nicolas - 2025/12/23 10:16 AM
• #12 - 105 - itszn - 2025/12/03 1:28 PM 
• #13 - 107 - matt - 2025/12/28 11:45 PM
• #14 - 111 - Sk4r - 2025/12/12 12:26 AM (write-up)
• #15 - 114 - mirisme - 2025/12/12 7:46 PM
• #16 - 114 - rick - 2025/12/29 6:02 PM
• #17 - 127 - rl0x01 - 2025/12/16 4:58 PM
• #18 - 128 - Gerfaut - 2025/12/27 10:58 AM
• #19 - 145 - Cortex - 2025/12/02 8:45 PM
• #20 - 148 - Aker - 2025/12/22 7:33 AM
• #21 - 165 - hendo - 2025/12/09 5:49 PM 
• #22 - 188 - n0x - 2025/12/14 2:46 PM
• #23 - 201 - Youssef - 2025/12/28 3:16 PM
• #24 - 226 - CupOfCoffee - 2025/12/05 8:01 AM
• #25 - 422 - Noé - 2025/12/13 5:11 PM

Nous remercions et félicitons les 25 participants pour la qualité des solutions reçues.
Bravo tout particulièrement aux 4 premiers, qui sont parvenus à faire mieux que notre solution Synacktiv de 83 octets :

$ hexdump -C synacktiv.bin 
00000000  7f 45 4c 46 01 ed eb 53  b2 58 41 04 6a 43 04 72  |.ELF...S.XA.jC.r|
00000010  02 00 03 00 3d 4b 80 cd  45 00 2c 00 2c 00 00 00  |....=K..E.,.,...|
00000020  00 00 00 00 00 00 01 00  20 00 20 00 01 00 00 00  |........ . .....|
00000030  00 00 00 00 00 00 2c 00  2c 00 45 cd 80 4b 3d 00  |......,.,.E..K=.|
00000040  03 00 02 72 04 43 6a 04  41 58 b2 53 eb ed 01 46  |...r.Cj.AX.S...F|
00000050  4c 45 7f                                          |LE.|

$ sha256sum synacktiv.bin 
8af9fdd50a4b5df623d59b4fde2d8c01d88c27a9badb09e2fdb1b24ca475e111  synacktiv.bin

La solution de IooNag

Nous avons choisi de publier ici le write-up de IooNag, d'abord parce qu'il a remporté ce défi avec un meilleur score que Synacktiv, mais aussi parce que son rapport est très détaillé et les explications y sont clairement rédigées !
Cette section entière a donc été copiée et traduite à partir du write-up de IooNag, disponible sur son GitHub.

🎅 1. Un nouveau défi se présente !

À la suite du Summer Challenge de 2025, Synacktiv a publié un nouveau challenge en décembre 2025 : le Winter Challenge 2025 : Quinindrome.

L'objectif est de concevoir un quinindrome, c'est-à-dire un binaire ELF qui respecte les deux propriétés suivantes :

1. être un palindrome, donc être parfaitement symétrique,
2. et être un byte-wise quine : afficher son propre fichier sur stdout lorsqu'on l'exécute.

Bien entendu, le processus doit se finir sans segfault, et le code de retour doit être défini à 0.

[...] le gagnant sera celui qui parviendra à obtenir le plus petit score [...]

Sur un système Linux, il est plutôt facile de créer un programme qui répond à ces deux contraintes, grâce à la directive d'interprétation shebang :

#!/bin/cat
tac/nib/!#

Ce programme de 21 octets est un palindrome et, lorsqu'il est exécuté, Linux lance cat avec le nom du fichier. Le contenu du fichier s'affiche alors et le programme se termine normalement.

Toutefois, ce programme échoue à passer le script de test fourni par Synacktiv. En effet, ce script crée un conteneur (basé sur l'image scratch) qui ne contient que le programme testé. Étant donné que cat n'est pas inclus dans le conteneur, il ne peut pas être exécuté.

Cette solution facile n'étant pas envisageable, que peut-on mettre en place pour résoudre le problème ?

🚚 2. Compiler une solution volumineuse

L'une des façons les plus simples de construire un Quine consiste à ouvrir le fichier du binaire indiqué dans argv[0], à le lire dans un tableau et à écrire le contenu du tableau sur la sortie standard :

#include <fcntl.h>
#include <unistd.h>

static unsigned char buffer[10000000];

int main(int argc, char **argv) {
    int fd = open(argv[0], 0);
    size_t size = read(fd, buffer, sizeof(buffer));
    write(1, buffer, size);
    return 0;
}

La compilation de ce programme C dans une machine virtuelle Debian 13 produit un exécutable de 737 Ko :

$ gcc -Os -static -o quine quine.c
$ stat --format=%s quine
754208

Afin de faire de ce programme un palindrome, la méthode naïve consisterait à ajouter une copie dont les octets sont inversés à la fin. Une approche moins naïve serait d'omettre le dernier octet de la copie, car il peut agir comme un pivot entre la partie originale et son symétrique.

$ cat quine > quinindrome
$ python3 -c 'import sys;sys.stdout.buffer.write(sys.stdin.buffer.read()[:-1][::-1])' \
    < quine >> quinindrome
$ chmod +x quinindrome
$ ./test_script.sh quinindrome
[+] 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: 1508415

Après plusieurs minutes, le script de test a confirmé que ce programme était une solution valide !

Mais le score reste très élevé. Comment le réduire autant que possible ?

⛳ 3. Code-golfer l'exécutable à nouveau

Puisque le score d'un programme répondant aux exigences correspond à sa taille, le but est de produire le programme le petit possible. Il s'agit d'un domaine appelé « code golfing » et mon write-up du challenge précédent dédiait une section entière à ce sujet, avec quelques conseils : Write-up for Synacktiv's 2025 Summer Challenge: OCInception, 6. (Bonus) Code-golfing the executable

Au lieu de passer en revue les explications de toutes les techniques, étudions une solution au problème consistant à afficher Hello world\n, qui a été réalisé en 98 octets ici https://codegolf.stackexchange.com/questions/5696/shortest-elf-for-hello-world-n :

7F 45 4C 46 01 01 01 00 00 00 00 00 00 00 00 00
02 00 03 00 01 00 00 00 35 40 B3 04 2C 00 00 00
00 00 00 00 00 00 00 00 34 00 20 00 01 00 00 00
00 00 00 00 00 40 B3 04 B2 0C EB 1C 62 00 00 00
62 00 00 00 05 00 00 00 00 10 00 00 48 65 6C 6C
6F 20 77 6F 72 6C 64 0A B9 4C 40 B3 04 93 CD 80
EB FB

Ce programme n'est ni un quine ni un palindrome, pourquoi est-il donc intéressant de l'étudier ? Un quine peut être élaboré en écrivant le contenu du programme à la place de la chaîne « Hello world ». Ceci rend possible la modification de ce programme afin d'obtenir une solution fonctionnelle pour le challenge quinindrome.

Cette réponse StackExchange apporte également des explications sur la disposition des octets :

            org     0x04B34000
            db      0x7F, "ELF", 1, 1, 1, 0 ; e_ident
            dd      0, 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      0x34                    ; e_ehsize
            dw      0x20                    ; e_phentsize
phdr:       dd      1                       ; e_phnum       ; p_type
                                            ; e_shentsize
            dd      0                       ; e_shnum       ; p_offset
                                            ; e_shstrndx
            db      0                                       ; p_vaddr
_start:     inc     eax
            mov     bl, 4
            mov     dl, 12                                  ; p_paddr
            jmp     short part2
            dd      filesize                                ; p_filesz
            dd      filesize                                ; p_memsz
            dd      5                                       ; p_flags
            dd      0x1000                                  ; p_align
str:        db      'Hello world', 10
part2:      mov     ecx, str
again:      xchg    eax, ebx
            int     0x80
            jmp     short again
filesize    equ     $ - $$EM_486

Cette syntaxe est celle utilisée par un assembleur bien connu appelé NASM. Elle permet d'écrire des instructions assembleur x86 (telles que inc eax ou mov ecx, str) entrecoupées de certains entiers avec les instructions db (pour les octets), dw (pour les entiers 16 bits, « mots ») et dd (pour les entiers 32 bits, « double-words »). Les commentaires dans la description mettent en correspondance les champs utilisés par les en-têtes ELF avec le contenu de la réponse.

En effet, les fichiers exécutables ELF contiennent généralement plusieurs en-têtes, documentés dans man 5 elf :

• un « en-tête ELF » nommé Ehdr
• un « en-tête de programme » nommé Phdr
• un « en-tête de section » nommé Shdr

Pour exécuter un programme, l'en-tête de section n'est pas utilisé et peut donc être ignoré. L'en-tête de programme contient des informations décrivant la manière dont le programme est chargé. Il doit contenir au moins une entrée indiquant comment le fichier est mappé en mémoire. Enfin, l'en-tête ELF est obligatoire et apparaît toujours dans les premiers octets du fichier.

Voici les versions 32 bits des structures C définissant l'en-tête ELF et l'en-tête de programme, accompagnées de quelques commentaires :

typedef struct {
    unsigned char e_ident[16];  // ELF identifier "\x7fELF"
    uint16_t      e_type;       // Type of ELF file, should be ET_EXEC = 2
    uint16_t      e_machine;    // Architecture, should be EM_386 = 3 or EM_486 = 6
    uint32_t      e_version;
    Elf32_Addr    e_entry;      // Address of the entrypoint of the program
    Elf32_Off     e_phoff;      // File offset of the program header
    Elf32_Off     e_shoff;      // File offset of the section headr
    uint32_t      e_flags;
    uint16_t      e_ehsize;     // Size of the ELF header, should be 0x34
    uint16_t      e_phentsize;  // Size of Elf32_Phdr, should be 0x20
    uint16_t      e_phnum;      // Number of entries in the program header table
    uint16_t      e_shentsize;  // Size of Elf32_Shdr
    uint16_t      e_shnum;      // Number of entries in the section header table
    uint16_t      e_shstrndx;
} Elf32_Ehdr;

typedef struct {
    uint32_t   p_type;   // Kind of entry, should be PT_LOAD = 1 for a loadable segment
    Elf32_Off  p_offset; // File offset of the segment
    Elf32_Addr p_vaddr;  // Address where the segment gets loaded
    Elf32_Addr p_paddr;  // "Physical address", ignored in Linux
    uint32_t   p_filesz; // Number of bytes from the file in the segment
    uint32_t   p_memsz;  // Number of bytes in memory for the segment
    uint32_t   p_flags;  // Permissions of the segment. Should be PF_X | PF_R = 5
    uint32_t   p_align;
} Elf32_Phdr;

Une astuce couramment employée pour créer de petits fichiers ELF consiste à faire se chevaucher ces deux en-têtes, en utilisant le fait que les octets 01 00 00 00 00 00 00 00 peuvent être utilisés pour représenter simultanément :

• e_phnum = 1; e_shentsize = 0; e_shnum = 0; e_shstrndx = 0 dans l'en-tête ELF,
• et p_type = PT_LOAD; p_offset = 0 dans l'en-tête du programme.

Cette technique a été utilisée dans la solution StackExchange.

Ensuite vient le code assembleur. Comment cela fonctionne-t-il ? Pour invoquer les fonctions du système d'exploitation via des appels système dans x86 (en mode 32 bits) sur Linux, une interruption logicielle peut être déclenchée grâce à l'instruction int 0x80. Les paramètres de l'appel système sont spécifiés dans les registres : eax pour identifier la fonction système réellement appelée ; et ebx, ecx, edx, esi, edi et ebp pour fournir les arguments. Le programme utilise deux appels système :

• write(int fd, void *buf, size_t count) (eax = 4) pour écrire des données dans la sortie standard (ebx = 1) ;
• _exit(int status) (eax = 1) pour terminer avec le code de retour succès (ebx = 0).

Modifions le code pour afficher le contenu du programme. Pour ce faire, l'adresse à laquelle le programme est chargé en mémoire doit être placée dans le registre ecx. Une instruction mov avec une valeur immédiate de 32 bits nécessite habituellement 5 octets. À l'aide de quelques techniques, il est possible de descendre à 3 octets lorsque l'adresse est 0xffff0000, grâce à 2 instructions : dec %ecx pour définir le registre à 0xffffffff et inc %cx pour incrémenter les 16 bits de poids faible (à noter que cette adresse doit être au moins égale à 0x10000, pour être supérieure à /proc/sys/vm/mmap_min_addr, et que sur un système 64 bits, les adresses de l'espace utilisateur peuvent être supérieures à 0xc0000000 car aucun espace mémoire n'est réservé au noyau).

Il est ainsi possible de créer un quine de 14 octets en assembleur (avec la syntaxe AT&T) :

49      dec %ecx
66 41   inc %cx         ; set ecx = 0xffff0000 (address)
b2 ab   mov $0xab,%dl   ; set edx = 171 (file size)
b0 04   mov $0x4,%al    ; set eax = 4
43      inc %ebx        ; set ebx = 1
cd 80   int $0x80       ; write(1, 0xffff0000, 171)

4b      dec %ebx        ; set ebx = 0
58      pop %eax        ; set eax = 1 by using argc from the stack
cd 80   int $0x80       ; exit(0)

Lorsqu'un programme est lancé dans Linux, la stack est initialisée avec plusieurs valeurs : le nombre d'arguments, les arguments, les variables d'environnement... (en C : {argc, argv[0], argv[1], ..., argv[argc-1], NULL, envp[0], ..., NULL}). Comme le programme de test est toujours exécuté sans aucun argument dans le script test_script.sh, argc = 1 et cette valeur peut être extraite de la stack avec l'instruction pop pour définir un registre à 1.

Afin de tester plus facilement une telle solution, j'ai écrit un script Python : solution_1_headers_code.py. Ce script implémente certaines fonctions qui aident à définir le contenu des en-têtes et du code, tout en garantissant que les champs qui se chevauchent utilisent les mêmes valeurs :

# ELF header
place_bytes(0, b"\x7fELF", "Elf32_Ehdr.e_ident = ELF magic")
place_u16(0x10, 2, "Elf32_Ehdr.e_type = ET_EXEC")
place_u16(0x12, 3, "Elf32_Ehdr.e_machine = EM_386")  # can also be EM_486 = 6
place_u32(0x18, image_base + code_offset, "Elf32_Ehdr.e_entry")
place_u32(0x1c, phdr_offset, "Elf32_Ehdr.e_phoff")
place_u16(0x2a, 0x20, "Elf32_Ehdr.e_phentsize")
place_u16(0x2c, 1, "Elf32_Ehdr.e_phnum")

# Program header
place_u32(phdr_offset + 0x00, 1, "Elf32_Phdr.p_type = PT_LOAD")
place_u32(phdr_offset + 0x04, 0, "Elf32_Phdr.p_offset")
place_u32(phdr_offset + 0x08, image_base, "Elf32_Phdr.p_vaddr")
place_u32(phdr_offset + 0x10, final_file_size, "Elf32_Phdr.p_filesz")
place_u32(phdr_offset + 0x14, final_file_size, "Elf32_Phdr.p_memsz")
place_u32(phdr_offset + 0x18, 5, "Elf32_Phdr.p_flags = PF_R | PF_X")

Connaître les octets définis permet d'afficher un dump hexadécimal du quine avec ?? pour représenter ceux sont indéfinis :

 000000:  7f45 4c46 ???? ???? ???? ???? ???? ????
 000010:  0200 0300 ???? ???? 4800 ffff 2c00 0000
 000020:  ???? ???? ???? ???? ???? 2000 0100 0000
 000030:  0000 0000 0000 ffff ???? ???? ab00 0000
 000040:  ab00 0000 0500 0000 4966 41b2 abb0 0443
 000050:  cd80 4b58 cd80

Cette première solution produit le quinindrome suivant (solution_1_headers_code.bin) :

$ xxd solution_1_headers_code.bin
00000000: 7f45 4c46 0000 0000 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0000 0000 4800 ffff 2c00 0000  ........H...,...
00000020: 0000 0000 0000 0000 0000 2000 0100 0000  .......... .....
00000030: 0000 0000 0000 ffff 0000 0000 ab00 0000  ................
00000040: ab00 0000 0500 0000 4966 41b2 abb0 0443  ........IfA....C
00000050: cd80 4b58 cd80 cd58 4b80 cd43 04b0 abb2  ..KX...XK..C....
00000060: 4166 4900 0000 0500 0000 ab00 0000 ab00  AfI.............
00000070: 0000 00ff ff00 0000 0000 0000 0000 0100  ................
00000080: 2000 0000 0000 0000 0000 0000 0000 2cff   .............,.
00000090: ff00 4800 0000 0000 0300 0200 0000 0000  ..H.............
000000a0: 0000 0000 0000 0046 4c45 7f              .......FLE.

$ ./test_script.sh solution_1_headers_code.bin
[+] 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: 171

Il reste encore plusieurs octets indéfinis dans ce fichier. Poursuivons notre progression !

💻 4. Un kernel loader très laxiste

Quand on analyse la solution produite, on remarque quelque chose d'étrange : l'en-tête ELF n'est en fait pas valide. La commande file indique :

$ file solution_1_headers_code.bin
solution_1_headers_code.bin: ELF invalid class invalid byte order (SYSV), unknown class 0

Un fichier ELF 32 bits commence normalement par 0x7f, "ELF", 1, 1, 1 pour spécifier :

• e_ident[EI_CLASS] = ELFCLASS32 (jeu d'instructions 32 bits)
• e_ident[EI_DATA] = ELFDATA2LSB (données en little endian)
• e_ident[EI_VERSION] = EV_CURRENT (version de la spécification ELF)

Néanmoins, ces 3 octets ne sont pas vérifiés par le fragment de code du noyau Linux responsable du chargement des programmes ELF. Où se trouve ce code ?

Dans le noyau Linux, lorsqu'un programme est lancé (via des appels système tels que execve ou execveat), plusieurs chargeurs peuvent être utilisés. Ils sont implémentés dans les fichiers binfmt_....c du répertoire fs/ :

binfmt_elf.c            for ELF files
binfmt_elf_fdpic.c      for FDPIC ELF files
binfmt_flat.c           for Flat files
binfmt_misc.c           to use /proc/sys/fs/binfmt_misc to invoke helper loaders
binfmt_script.c         for script files with shebang
compat_binfmt_elf.c     for 32-bit ELF files on 64-bit systems

En réalité, le noyau prend en charge d'autres formats que ELF ! Mais sur les systèmes x86, FDPIC ELF et Flat ne sont pas disponibles (ils sont utilisés sur certains systèmes ARM et certains systèmes sans MMU, selon Kconfig). Cela peut être confirmé par l'inspection de la configuration du noyau dans une machine virtuelle Debian 13 :

$ grep BINFMT /boot/config-6.12.57+deb13-amd64
CONFIG_BINFMT_ELF=y
CONFIG_COMPAT_BINFMT_ELF=y
CONFIG_BINFMT_SCRIPT=y
CONFIG_BINFMT_MISC=m

Sur un système 64 bits, le chargement des programmes ELF 32 bits est géré par fs/compat_binfmt_elf.c, qui définit principalement certaines macros C et inclut le parseur principal (cf. ligne 144) :

/*
 * We share all the actual code with the native (64-bit) version.
 */
#include "binfmt_elf.c"

Ce fichier implémente la fonction load_elf_binary, en commençant par :

    retval = -ENOEXEC;
    /* First of all, some simple consistency checks */
    if (memcmp(elf_ex->e_ident, ELFMAG, SELFMAG) != 0)
        goto out;

    if (elf_ex->e_type != ET_EXEC && elf_ex->e_type != ET_DYN)
        goto out;
    if (!elf_check_arch(elf_ex))
        goto out;

Voici le code qui vérifie les 4 premiers octets des programmes ELF, ainsi que les champs e_type et e_machine !

Dans le même fichier, la fonction load_elf_phdrs vérifie certaines contraintes liées aux champs e_phentsize et e_phnum :

    /*
     * If the size of this structure has changed, then punt, since
     * we will be doing the wrong thing.
     */
    if (elf_ex->e_phentsize != sizeof(struct elf_phdr))
        goto out;

    /* Sanity check the number of program headers... */
    /* ...and their total size. */
    size = sizeof(struct elf_phdr) * elf_ex->e_phnum;
    if (size == 0 || size > 65536 || size > ELF_MIN_ALIGN)
        goto out;

/* ... */
    retval = elf_read(elf_file, elf_phdata, size, elf_ex->e_phoff);

Ainsi, e_phentsize doit être égal à 0x20, e_phnum doit compter le nombre réel d'entrées dans l'en-tête du programme et e_phoff est utilisé pour localiser celle-ci.

Le champ e_entry sert à définir le point de départ de l'exécution et doit donc être une adresse mémoire valide contenant des instructions x86 valides.

Y aurait-il d'autres contraintes ? Pour le vérifier, le script Python a été modifié afin d'utiliser des octets aléatoires pour lesquels aucune contrainte n'était définie :

if "--random-elf" in sys.argv:
    for i in range(len(program_bytes)):
        program_bytes[i] = random.randint(0, 255)

L'exécution de ./solution_1_headers_code.py --random-elf --run permet de confirmer que les autres champs de l'en-tête ELF ne sont pas réellement utilisés.

Qu'en est-il de l'en-tête du programme ?

• Field p_type doit être PT_LOAD = 1.
• Field p_paddr n'est pas utilisé.
• Field p_align n'est utilisé que lorsque le programme est déplacé vers une autre adresse. Avec un exécutable de position fixe (e_type = ET_EXEC au lieu de ET_DYN), il n'est pas utilisé.
• Seuls les 3 bits de poids faible de p_flags sont utilisés pour définir les permissions du segment (PF_X = 1 ; PF_W = 2 ; PF_R = 4). Les 29 autres bits peuvent avoir n'importe quelle valeur.

Par ailleurs, les champs p_offset, p_vaddr, p_filesz et p_memsz sont soumis à certaines contraintes complexes. Alors que les règles intuitives seraient « p_offset = 0 pour mapper le début du fichier ; p_vaddr = adresse de base pour mapper le fichier à une adresse donnée ; p_filesz = p_memsz = taille du fichier pour mapper l'intégralité du fichier », dans la pratique, l'implémentation des fonctions load_elf_binary et elf_load est beaucoup plus souple :

• p_filesz <= p_memsz : cela garantit que la zone mémoire contient suffisamment de données provenant du fichier (le contenu restant est rempli de zéros).
• eppnt->p_filesz != 0 : cela garantit que la zone mémoire est chargée à partir du fichier (avec elf_map à la ligne 408) au lieu d'être remplie de zéros.

Cela permet de créer un fichier ELF dont l'en-tête du programme se trouve 4 octets après le début du fichier, solution_2_phdr4.py :

place_u32(phdr_offset + 0x00, 1, "Elf32_Phdr.p_type = PT_LOAD")
place_u32(phdr_offset + 0x04, 0, "Elf32_Phdr.p_offset")
place_u32(phdr_offset + 0x08, image_base, "Elf32_Phdr.p_vaddr")
place_u32(phdr_offset + 0x10, final_file_size, "Elf32_Phdr.p_filesz")
# e_entry and p_memsz are located at the same place
place_u32(phdr_offset + 0x14, image_base + code_offset, "Elf32_Phdr.p_memsz")
# e_phoff and p_flags are located at the same place
place_u8(phdr_offset + 0x18, 4, "Elf32_Phdr.p_flags = PF_R")

Cependant, dans ce cas p_flags doit être égal à 4, ce qui empêche le fichier d'être mappé avec le bit d'exécution activé... mais est-ce vraiment le cas ? En réalité, avec les programmes x86 32 bits, lorsqu'il n'y a pas d'entrée PT_GNU_STACK dans l'en-tête du programme, tous les segments sont chargés avec le bit exécutable ! C'est là toute la magie de elf_read_implies_exec.

L'en-tête ELF prend 0x2e octets et il ne reste que peu d'espace pour y insérer du code :

Hexdump:
 000000:  7f45 4c46 0100 0000 0000 0000 <vaddr  >
 000010:  0200 0300 <filesz > <entry  > 0400 0000
 000020:  ???? ???? ???? ???? ???? 2000 0100

Pour créer un quinindrome, le code assembleur peut être ajouté juste après et inversé. Une autre méthode consiste à prendre directement en compte les octets inversés et à les utiliser dans le code. Avec cette stratégie, j'ai conçu une solution de 96 octets (solution_2_phdr4.bin), en utilisant ce code de 16 octets :

04 04       add $4, %al           ; eax = 4
b9 00010020 mov $0x20000100, %ecx ; ecx = 0x20000100
b2 60       mov $0x60, %dl        ; edx = 96 (file size)
86 dd       xchg %bl, %ch         ; ebx = 1, ecx = 0x20000000
cd 80       int $0x80             ; write(1, 0x20000000, 96)
58          pop %eax              ; eax = 1
eb f9       jmp . - 5             ; jump to "xchg %bl, %ch"
            ; xchg %bl, %ch       ; ebx = 0
            ; int $0x80           ; exit(0)

Ce code fait appel à plusieurs techniques, telles que l'utilisation de xchg et jmp pour réutiliser des instructions afin d'invoquer des appels système (ce qui permet d'économiser un octet). Cette méthode est documentée par exemple sur StackExchange. De plus, la première instruction mov utilise les octets miroirs de l'en-tête ELF et défini l'adresse où le fichier est chargé à 0x20000000.

$ xxd solution_2_phdr4.bin
00000000: 7f45 4c46 0100 0000 0000 0000 0000 0020  .ELF...........
00000010: 0200 0300 6000 0000 2f00 0020 0400 0000  ....`.../.. ....
00000020: 00f9 eb58 80cd dd86 60b2 2000 0100 b904  ...X....`. .....
00000030: 04b9 0001 0020 b260 86dd cd80 58eb f900  ..... .`....X...
00000040: 0000 0004 2000 002f 0000 0060 0003 0002  .... ../...`....
00000050: 2000 0000 0000 0000 0000 0001 464c 457f   ...........FLE.

$ ./test_script.sh solution_2_phdr4.bin
[+] 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: 96

#if ELF_EXEC_PAGESIZE > PAGE_SIZE
#define ELF_MIN_ALIGN    ELF_EXEC_PAGESIZE
#else
#define ELF_MIN_ALIGN    PAGE_SIZE
#endif
#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))
#define ELF_PAGEOFFSET(_v) ((_v) & (ELF_MIN_ALIGN-1))
#define ELF_PAGEALIGN(_v) (((_v) + ELF_MIN_ALIGN - 1) & ~(ELF_MIN_ALIGN - 1))

static unsigned long elf_map(struct file *filep, unsigned long addr,
        const struct elf_phdr *eppnt, int prot, int type,
        unsigned long total_size)
{
    unsigned long map_addr;
    unsigned long size = eppnt->p_filesz + ELF_PAGEOFFSET(eppnt->p_vaddr);
    unsigned long off = eppnt->p_offset - ELF_PAGEOFFSET(eppnt->p_vaddr);
    addr = ELF_PAGESTART(addr);
    size = ELF_PAGEALIGN(size);
/* ... */
    if (total_size) {
        total_size = ELF_PAGEALIGN(total_size);
        map_addr = vm_mmap(filep, addr, total_size, prot, type, off);

$ xxd solution_2_phdr4_0x123.bin
00000000: 7f45 4c46 0100 0000 2301 0000 2301 0020  .ELF....#...#..
00000010: 0200 0300 0100 0000 2f00 0020 0400 0000  ......../.. ....
00000020: 00f9 eb58 80cd dd86 60b2 2000 0100 b904  ...X....`. .....
00000030: 04b9 0001 0020 b260 86dd cd80 58eb f900  ..... .`....X...
00000040: 0000 0004 2000 002f 0000 0001 0003 0002  .... ../........
00000050: 2000 0123 0000 0123 0000 0001 464c 457f   ..#...#....FLE.

$ readelf --program-headers solution_2_phdr4_0x123.bin
readelf: Warning: The e_shentsize field in the ELF header is larger than the size of an ELF section header
readelf: Error: Reading 57263076 bytes extends past end of file for section headers

Elf file type is EXEC (Executable file)
Entry point 0x2000002f
There is 1 program header, starting at offset 4

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x000123 0x20000123 0x00030002 0x00001 0x2000002f R   0x58ebf900

$ ./test_script.sh solution_2_phdr4_0x123.bin
[+] 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: 96

Q(65=0x41.0x04) possible with holes [1, 4, 1, 2, 1, 2, 1, 4, 1]:
    0000:  7f45 4c46 0100 0000 ..v0 0000 .... ....
    0010:  0200 v100 0100 20.. v2v3 .... 0400 0000
    0020:  ..00 0000 04.. ..v3 v2.. 2000 0100 v100
    0030:  02.. .... ..00 00v0 ..00 0000 0146 4c45
    0040:  7f
    - v0 at 0x9 in {00,01,02,03,04,05,06,07,08,09,0a,0b,0c,0d,0e,0f}
    - v1 at 0x12 in {03,06}
    - v2 at 0x18 in {00,01,02,03,04,05,06,07,08,09,0a,0b,0c,0d,0e,0f,10,11,12,13,14,15,16,17,18,19,1a,1b,1c,1d,1e,1f,20,21,22,23,24,25,26,27,28,29,2a,2b,2c,2d,2e,2f,30,31,32,33,34,35,36,37,38,39,3a,3b,3c,3d,3e,3f,40}
    - v3 at 0x19 in {00,10,20,30,40,50,60,70,80,90,a0,b0,c0,d0,e0,f0}
    - e_entry  at 0x18 is 0x....v3v2
    - p_offset at 0x08 is 0x0000v0..
    - p_vaddr  at 0x0c is 0x........
    - p_filesz at 0x14 is 0x..200001
    - p_memsz  at 0x18 is 0x....v3v2
    - p_flags  at 0x1c is 0x00000004

Q(77=0x4d.0x2c) possible with holes [12, 1, 1, 7, 1, 1, 12]:
    0000:  7f45 4c46 .... .... .... .... .... ....
    0010:  0200 v000 ..v1 00.. 2c00 00v2 2c00 0000
    0020:  0100 20.. .... .... .... 2000 0100 0000
    0030:  2cv2 0000 2c.. 00v1 ..00 v000 02.. ....
    0040:  .... .... .... .... ..46 4c45 7f
    - v0 at 0x12 in {03,06}
    - v1 at 0x15 in {00,01,02,03,04,05,06,07,08,09,0a,0b,0c,0d,0e,0f}
    - v2 at 0x1b in {00,01,02,03,04,05,06,07,08,09,0a,0b,0c,0d,0e,0f}
    - e_entry  at 0x18 is 0xv200002c
    - p_offset at 0x30 is 0x0000v22c
    - p_vaddr  at 0x34 is 0xv100..2c
    - p_filesz at 0x3c is 0x......02
    - p_memsz  at 0x40 is 0x........
    - p_flags  at 0x44 is 0x........

Q(81=0x51.0x2c) possible with holes [12, 4, 1, 3, 1, 4, 12]:
    0000:  7f45 4c46 .... .... .... .... .... ....
    0010:  0200 v000 .... .... v1v2 ..v3 2c00 0000
    0020:  2c00 0000 0100 20.. .... 2000 0100 0000
    0030:  2c00 0000 2cv3 ..v2 v1.. .... ..00 v000
    0040:  02.. .... .... .... .... .... ..46 4c45
    0050:  7f
    - v0 at 0x12 in {03,06}
    - v1 at 0x18 in {00,01,02,03,04,05,06,07,08,09,0a,0b,0c,0d,0e,0f,10,11,12,13,14,15,16,17,18,19,1a,1b,1c,1d,1e,1f,20,21,22,23,24,25,26,27,28,29,2a,2b,2c,2d,2e,2f,30,31,32,33,34,35,36,37,38,39,3a,3b,3c,3d,3e,3f,40,41,42,43,44,45,46,47,48,49,4a,4b,4c,4d,4e,4f,50}
    - v2 at 0x19 in {00,10,20,30,40,50,60,70,80,90,a0,b0,c0,d0,e0,f0}
    - v3 at 0x1b in {00,10,20,30,40,50,60,70,80,90,a0,b0,c0,d0,e0,f0}
    - e_entry  at 0x18 is 0xv3..v2v1
    - p_offset at 0x30 is 0x0000002c
    - p_vaddr  at 0x34 is 0xv2..v32c
    - p_filesz at 0x3c is 0x00v000..
    - p_memsz  at 0x40 is 0x......02
    - p_flags  at 0x44 is 0x........

43          inc %ebx              ; ebx = 1
04 04       add $4, %al           ; eax = 4
b9 00030002 mov $0x02000300, %ecx ; ecx = 0x02000300
c1 e1 08    shl $8, %ecx          ; ecx = 0x00030000
45          inc %ebp              ; Have p_flags&7 = PF_R | PF_X
b2 51       mov $0x51, %dl        ; edx = 81 (file size)
cd 80       int $0x80             ; write(1, 0x00030000, 81)
4b          dec %ebx              ; ebx = 0
58          pop %eax              ; eax = 1
cd 80       int $0x80             ; exit(0)

Hexdump:
 000000:  7f45 4c46 80cd 584b 80cd 51b2 4508 e1c1
 000010:  0200 0300 b904 0443 3900 0300 2c00 0000
 000020:  2c00 0000 0100 20?? ???? 2000 0100 0000
 000030:  2c00 0000 2c00 0300 3943 0404 b900 0300
 000040:  02c1 e108 45b2 51cd 804b 58cd 8046 4c45
 000050:  7f

Dans cette configuration, les 3 octets au milieu du fichier ne sont soumis à aucune contrainte (car e_flags et e_ehsize ne sont pas utilisés par le noyau). Pour rendre la solution un peu amusante, j'ai ajouté un smiley.

$ xxd solution_3_minimal.bin
00000000: 7f45 4c46 80cd 584b 80cd 51b2 4508 e1c1  .ELF..XK..Q.E...
00000010: 0200 0300 b904 0443 3900 0300 2c00 0000  .......C9...,...
00000020: 2c00 0000 0100 205e 5f5e 2000 0100 0000  ,..... ^_^ .....
00000030: 2c00 0000 2c00 0300 3943 0404 b900 0300  ,...,...9C......
00000040: 02c1 e108 45b2 51cd 804b 58cd 8046 4c45  ....E.Q..KX..FLE
00000050: 7f                                       .

$ ./test_script.sh solution_3_minimal.bin
[+] 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: 81

💥 6. (Bonus) Ça fonctionne sur ma machine !

Avant de soumettre une solution aux organisateurs du challenge, je me suis assuré que le script de test fonctionnait correctement dans une machine virtuelle Debian 13. Cela aurait dû éviter toute situation où une solution fonctionnait de mon côté, mais pas de celui des organisateurs.

Malheureusement, c'est ce qui s'est produit.

Voici la solution que j'ai envoyée et qui s'est avérée problématique :

$ xxd solution_3_with_bug.bin
00000000: 7f45 4c46 80cd 584b 80cd 4308 e1c1 51b2  .ELF..XK..C...Q.
00000010: 0200 0300 b904 0490 3900 0300 2c00 0000  ........9...,...
00000020: 2c00 0000 0100 2000 0000 2000 0100 0000  ,..... ... .....
00000030: 2c00 0000 2c00 0300 3990 0404 b900 0300  ,...,...9.......
00000040: 02b2 51c1 e108 43cd 804b 58cd 8046 4c45  ..Q...C..KX..FLE
00000050: 7f                                       .

$ ./test_script.sh solution_3_with_bug.bin
[+] 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: 81

Le code utilisé ici est similaire à celui présenté comme la solution minimale :

90          nop
04 04       add $4, %al           ; eax = 4
b9 00030002 mov $0x02000300, %ecx ; ecx = 0x02000300
b2 51       mov $0x51, %dl        ; edx = 81 (file size)
c1 e1 08    shl $8, %ecx          ; ecx = 0x00030000
43          inc %ebx              ; ebx = 1
cd 80       int $0x80             ; write(1, 0x00030000, 81)
4b          dec %ebx              ; ebx = 0
58          pop %eax              ; eax = 1
cd 80       int $0x80             ; exit(0)

$ readelf --program-headers solution_3_with_bug.bin
...
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x00002c 0x0003002c 0x04049039 0x300b9 0xc151b202   E 0xcd584b80

🏁 Conclusion

Réaliser un fichier ELF aussi petit que possible est un moyen agréable d'explorer la tolérance du noyau Linux lors du traitement des fichiers ELF. Cela a été l'occasion de découvrir de nouvelles techniques pour créer des programmes qui se chargent et s'exécutent correctement, mais qui provoquent l'échec les outils habituels :

$ file ./solution_3_minimal.bin
./solution_3_minimal.bin: ELF, unknown class 128

$ objdump -x ./solution_3_minimal.bin
objdump: ./solution_3_minimal.bin: file format not recognized

$ gdb ./solution_3_minimal.bin
...
"/vagrant/./solution_3_minimal.bin": not in executable format: file format not recognized

$ ./solution_3_minimal.bin | base64
f0VMRoDNWEuAzVGyRQjhwQIAAwC5BARDOQADACwAAAAsAAAAAQAgXl9eIAABAAAALAAAACwAAwA5
QwQEuQADAALB4QhFslHNgEtYzYBGTEV/

Merci aux auteurs et aux organisateurs du challenge d'avoir proposé un événement aussi sympathique !

La solution de Synacktiv

1. Première étape : exclure les mauvaises pistes

Ce challenge peut être divisé en deux parties. La première est de créer un palindrome ELF que le noyau Linux voudra bien charger, la seconde est de faire en sorte que ce soit un quine. Comme précisé dans le write-up de IooNag ci-dessus, le noyau Linux ne vérifie pas tout les champs présents dans le binaire. Le noyau charge la première page du binaire et remplit le reste de la page par des zéros. Il lit ensuite le header ELF présent à l'offset 0 puis itère dans les program headers pour trouver ce qu'il doit charger.

En admettant que la solution proposée sera composée d'un seul segment qui contiendra le code, on peut rechercher quel offset du program header permettra d'obtenir un programme potentiellement valide. Par exemple, seules quelques valeurs sont acceptées pour le champ p_type du program header et 0x7f454c46 ('\x7fELF', les octets magiques ELF) n'en fait pas partie. Par conséquent, l'offset 0 est inutilisable pour placer le program header.

En utilisant la logique, on peut construire un header ELF basique, un program header basique et des masques binaires pour chacun qui permettent de savoir quels bits sont fixés. À l'aide de ces masques, on peut déterminer si une paire (taille du binaire, offset du program header) est potentiellement valide.

elf_value = bytes.fromhex("7f454c46 010000000000000000000000 0200 0300 00000000 00000000 00000000 00000000 00000000 0000 2000 0100")
elf_mask = bytes.fromhex("ffffffff ff0000000000000000000000 ffff ffff 00000000 000f0000 00ffffff 00000000 00000000 0000 ffff ffff")
phr_value = bytes.fromhex("01000000 00000000 00000000 00000000 00000000 00000000 04000000 00000000")
phr_mask = bytes.fromhex("ffffffff ffffffff ff0f0000 00000000 00000000 00000000 04000000 00000000")

def test(val, mask, index, byte, bytemask):
    if index >= len(val) or index < 0:
        assert (byte & bytemask) == 0
    else:
        ov = val[index]
        om = mask[index]
        mask[index] |= bytemask
        val[index] |= bytemask & byte
        assert (val[index] & om) == (ov & om)
        assert (val[index] & bytemask) == (byte & bytemask)

def bind_palindrome(val, msk, index, bv, bm):
    for i, (x, m) in enumerate(zip(bv, bm)):
        test(val, msk, index + i, x, m)
        test(val, msk, len(val) - 1 - index - i, x, m)

def build_pal(full_size, hdr_off):
    m_elf_value = bytearray(elf_value)
    m_elf_mask = bytearray(elf_mask)
    m_elf_value[28] = hdr_off
    m_elf_mask[28] = 0xff

    res =  bytearray([0] * full_size)
    mask = bytearray([0] * full_size)

    bind_palindrome(res, mask, 0, m_elf_value, m_elf_mask)
    bind_palindrome(res, mask, hdr_off, phr_value, phr_mask)

    bind_palindrome(res, mask, hdr_off + 9, res[25:28], mask[25:28])
    bind_palindrome(res, mask, 25, res[hdr_off + 9:hdr_off + 12], mask[hdr_off + 9:hdr_off + 12])

    return res, mask

On trouve en utilisant ce code que l'offset 4 est potentiellement valable pour les tailles de binaire de 65 octets à 69 inclus et de 77 à 85. L'offset 44 est valable pour les tailles 83 et 84, de même que l'offset 46 pour la taille 85.

Les tailles possibles suivantes sont de 89 puis 91.

2. L'offset 44 dans un ELF de 83 octets

Le programme ci-dessus permet aussi d'obtenir un masque global pour le fichier final ainsi qu'une sorte de squelette du fichier. L'offset 44 et la taille 83 a la très bonne propriété de laisser une grande plage d'octets non contraints à partir de l'offset 5 (ou 67).

7f454c46010000000000000000000400020003000000000000002c002c000000000000000000010020002000010000000000000000002c002c00000000000000030002000400000000000000000001464c457f
ffffffffff0000000000000000000400ffffffff0000000000ffff00ffffffffffffffffffffffffff00ffffffffffffffffffffffffff00ffff0000000000ffffffff0004000000000000000000ffffffffff

# ELF header
magic        7f454c46   ffffffff   [0, 1, 2, 3]         [82, 81, 80, 79]
padding1     01000000   ff000000   [4, 5, 6, 7]         [78, 77, 76, 75]
padding2     00000000   00000000   [8, 9, 10, 11]       [74, 73, 72, 71]
padding3     00000400   00000400   [12, 13, 14, 15]     [70, 69, 68, 67]
e_type       0200       ffff       [16, 17]             [66, 65]
e_machine    0300       ffff       [18, 19]             [64, 63]
e_version    00000000   00000000   [20, 21, 22, 23]     [62, 61, 60, 59]
e_entry      00002c00   00ffff00   [24, 25, 26, 27]     [58, 57, 56, 55]
e_phoff      2c000000   ffffffff   [28, 29, 30, 31]     [54, 53, 52, 51]
e_shoff      00000000   ffffffff   [32, 33, 34, 35]     [50, 49, 48, 47]
e_flags      00000100   ffffffff   [36, 37, 38, 39]     [46, 45, 44, 43]
e_ehsize     2000       ff00       [40, 41]             [42, 41]
e_phentsize  2000       ffff       [40, 39]             [42, 43]
e_phnum      0100       ffff       [38, 37]             [44, 45]

# Program header
p_type       01000000   ffffffff   [38, 37, 36, 35]     [44, 45, 46, 47]
p_offset     00000000   ffffffff   [34, 33, 32, 31]     [48, 49, 50, 51]
p_vaddr      00002c00   ffffff00   [30, 29, 28, 27]     [52, 53, 54, 55]
p_paddr      2c000000   ffff0000   [26, 25, 24, 23]     [56, 57, 58, 59]
p_filesz     00000000   000000ff   [22, 21, 20, 19]     [60, 61, 62, 63]
p_memsz      03000200   ffffff00   [18, 17, 16, 15]     [64, 65, 66, 67]
p_flags      04000000   04000000   [14, 13, 12, 11]     [68, 69, 70, 71]
p_align      00000000   00000000   [10, 9, 8, 7]        [72, 73, 74, 75]

3. Le code du quine

L'espace disponible dans la configuration choisie est de 11 octets libres (à l'exception d'un octet qui a un bit contraint), puis 4 octets après 02000300. L'octet suivant, à l'offset 24, est libre mais correspond à l'octet de poids faible du point d'entrée. La solution proposée était initialement positionnée dans la partie basse du fichier et a ensuite été placée dans la partie haute où les 11 octets libres sont situés après la constante 00030002.

Une mauvaise propriété du point choisi est de forcer l'offset de chargement de notre page à cause de l'octet 2c à l'offset 26.

Le shellcode qui sera intégré devra d'abord mettre eax à la valeur 4, mettre ebx à 1 (stdout), ecx au début de la page courante (0x2c0000, sauf si on change l'octet 27), edx à 83, la taille du shellcode, faire un syscall, puis mettre 1 dans eax, 0 dans ebx puis faire un autre syscall.

Après des premiers essais à essayer de faire loger cette solution dans le ELF, le principe du shellcode a été changé.

On a au milieu de notre plage libre une constante 00030002. On voudrait pouvoir l'ignorer en ajoutant le moins d'octets possible avant. Ceci peut être fait en un octet en ajoutant un instruction de push (6a) avant ou une instruction cmp. push ne nous arrange pas étant donné que le 1 en haut de la stack pourra être pratique plus tard. cmp est plus pratique et nous permettrait de faire un jump conditionnel.

Le fichier ELF chargé ne contient qu'un seul segment à charger mais lors du chargement, le noyau ajoute une zone mémoire pour la stack et une zone mémoire vdso. La zone mémoire vdso est toujours située à une adresse très élevée et la stack est habituellement placée plus haut que notre page éxecutable.

Ceci implique que la page la plus basse chargée par le programme est notre fichier ELF. Tout appel à write de taille non-nulle avec un offset plus faible retournera donc -EINVAL dans eax. La comparaison effectuée avec 00030002 permet donc de bruteforcer l'adresse de notre fichier ELF en comparant eax après le syscall. Ceci nous permet de ne pas avoir à mettre l'offset dans ecx, ce qui s'était montré octet-o-phage.

On ne sait pas encore où notre jump conditionnel sautera mais on peut commencer le shellcode :

.before_gap:
    ; 1 free byte
    int 0x80             # cd80
    cmp eax, 0x02000300  # 3d00030002
.after_gap:
    jc somewhere         # 72xx
    ; 9 free bytes

On devra a priori jumper sur int 0x80 si on a pas pris le jump conditionnel.

.before_gap:
    ; 1 free byte
    int 0x80             # cd80
    cmp eax, 0x02000300  # 3d00030002
.after_gap:
    jc somewhere         # 72xx
    jmp .before_gap      # ebxx
    ; 7 free bytes

eax est effacé lors du write, la manière la plus simple de le rétablir est de pousser 4 et de pop dans eax. On doit ajouter de plus l'instruction mov 83, dl et  inc ecx.

    ; 1 free byte
.before_gap:
    int 0x80             # cd80
    cmp eax, 0x02000300  # 3d00030002
.after_gap:
    jc somewhere         # 72xx
    push 4               # 6a04
    inc ecx              # 43
    pop eax              # 58
    mov dl, 83           # b253
    jmp .before_gap      # ebxx
    ; 1 free byte

On peut essayer de n'utiliser qu'une seule instruction int 0x80 pour économiser deux octets et de s'en servir pour le call à exit.

On peut choisir que le jmp conditionnel est pris que si write a marché. Dans ce cas, eax doit recevoir la valeur 1 et pas 4 et ebx doit être zéro. On peut sauter au dessus de push 4 pour pop le 1 en haut de la stack plutôt que 4 pour obtenir la bonne valeur dans eax. Le code devient :

    ; 1 free byte
.before_gap:
    int 0x80             # cd80
    cmp eax, 0x02000300  # 3d 00030002
.after_gap:
    jc somewhere         # 72xx
    push 4               # 6a04
.somewhere:
    inc ecx              # 43
    pop eax              # 58
    mov dl, 83           # b253
    jmp .before_gap      # ebxx
    ; 1 free byte

ebx vaut zéro au début de l'exécution et doit valoir 1 pour les write et 0 pour exit. mov ebx, 1 prend 5 octets, il nous en reste deux au total. inc ebx n'en prend qu'un, de même que dec ebx. En plaçant soigneusement ces instructions, on peut obtenir que ebx ait la bonne valeur lors des calls :

.before_gap:
    int 0x80             # cd80
    dec ebx              # 4b
    cmp eax, 0x02000300  # 3d 00030002
.after_gap:
    jc somewhere         # 72xx
    push 4               # 6a04
    inc ebx              # 43
.somewhere:
    inc ecx              # 43
    pop eax              # 58
    mov dl, 83           # b253
    jmp .before_gap      # ebxx

Le bit contraint 04 tombe sur le deuxième octet de jc somewhere. En bougeant un peu les instructions, on peut obtenir le code suivant :

.before_gap:
    int 0x80             # cd80
    dec ebx              # 4b
    cmp eax, 0x02000300  # 3d 00030002
.after_gap:
    jc .end              # 7204
    inc ebx              # 43
    push 4               # 6a04
    inc ecx              # 43
.end:
    pop eax              # 58
    mov dl, 83           # b253
    jmp .before_gap      # ebed

Le point d'entrée doit être placé sur l'instruction inc ebx pour bien obtenir le comportement souhaité sur ebx.

Le shellcode final fonctionne et permet d'obtenir une solution non seulement valide mais aussi particulièrement lente, ce qui permet d'envoyer ses collègues dans des mauvaises directions.

Classement alternatif

1. Injection de commande par XeR

Le script de test initial, publié avec l'article présentant ce challenge, contenait une vulnérabilité qui n'a pas échappé au regard aiguisé de XeR. Le nom du fichier fourni par l'utilisateur était utilisé sans précautions dans la construction de l'image Podman qui servait à contenairiser l'exécution du binaire :

binary=$1

[...]

cat > "$containerfile" <<EOF
FROM scratch
COPY $binary /binary
CMD ["/binary"]
EOF

Par conséquent, il était possible d'injecter des commandes dans le Containerfile en définissant un nom de fichier bien précis. Pour exploiter cette faiblesse du script, XeR avait envoyé une archive composée du fichier :

*# b\nENV PATH=.\nENTRYPOINT ["b", "", "", "", "", "", "",  "j@X4AP[h@@@@X%  @ PYjCZjDX4@<0340>K4B<0340>"]\n#.

Voici le Contenairefile obtenu, dont les lignes 2. à 5.  étaient injectées :

1. FROM scratch
2. COPY *# b
3. ENV PATH=.
4. ENTRYPOINT ["b", "", "", "", "", "", "",  "j@X4AP[h@@@@X%  @ PYjCZjDX4@<0340>K4B<0340>"]
5. #/binary
6. CMD ["/binary"]

La commande COPY *# b ligne 2. sert à sélectionner le binaire, dont le nom fini par un '#',  et à le copier dans l'image à la racine, avec le nom "b".

Rappelons que le caractère "/" n'est pas autorisé dans un nom de fichier, car il correspondrait alors à un séparateur dans le chemin du fichier. Il était donc impossible de spécifier un ENTRYPOINT avec le chemin absolu vers le binaire à exécuter : "/b". C'est pour cette raison que la ligne 3. définie la variable d'environnement PATH sur le répertoire courant, afin que le binaire soit localisé dans ce répertoire.

Enfin, la ligne 4. contient l'ENTRYPOINT, dont le 7ème argument est le shellcode qui sera appelé lors de l'exécution. Comme dans les autres solutions, ce shellcode va utiliser les appels systèmes  write et exit pour valider les exigences du challenge.

Grâce à la mise en place de ces techniques ingénieuses, XeR avait réussi à obtenir un score de 67 qui validait le script de test (cf. sa solution) :

$ hexdump -C \*\#\ b$'\n'ENV\ PATH=.$'\n'ENTRYPOINT\ \[\"b\",\ \"\",\ \"\",\ \"\",\ \"\",\ \"\",\ \"\",\ \ \"j@X4AP\[h@@@@X%\ \ @\ PYjCZjDX4@<0340>K4B<0340>\"\]$'\n'\#
00000000  7f 45 4c 46 01 00 00 00  00 00 00 00 00 00 40 00  |.ELF..........@.|
00000010  02 00 03 00 00 00 01 00  20 00 40 00 04 00 00 00  |........ .@.....|
00000020  61 c3 61 00 00 00 04 00  40 00 20 00 01 00 00 00  |a.a.....@. .....|
00000030  03 00 02 00 40 00 00 00  00 00 00 00 00 00 01 46  |....@..........F|
00000040  4c 45 7f                                          |LE.| 

Par la suite, le script de test a été mis à jour pour corriger cette vulnérabilité.

2. Mapping du segment à l'adresse 0x00 par matt

matt nous a partagé cette solution intéressante :

$ hexdump -C matt.bin 
00000000  7f 45 4c 46 01 db eb 39  43 8a 4d b2 02 8a 4d b2  |.ELF...9C.M...M.|
00000010  02 00 03 00 5b 00 00 00  2c 00 00 00 2c 00 00 00  |....[...,...,...|
00000020  01 00 20 40 cd 80 5b 80  cd 40 20 00 01 00 00 00  |.. @..[..@ .....|
00000030  2c 00 00 00 2c 00 00 00  5b 00 03 00 02 b2 4d 8a  |,...,...[.....M.|
00000040  02 b2 4d 8a 43 39 eb db  01 46 4c 45 7f           |..M.C9...FLE.|

Pour que celle-ci fonctionne, il faut ajouter l'option --privileged à la commande podman run, et exécuter le script en sudo. En effet, matt a remarqué qu'en s'exécutant dans un contexte suffisamment privilégié, il était possible de définir l'adresse de base où charger le segment en mémoire à 0x00 (plus un offset de 0x2c), et ainsi réduire le binaire à seulement 77 octects.
L'entrée n'a pas été validée car elle implique de modifier le script de test, mais nous le félicitons néanmoins pour ce score !

3. Haiku nocturne par rick

Pour finir ce classement alternatif, voici un poème de rick, qui semble avoir été inspiré par les heures tardives passées à travailler sur ce quinindrome :

Au fond de la nuit,
J'écris des octets sur Vim,
Un petit binaire.

Conclusion

Merci encore à tous les participants, pour le temps et la créativité dont ils ont fait preuve pendant cette compétition.

À cet été pour le prochain challenge !

Engage le jeu, que je le gagne !