Solution de thierryb_77285 pour Mazetodon

Table des matières

Étape 1 : reconnaissance

Il s’agit d’un programme ELF pour LINUX qui est classiquement strippé.

Le nom du programme laisse penser que l’on sera confronté à un moment à un labyrinthe.

Un coup de strings sur le programme fait remonter quelques chaines intéressantes :

% strings mazetodon
...
/tmp/mazetodon_%d
mkfifo
open fifo
...

Effectivement, si on lance le programme, on voit bien qu’il crée dans /tmp 7 pipes :

% ls -l /tmp/
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_0
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_1
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_2
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_3
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_4
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_5
prw-r--r-- 1 besancon besancon 0 Jul 29 19:33 /tmp/mazetodon_6

Vraisemblablement on va communiquer avec le programme via ces pipes. Si l’on a affaire à un labyrinthe, 4 de ces pipes servent peut-être pour aller dans les 4 directions ? On verra pour les 3 autres.

On voit via ldd que le programme utilise du chiffrement (les noms sortaient aussi au moment du strings) :

% ldd mazetodon
	linux-vdso.so.1 (0x00007fffa5dca000)
	libcrypto.so.3 => /lib/x86_64-linux-gnu/libcrypto.so.3 (0x0000799a4fe00000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x0000799a4fc1f000)
	/lib64/ld-linux-x86-64.so.2 (0x0000799a50330000)

Un strings ne renvoie rien de type message de réussite. Un message ou un flag est certainement chiffré au sein du binaire et sera affiché en cas de réussite du challenge.

Étape 2 : décompilation

On passe le programme fourni dans des outils de décompilation, IDA, GHIDRA, BINARY NINJA, ANGR, etc. On peut utiliser pour cela le site https://dogbolt.org qui propose online divers outils de ce genre. Ma préférence va à IDA cette fois-ci.

Le code n’est pas très long. On trouve 13 fonctions nous intéressant :

adresse 0x14d9
adresse 0x15d3
adresse 0x1709
adresse 0x17b6
adresse 0x1844
adresse 0x1bf0
adresse 0x1ca4
adresse 0x1dd6
adresse 0x208c
adresse 0x2104
adresse 0x2232
adresse 0x2489
adresse 0x2630

(les adresses ci-dessus sont visibles par un désassemblage par objdump -M intel --disassemble mazetodon aussi bien que par IDA).

Passons les en revue.

Étape 3 : fonction à l’adresse 0x2630 : main

IDA reconnait la fonction et la renvoie directement. Avec GHIDRA, on trouve la fonction classiquement via l’appel à libc_start_main() ou via la fonction entry().

La fonction main fait globalement ceci

Elle configure un handler qui sera appelé lors de l’exit du programme.
Elle initialise une structure de données via la fonction en 0x2232.
Elle met en place les 7 pipes dont on parlait au début et se met en attente d’arrivée de data sur ces pipes et aiguille ce qui arrive vers la fonction 0x2104().

Logiquement, on va vers la fonction en 0x2232.

Étape 3 : fonction à l’adresse 0x2232 : initialisation de data

S’il y a un labyrinthe, il faut en construire le plan. Vraisemblablement cette fonction s’en charge.

On remarque que cette fonction ne prend pas de paramètre mais renvoie un pointeur. Au pire, il suffit de la laisser faire et de voir ce qu’elle renvoie à la fin.

Sur cette fonction, je constate une fois de plus (je me trompe souvent) qu’il faut faire attention aux types que l’on manipule. Est-ce un char, un int32, un int64, etc ? C’est important ici car on voit qu’il y a un tableau et donc un saut d’indice fait se déplacer de 1, 4, 8 bytes etc. selon le type des éléments du tableau.

Si l’on analyse mieux, on se rend compte que l’on alloue une zone mémoire a priori de uint32 organisée de la façon suivante. Tout au long de ce write up, je désignerai par la variable m cette zone mémoire.

Organisation de m :

m : zone obtenue par un malloc() de 0x590 = 1424 bytes ou dit autrement 0x164 = 356 uint32 (selon le cas, on retrouve ces valeurs exprimées en décimal ou hexadécimal)
m[0] : un uint32 initialisé à 1
m[1] : un uint32 initialisé à 9
m[2] : un uint32 initialisé à 0
m[3..93] : une zone de 91 uint32 qui sera lue en fait comme des unsigned char
m[94] : un uint64 initialisé à 0
m[96] : un uint64 initialisé à 0
m[97] : un uint32 initialisé à 0
m[98] : un uint32 initialisé à 0
m[99..356] : des uint32 initialisés à 0

Je n’ai pas cherché à comprendre la construction des murs du labyrinthe.

On y voit une expression qui reviendra souvent dans le code sous globalement cette forme que je vous réécris progressivement pour montrer l’idée :

*((_BYTE *)v5 + 19 * *v5 + v5[1]++ + 12) =
(char*)v5[ 19 * v5[0] + v5[1]++ + 12 ] = ...
(char*)v5[ 12 + 19 * v5[0] + v5[1]++ ] = ...
(char*)v5[ 12 + 19 * y + x ] = ...

On manipule donc ici des char. 12, c’est la taille de nos 3 premiers uint32. Puis on a le codage d’un point dans un carré ou rectangle. C’est le labyrinthe.

m[0] désigne donc une ligne du labyrinthe.
m[1] désigne donc une colonne du labyrinthe.
Un mur du labyrinthe est codé par le caractère ASCII 66 (0x42) donc B (B comme Brique ?).
Une case libre est codé par la valeur ASCII 0.

Dessinons le tableau des char qui donne le labyrinthe, en sortie de 0x2232 :

labyrinthe

On comprend au final que l’on part de la position (x=9,y=1).

Récapitulatif :

On a le plan du labyrinthe, notre position initiale dans le labyrinthe.
On a 7 pipes dans lesquels on peut écrire.

La fonction qui traite les pipes est en 0x2104. Analysons la, puis nous analyserons ce que permettent de faire les pipes.

Étape 3 : fonction à l’adresse 0x2104

Son paramètre 1 est m.

Sans surprise, on trouve un switch dans la fonction selon le pipe que l’on traite. On se doute que les pipes 0, 1, 2 et 3 seront des déplacements dans le labyrinthe traités par la fonction en 0x1ca4.

On note que le pipe 4 est le seul à utiliser ce qui lui est écrit.

On verra le cas des pipes 5 et 6 plus tard.

Étape 3 : fonction à l’adresse 0x1ca4

C’est la fonction associée aux pipes 0, 1, 2 et 3.

On voit que cette fonction est appelée avec les jeux suivants de paramètres : (0, 1), (0, -1), ( 1, 0), (-1, 0).

Dans un contexte de labyrinthe, ca sent bien le déplacement dans le labyrinthe: gauche, droite, haut, bas.

On se doutait que le labyrinthe avait la largeur 19 vu sa construction. On trouve ici confirmation que sa hauteur est aussi 19. En effet, après application du déplacement d’une case, on ne doit jamais dépasser 0x12. Donc on va des cases 0 à 0x12 = 18.

On voit qu’on ne peut se déplacer que sur une case valant 0. Si on se déplace sur une case autre donc invalide, on écrit 1 dans m[2]. Ce m[2] agit donc comme un « registre d’erreur » qui ne peut jamais être remis à 0. Si l’on regarde tout le code du programme, on retrouvera sans cesse que ce registre d’erreur est « ORé » avec 1 en cas d’erreur. A la moindre erreur, le registre est donc levé. Le programme ne pardonne aucune erreur de la part du joueur.

La fonction ne s’arrête pas là. Elle continue par 2 autres actions.

Commençons par la seconde action :

++a1[98];

On mémorise ici le nombre de déplacements (ou de pas) dans le labyrinthe dans m[98] puisqu’on incrémente à chaque déplacement.

Revenons à la première action que je réécris pour en comprendre l’idée:

*((_BYTE *)a1 + 2 * a1[98] + 396) = *a1;
*((_BYTE *)a1 + 2 * a1[98] + 397) = a1[1];
m[ 99 + 0 + 2 * nombre-de-pas ] = m[0] ;
m[ 99 + 1 + 2 * nombre-de-pas ] = m[1] ;

On mémorise le chemin de déplacement dans le labyrinthe…

Étape 3 : fonction à l’adresse 0x1dd6 (1/2)

C’est la fonction associée au pipe 4.

C’est la fonction qui m’a posé le plus de souci parce que son code, court, est étrange.

Pour le suspense, je vais simplement résumer cette fonction comme écrivant sur une case libre du labyrinthe une valeur de 1 à 9 transmise via le pipe (mais peut-être que vous devinez déjà de quoi il s’agit…).

Étape 3 : fonction à l’adresse 0x208c

C’est la fonction associée au pipe 5.

Son rôle est d’enregistrer la position courante sur demande explicite du joueur. On comprend mieux cette fonction si on l’écrit sous la forme suivante (rappel m[94] et m[96] sont des uint64) :

m[94] = (m[94] << 4) ^ ((m[0] - 1) / 2) ;
m[96] = (m[96] << 4) ^ ((m[1] - 1) / 2) ;

On shifte d’un nibble et on stocke la coordonnée courante x ou y mais comme les coordonnées vont de 0 à 18, ca ne tient pas sur un nibble donc l’auteur du challenge réduit sur 4 bits en prenant la partie entière de la moitié de la coordonnée.

Il faut comprendre cela de la façon suivante : on doit suivre un certain chemin dans le labyrinthe et enregistrer sur certaines cases qu’on est passé par elles. J’appellerai cela les breadcrumbs du labyrinthe.

Pour gagner, le programme vérifiera qu’on est passé par une certaine liste hardcodée dans le binaire, de cases.

En l’occurrence, la liste hardcodée se voit dans la fonction en 0x1844 :

maze[ 2 ] |= ( maze[ 94 ] != 0x0007780041024858 );
maze[ 2 ] |= ( maze[ 96 ] != 0x0004688563022204 );

Par quelles cases doit-on passer alors ? A priori on ne va pas pouvoir savoir exactement la case (x,y) à cause de la réduction de valeur 0 à 18 vers 4 bits qui laisse le choix entre 4 cases possibles au final mais en fait, si, on va savoir précisemment, en regardant à chaque fois si l’une des cases n’est pas un mur et si c’est un mur, cette case n’est pas éligible. Puis on fera jouer l’instinct.

Il faut lire de gauche à droite. Il faut passer par 13 cases imposées.

breadcrumb 1 : (7,4) donne le choix entre 2 cases possibles (9,15) ou (10,15)
breadcrumb 2 : (7,6) donne le choix entre 2 cases possibles (13,15) ou (14,15)
breadcrumb 3 : (8,8) donne la case (17,17)
breadcrumb 4 : (0,8) donne la case (17,1)
breadcrumb 5 : (0,5) donne le choix entre 2 cases possibles (11,1) ou (12,1)
breadcrumb 6 : (4,6) donne le choix entre 2 cases possibles (13,9) ou (13,10)
breadcrumb 7 : (1,3) donne le choix entre 2 cases possibles (7,3) ou (8,3)
breadcrumb 8 : (0,0) donne le choix entre 2 cases possibles (1,1) ou (2,1)
breadcrumb 9 : (2,2) donne le choix entre 2 cases possibles (5,5) ou (5,6)
breadcrumb 10 : (4,2) donne la case (5,9)
breadcrumb 11 : (8,2) donne la case (5,17)
breadcrumb 12 : (5,0) donne le choix entre 2 cases possibles (1,11) ou (1,12)
breadcrumb 13 : (8,4) donne le choix entre 2 cases possibles (9,17) ou (9,18)

Si l’on regarde bien, on comprend que l’auteur a mis les breadcrumbs sur les cases qui sont des culs de sac dans le labyrinthe. Donc au final, on a :

breadcrumb 1 : (7,4) donne la case (9,15)
breadcrumb 2 : (7,6) donne la case (13,15)
breadcrumb 3 : (8,8) donne la case (17,17)
breadcrumb 4 : (0,8) donne la case (17,1)
breadcrumb 5 : (0,5) donne la case (11,1)
breadcrumb 6 : (4,6) donne la case (13,9)
breadcrumb 7 : (1,3) donne la case (7,3)
breadcrumb 8 : (0,0) donne la case (1,1)
breadcrumb 9 : (2,2) donne la case (5,5)
breadcrumb 10 : (4,2) donne la case (5,9)
breadcrumb 11 : (8,2) donne la case (5,17)
breadcrumb 12 : (5,0) donne la case (1,11)
breadcrumb 13 : (8,4) donne la case (9,17)

breadcrumbs

Via les pipes 0 à 3, on se déplace pour passer par les cases ci-dessus et on s’enregistre sur ces cases par le pipe 5.

Le chemin est facile à trouver :

up	2
right	2
up	4
right	4
up	4
right	2
up	2
left	2
up	4
left	4
down	2
left	2
right	2
up	2
right	4
down	2
left	2
right	2
down	2
right	2
up	4
down	14
left	2
down	2
right	2
left	2
up	2
right	2
up	2
left	4
down	4
left	2
right	2
up	4
right	4
up	6
left	2
down	4
left	4
up	6
right	2
down	4
up	4
left	2
down	10
left	4
right	2
down	2
left	8
right	4
up	2
left	2
up	4
right	2
down	2
up	2
left	2
down	4
left	2
up	6
right	4
left	2
up	6
left	2
up	2
right	4
left	4
down	6
up	4
right	2
down	4
right	4
down	6
right	2
up	8
left	4
up	2
right	2
up	2
right	2

path

Avant de passer à la fonction 0x1844 du pipe 6, visitons la petite fonction 0x1709.

Étape 3 : fonction à l’adresse 0x1709

Cette fonction accepte un tableau de 9 entiers et vérifie si les éléments du tableau sont tous différents. Si c’est le cas, on renvoie 1 (true) sinon 0 (false).

Hmmm… 9… Cela m’a fait tout de suite penser à un autre type de jeu où 9 chiffres doivent être tous différents.

Étape 3 : fonction à l’adresse 0x1844

C’est la fonction associée au pipe 6.

Cette fonction semble construire des contraintes à satisfaire.

Je vais utiliser le terme de « case impaire ». Une telle case a ses 2 coordonnées ligne et colonne impaires.

Contrainte 1 : elle porte sur les colonnes impaires du labyrinthe. On en prend les case impaires, il y en a 9 et cela doit satisfaire la fonction 0x1709.

Contrainte 2 : elle porte sur les lignes impaires du labyrinthe. On en prend les case impaires, il y en a 9 et cela doit satisfaire la fonction 0x1709.

Contrainte 3 : elle porte sur des sous-blocs du labyrinthe. Au sein d’un sous-bloc, chaque case « impaire » doit être différente.

Euh… on ne serait pas en train de faire un sudoku sur les cases impaires du labyrinthe, là ?

Contrainte 4 : la diagonale descendante des cases impaires satisfait 0x1709.

Contrainte 5 : la diagonale montante des cases impaires satisfait 0x1709.

C’est dit. En plus d’un labyrinthe, on joue aussi à un sudoku étendu à ses diagonales.

sudoku-empty

Contrainte 6 et 7 : elles portent sur les breadcrumbs du parcours dans le labyrinthe. Voir les explications sur la fonction en 0x208c ci dessus.

Contrainte 8 : elle porte sur le nombre de pas à faire dans le labyrinthe. On ne peut faire que 268 pas.

Contrainte 9 : elle demande que le registre d’erreur vaille 0.

Moyennant que toutes ces contraintes sont satisfaites, on appelle la fonction 0x17b6.

Étape 3 : fonction à l’adresse 0x17b6

Cette fonction fait appel à deux autres fonctions.

Fonction à l’adresse 0x14d9

Cette fonction fait appel à des fonctions de chiffrement bien identifiées par les décompilateurs.

On reconnait que cette fonction calcule un SHA256 de la zone mémoire passée en paramètre.

Fonction à l’adresse 0x15d3

Idem, cette fonction fait appel à des fonctions de chiffrement bien identifiées par les décompilateurs.

On reconnait que cette fonction déchiffre un secret passé via pointeur, chiffré en AES-256-ECB dont la clef est passée en paramètre.

Déchiffrement du secret

On comprend donc qu’on utilise la structure mémoire du labyrinthe comme entrée de la fonction 0x14d9(), on en fait un hash SHA256. Ce hash est la clef qui déchiffre cette zone mémoire du binaire :

00003020: 9e0f 4778 331b b3f0 aa90 84d5 cdd3 82bf
00003030: ef3d fbad 343b 5b3d 0dff 085d 8389 de15
00003040: 819e a993 7924 3678 44bc 20c3 89f2 d423
00003050: 2053 dc41 6421 8904 0723 2e5c 1fb7 2a6c
00003060: 5247 6e5b ba29 05c4 72cd 3270 26f8 619d
00003070: a5aa 19a1 05a0 1ac7 a8b8 9880 0a88 5731
00003080: 3943 d16b 4e98 c8d1 fa5f 51ed 3848 5fe3
00003090: e934 f5b7 8fdc ef3c 1ce4 c8c4 6361 fcde
000030a0: 55a6 3298 dc32 cb41 dc56 2d15 5a7d a512
000030b0: 2f2d 85d2 e9f2 06a6 4c84 e9f2 a746 3cb2
000030c0: 844a 00dc d04e d72b c853 0a68 cc82 08de
000030d0: 7f9a 5feb 695b 5991 1295 ce42 688b 417a
000030e0: 76d4 b21c b383 5f34 7cb0 3de0 4ec9 2f63
000030f0: 63b7 43f4 d4cb 0c20 9674 5b9a aea5 a424
00003100: b080 ecb0 3396 29c4 a3e7 fa7b c57c a195
00003110: d3ee 320e db0c 9770 2a7a f169 fc76 6ab3
00003120: f66c 7a10 003c 88af a6a0 92e0 ba05 d093
00003130: 409d 1b09 b1b6 082b 1497 e73d c408 ab76
00003140: 6235 9ecf 7bc5 7d03 e3a8 bdee 846a decd

On a presque tout reversé à ce niveau… Reste à revenir sur la fonction 0x1dd6.

Étape 3 : fonction à l’adresse 0x1dd6 (2/2)

Que nous manque-t-il ? Que sait-on faire ?

On sait se déplacer dans le labyrinthe.
On sait comment parcourir le labyrinthe via les breadcrumbs.
On doit marquer son passage sur 13 cases précises.
On nous demande que les cases du labyrinthe satisfassent un sudoku étendu à ses diagonales.

Mais on n’a aucune case préremplie comme pour un sudoku classiquement ! Initialement le sudoku est vide. Que mettre dans les cases ?

On ne peut pas remplir le sudoku n’importe comment car il y a une et une seule structure mémoire permettant d’avoir le bon SHA256 servant de clef de déchiffrement.

On doit avoir classiquement comme dans un sudoku, des contraintes fournies et on complète les cases manquantes et un seul sudoku doit en être solution.

La fonction 0x1dd6 a donc un double rôle :

Elle doit permettre de remplir une case vide du sudoku par n’importe quelle valeur de 1 à 9. Ce serait classiquement les cases que déduit un joueur grâce aux autres cases pré-remplies.
Elle doit imposer de ne pouvoir écrire sur certaines cases que les valeurs de contraintes de sudoku choisies par l’auteur.

En analysant cette fonction, on trouvera donc les contraintes imposées au sudoku. On devra résoudre ensuite le sudoku qui logiquement n’aura qu’une seule solution.

J’ai eu un peu de mal sur cette fonction. Les codes décompilés sont globalement faux ou je ne les ai pas compris Au final, j’ai perdu du temps à essayer de les comprendre ou les tester alors que la vérité se trouve dans le code assembleur par construction et dans un bon manuel des instructions assembleur x86-64. Cela dit, le code décompilé donne globalement l’idée de ce que fait la fonction au début. Elle vérifie pour commencer :

si la case courante dans le labyrinthe vaut 0 sinon c’est une erreur
si l’on veut écrire une valeur entre 1 et 9 sinon c’est une erreur
si l’on est sur une case impaire sinon c’est une erreur

C’était la partie facile.

Pour cette suite, le plus simple est de partir du code assembleur généré par objdump -M intel --disassemble mazetodon. Pour ce writeup, je ne garde que les offsets et les instructions assembleur, j’élimine le code hexadécimal des instructions.

On trouve après les premières vérifications données ci-dessus un motif de quelques lignes répété 12 fois dans le code assembleur (sur le douzième bloc, il y a une toute petite différence assez mineure, on le verra).

;; Bloc  1 --------------------------------
1e76:      mov    rax,QWORD PTR [rbp-0x8]
1e7a:      mov    eax,DWORD PTR [rax]
1e7c:      sub    eax,0x4
1e7f:      cmp    eax,0x1
1e82:      ja     1e9d
1e84:      mov    rax,QWORD PTR [rbp-0x8]
1e88:      mov    eax,DWORD PTR [rax+0x4]
1e8b:      sub    eax,0x4
1e8e:      cmp    eax,0x1
1e91:      ja     1e9d
1e93:      cmp    DWORD PTR [rbp-0xc],0x1
1e97:      jne    203a
;; Bloc  2 --------------------------------
1e9d:      mov    rax,QWORD PTR [rbp-0x8]
1ea1:      mov    eax,DWORD PTR [rax]
1ea3:      sub    eax,0x4
1ea6:      cmp    eax,0x1
1ea9:      ja     1ec4
1eab:      mov    rax,QWORD PTR [rbp-0x8]
1eaf:      mov    eax,DWORD PTR [rax+0x4]
1eb2:      sub    eax,0x8
1eb5:      cmp    eax,0x1
1eb8:      ja     1ec4
1eba:      cmp    DWORD PTR [rbp-0xc],0x2
1ebe:      jne    203a
;; Bloc  3 --------------------------------
1ec4:      mov    rax,QWORD PTR [rbp-0x8]
1ec8:      mov    eax,DWORD PTR [rax]
1eca:      sub    eax,0x4
1ecd:      cmp    eax,0x1
1ed0:      ja     1eeb
1ed2:      mov    rax,QWORD PTR [rbp-0x8]
1ed6:      mov    eax,DWORD PTR [rax+0x4]
1ed9:      sub    eax,0xa
1edc:      cmp    eax,0x1
1edf:      ja     1eeb
1ee1:      cmp    DWORD PTR [rbp-0xc],0x3
1ee5:      jne    203a
;; Bloc  4 --------------------------------
...
;; Bloc 12 --------------------------------
2017:      mov    rax,QWORD PTR [rbp-0x8]
201b:      mov    eax,DWORD PTR [rax]
201d:      sub    eax,0xc
2020:      cmp    eax,0x1
2023:      ja     204f
2025:      mov    rax,QWORD PTR [rbp-0x8]
2029:      mov    eax,DWORD PTR [rax+0x4]
202c:      sub    eax,0xe
202f:      cmp    eax,0x1
2032:      ja     204f
2034:      cmp    DWORD PTR [rbp-0xc],0x8
2038:      je     204f
;;-----------------------------------------
;; On a rencontré une erreur.
;; On lève le « registre d'erreur » en le ORant avec 1.
;;-----------------------------------------
203a:      ...
...
204d:      jmp    2089
;;-----------------------------------------
;; On a entré une valeur valide.
;; On l'écrit dans la case (x,y) courante.
;;-----------------------------------------
204f:      ...
...
2088:      nop
;;-----------------------------------------
;; The end : return.
;;-----------------------------------------
2089:      nop
208a:      pop    rbp
208b:      ret

On se rappelle que :

En m[0] se trouve la ligne courante, le $Y de la case courante.
En m[1] se trouve la colonne courante, le $X de la case courante.
On passe une valeur entre 1 et 9 à tester, le $SYMBOL de la case courante.

Concrétement, le bloc suivant signifie simplement eax = $Y :

mov    rax,QWORD PTR [rbp-0x8]
mov    eax,DWORD PTR [rax]

Concrétement, le bloc suivant signifie simplement eax = $X :

mov    rax,QWORD PTR [rbp-0x8]
mov    eax,DWORD PTR [rax+0x4]

Concrétement, le bloc suivant signifie simplement cmp $SYMBOL à 1 (parfois on comparera à une autre valeur que 1) :

cmp    DWORD PTR [rbp-0xc],0x1

On fait donc :

;; Bloc  1 --------------------------------
1e76:
1e7a:      mov    eax,$Y
1e7c:      sub    eax,0x4
1e7f:      cmp    eax,0x1
1e82:      ja     1e9d
1e84:
1e88:      mov    eax,$X
1e8b:      sub    eax,0x4
1e8e:      cmp    eax,0x1
1e91:      ja     1e9d
1e93:      cmp    $SYMBOL,0x1
1e97:      jne    203a
;; Bloc  2 --------------------------------
1e9d:
1ea1:      mov    eax,$Y
1ea3:      sub    eax,0x4
1ea6:      cmp    eax,0x1
1ea9:      ja     1ec4
1eab:
1eaf:      mov    eax,$X
1eb2:      sub    eax,0x8
1eb5:      cmp    eax,0x1
1eb8:      ja     1ec4
1eba:      cmp    $SYMBOL,0x2
1ebe:      jne    203a
;; Bloc  3 --------------------------------
1ec4:      mov    rax,QWORD PTR [rbp-0x8]
1ec8:      mov    eax,$Y
1eca:      sub    eax,0x4
1ecd:      cmp    eax,0x1
1ed0:      ja     1eeb
1ed2:
1ed6:      mov    eax,$X
1ed9:      sub    eax,0xa
1edc:      cmp    eax,0x1
1edf:      ja     1eeb
1ee1:
1ee5:      jne    203a
;; Bloc  4 --------------------------------
...
;; Bloc 12 --------------------------------
2017:
201b:      mov    eax,$Y
201d:      sub    eax,0xc
2020:      cmp    eax,0x1
2023:      ja     204f
2025:
2029:      mov    eax,$X
202c:      sub    eax,0xe
202f:      cmp    eax,0x1
2032:      ja     204f
2034:      cmp    $SYMBOL,0x8
2038:      je     204f
;;-----------------------------------------
;; On a rencontré une erreur.
;; On lève le « registre d'erreur » en le ORant avec 1.
;;-----------------------------------------
203a:      ...
...
204d:      jmp    2089
;;-----------------------------------------
;; On a entré une valeur valide.
;; On l'écrit dans la case (x,Y) courante.
;;-----------------------------------------
204f:      ...
...
2088:      nop
;;-----------------------------------------
;; The end : return.
;;-----------------------------------------
2089:      nop
208a:      pop    rbp
208b:      ret

J’ai perdu du temps sur la subtilité de l’instruction ja : « jump above ». J’ai cru que cela signifiait faire un saut si le test précédent conduisait à être plus grand que la valeur testée. Oui mais non, sinon on utiliserait l’instruction jg « jump greater ». La subtilité est que ja est en mode unsigned.

Prenons le case de X=1, Y=1, SYMBOL=1 sur le bloc 1 :

;; Bloc  1 --------------------------------
1e76:
1e7a:      mov    eax,$Y
1e7c:      sub    eax,0x4  <--- A ce niveau, eax = 1 - 4 = -3 = 0xfffffffd.
1e7f:      cmp    eax,0x1  <--- On compare -3 à 1.
1e82:      ja     1e9d     <--- On saute si « above ».
1e84:
1e88:      mov    eax,$X
1e8b:      sub    eax,0x4
1e8e:      cmp    eax,0x1
1e91:      ja     1e9d
1e93:      cmp    $SYMBOL,0x1
1e97:      jne    203a
;; Bloc  2 --------------------------------
1e9d:

En pratique, on saute au bloc 2 parce que l’on compare non pas -3 (signed) mais 0xfffffffd (unsigned) qui est bien « above » 1. Pour ne pas jumper, il faut eax valant 1 ou 0 donc $Y vaut 5 car 4 est impossible car pair.

Pour ne pas jumper dans la suite du bloc 1, il faut de nouveau eax valant 1 ou 0 donc $X vaut 5 (4 est impossible).

Pour ne pas jumper dans la fin du bloc 1, il faut le symbole à 1.

Donc on comprend qu’en (X=5, Y=5), la seule valeur autorisée sera 1. Cela donne la contrainte 1 du sudoku.

Et ainsi de suite pour les 11 blocs restant.

Les 12 blocs définissent 12 contraintes du sudoku.

les 12 blocs sont construits pour s’enchainer de façon à ce que si l’on matche une case de contrainte, on ne provoque pas d’erreur et que dans le cas d’une case sans contrainte imposée par l’auteur, on puisse entrer n’importe quel symbole de 1 à 9. Il suffit de lire le code pour s’en persuader une fois qu’on a compris mes explications.

Les cases préremplies du sudoku sont donc les suivantes :

sudoku-constraints

La résolution de ce sudoku ne pose pas de souci.

J’ai utilisé pour cela un code Python appelant classiquement le solveur SMT Z3 de Microsoft. Je n’ai pas réinventé l’eau chaude. J’ai utilisé le bout de code écrit par Hakan Kjellerstrand (hakank@gmail.com), diffusé sur sa page web http://hakank.org/z3/ qui a l’avantage de confirmer l’unicité de la solution quand c’est le cas. Il faut juste y ajouter les contraintes sur les diagonales, ce qui est facile.

$ ./solve.py 
problem: mazetodon 9 x 9
9 3 8 4 6 1 5 2 7 
2 4 7 8 5 9 3 6 1 
5 6 1 7 2 3 4 9 8 
4 8 5 6 7 2 1 3 9 
7 1 2 9 3 5 8 4 6 
3 9 6 1 4 8 7 5 2 
6 7 9 5 1 4 2 8 3 
1 5 3 2 8 6 9 7 4 
8 2 4 3 9 7 6 1 5 


time: 0.6589217185974121

0.66 secondes de calcul…

sudoku-solved

On sait maintenant ce qu’il faut écrire sur les cases impaires au fur et à mesure qu’on se déplacera dans le labyrinthe.

Je rappelle qu’on ne peut se déplacer que sur les cases valant 0. Donc on ne peut plus revenir sur une case pour laquelle on a écrit la valeur dans le sudoku.

Étape 3 : fonction à l’adresse 0x1bf0

C’est une fonction qui fait le ménage des pipes. Classiquement c’est une fonction appelée dans un atexit().

Aucun intérêt.

Étape 4 : solution

On a tout compris du problème à résoudre.

Pour écrire les valeurs du sudoku, il suffit de parcourir le labyrinthe une fois en comptant combien de fois on passe par case. On le reparcourt ensuite une seconde fois et quand on passe sur une case pour l’ultime fois qu’on a calculée précédemment, on écrit la valeur de la case de sudoku.

Quand on est sur une case de breadcrumb dont on a la liste, on enregistre que l’on passe par la case breadcrumb.

Quand on atteint l’ultime case, on appelle le déchiffrement du secret.

Le programme affiche alors :

Congrats! The flag is:
flag{MHPoLKWaxofjJbJPqohiPcbCPdMzHuJWYRwUfnKduLMxyqjoRyUMyL3AT}

If you are at LeHack2025, please show the QR Code at this address to ANSSI people:
https://hackropole.fr/fr/challenges/reverse/lehack2025-reverse-mazetodon/flag-6ad409c3eb5d43ce91a1eaac86f8b6c3ded3e6248dec3cc83e.png

La conférence LeHack2025 étant finie au moment où je m’affaire au challenge, le QR Code n’est plus disponible mais le flag se valide (on s’en doute sinon on n’aurait pas pu déchiffrer et obtenir un texte intelligible).

Ci-dessous le fichier de la solution sous forme humaine. Je laisse au lecteur l’exercice de convertir en instructions sur les pipes mon code de haut niveau.

# rmove up 2 from 9 1 (line 1)...
up
up
# reached 9 3

# rmove right 2 from 9 3 (line 2)...
right
right
# reached 11 3

# rmove up 4 from 11 3 (line 3)...
up
up
up
up
# reached 11 7

# rmove right 4 from 11 7 (line 4)...
right
right
right
right
# reached 15 7

# rmove up 4 from 15 7 (line 5)...
up
up
up
up
# reached 15 11

# rmove right 2 from 15 11 (line 6)...
right
right
# reached 17 11

# rmove up 2 from 17 11 (line 7)...
up
up
# reached 17 13

# rmove left 2 from 17 13 (line 8)...
left
left
# reached 15 13

# rmove up 4 from 15 13 (line 9)...
up
up
up
up
# reached 15 17

# rmove left 4 from 15 17 (line 10)...
left
left
left
left
# reached 11 17

# rmove down 2 from 11 17 (line 11)...
down
down
# reached 11 15

# rmove left 2 from 11 15 (line 12)...
left
left
breadcrumb
sudoku 9 15
# reached 9 15

# rmove right 2 from 9 15 (line 13)...
right
right
sudoku 11 15
# reached 11 15

# rmove up 2 from 11 15 (line 14)...
up
up
sudoku 11 17
# reached 11 17

# rmove right 4 from 11 17 (line 15)...
right
right
sudoku 13 17
right
right
sudoku 15 17
# reached 15 17

# rmove down 2 from 15 17 (line 16)...
down
down
# reached 15 15

# rmove left 2 from 15 15 (line 17)...
left
left
breadcrumb
sudoku 13 15
# reached 13 15

# rmove right 2 from 13 15 (line 18)...
right
right
sudoku 15 15
# reached 15 15

# rmove down 2 from 15 15 (line 19)...
down
down
sudoku 15 13
# reached 15 13

# rmove right 2 from 15 13 (line 20)...
right
right
# reached 17 13

# rmove up 4 from 17 13 (line 21)...
up
up
up
up
breadcrumb
sudoku 17 17
# reached 17 17

# rmove down 14 from 17 17 (line 22)...
down
down
sudoku 17 15
down
down
sudoku 17 13
down
down
down
down
down
down
down
down
down
down
# reached 17 3

# rmove left 2 from 17 3 (line 23)...
left
left
# reached 15 3

# rmove down 2 from 15 3 (line 24)...
down
down
# reached 15 1

# rmove right 2 from 15 1 (line 25)...
right
right
breadcrumb
sudoku 17 1
# reached 17 1

# rmove left 2 from 17 1 (line 26)...
left
left
sudoku 15 1
# reached 15 1

# rmove up 2 from 15 1 (line 27)...
up
up
sudoku 15 3
# reached 15 3

# rmove right 2 from 15 3 (line 28)...
right
right
sudoku 17 3
# reached 17 3

# rmove up 2 from 17 3 (line 29)...
up
up
# reached 17 5

# rmove left 4 from 17 5 (line 30)...
left
left
left
left
# reached 13 5

# rmove down 4 from 13 5 (line 31)...
down
down
down
down
# reached 13 1

# rmove left 2 from 13 1 (line 32)...
left
left
breadcrumb
sudoku 11 1
# reached 11 1

# rmove right 2 from 11 1 (line 33)...
right
right
sudoku 13 1
# reached 13 1

# rmove up 4 from 13 1 (line 34)...
up
up
sudoku 13 3
up
up
sudoku 13 5
# reached 13 5

# rmove right 4 from 13 5 (line 35)...
right
right
sudoku 15 5
right
right
sudoku 17 5
# reached 17 5

# rmove up 6 from 17 5 (line 36)...
up
up
sudoku 17 7
up
up
sudoku 17 9
up
up
sudoku 17 11
# reached 17 11

# rmove left 2 from 17 11 (line 37)...
left
left
sudoku 15 11
# reached 15 11

# rmove down 4 from 15 11 (line 38)...
down
down
sudoku 15 9
down
down
sudoku 15 7
# reached 15 7

# rmove left 4 from 15 7 (line 39)...
left
left
sudoku 13 7
left
left
# reached 11 7

# rmove up 6 from 11 7 (line 40)...
up
up
up
up
up
up
# reached 11 13

# rmove right 2 from 11 13 (line 41)...
right
right
# reached 13 13

# rmove down 4 from 13 13 (line 42)...
down
down
down
down
breadcrumb
sudoku 13 9
# reached 13 9

# rmove up 4 from 13 9 (line 43)...
up
up
sudoku 13 11
up
up
sudoku 13 13
# reached 13 13

# rmove left 2 from 13 13 (line 44)...
left
left
sudoku 11 13
# reached 11 13

# rmove down 10 from 11 13 (line 45)...
down
down
sudoku 11 11
down
down
sudoku 11 9
down
down
sudoku 11 7
down
down
sudoku 11 5
down
down
sudoku 11 3
# reached 11 3

# rmove left 4 from 11 3 (line 46)...
left
left
left
left
breadcrumb
sudoku 7 3
# reached 7 3

# rmove right 2 from 7 3 (line 47)...
right
right
sudoku 9 3
# reached 9 3

# rmove down 2 from 9 3 (line 48)...
down
down
sudoku 9 1
# reached 9 1

# rmove left 8 from 9 1 (line 49)...
left
left
sudoku 7 1
left
left
left
left
left
left
breadcrumb
sudoku 1 1
# reached 1 1

# rmove right 4 from 1 1 (line 50)...
right
right
sudoku 3 1
right
right
sudoku 5 1
# reached 5 1

# rmove up 2 from 5 1 (line 51)...
up
up
sudoku 5 3
# reached 5 3

# rmove left 2 from 5 3 (line 52)...
left
left
# reached 3 3

# rmove up 4 from 3 3 (line 53)...
up
up
up
up
# reached 3 7

# rmove right 2 from 3 7 (line 54)...
right
right
# reached 5 7

# rmove down 2 from 5 7 (line 55)...
down
down
breadcrumb
sudoku 5 5
# reached 5 5

# rmove up 2 from 5 5 (line 56)...
up
up
sudoku 5 7
# reached 5 7

# rmove left 2 from 5 7 (line 57)...
left
left
sudoku 3 7
# reached 3 7

# rmove down 4 from 3 7 (line 58)...
down
down
sudoku 3 5
down
down
sudoku 3 3
# reached 3 3

# rmove left 2 from 3 3 (line 59)...
left
left
sudoku 1 3
# reached 1 3

# rmove up 6 from 1 3 (line 60)...
up
up
sudoku 1 5
up
up
sudoku 1 7
up
up
sudoku 1 9
# reached 1 9

# rmove right 4 from 1 9 (line 61)...
right
right
right
right
breadcrumb
sudoku 5 9
# reached 5 9

# rmove left 2 from 5 9 (line 62)...
left
left
sudoku 3 9
# reached 3 9

# rmove up 6 from 3 9 (line 63)...
up
up
up
up
up
up
# reached 3 15

# rmove left 2 from 3 15 (line 64)...
left
left
# reached 1 15

# rmove up 2 from 1 15 (line 65)...
up
up
# reached 1 17

# rmove right 4 from 1 17 (line 66)...
right
right
right
right
breadcrumb
sudoku 5 17
# reached 5 17

# rmove left 4 from 5 17 (line 67)...
left
left
sudoku 3 17
left
left
sudoku 1 17
# reached 1 17

# rmove down 6 from 1 17 (line 68)...
down
down
down
down
down
down
breadcrumb
sudoku 1 11
# reached 1 11

# rmove up 4 from 1 11 (line 69)...
up
up
sudoku 1 13
up
up
sudoku 1 15
# reached 1 15

# rmove right 2 from 1 15 (line 70)...
right
right
sudoku 3 15
# reached 3 15

# rmove down 4 from 3 15 (line 71)...
down
down
sudoku 3 13
down
down
sudoku 3 11
# reached 3 11

# rmove right 4 from 3 11 (line 72)...
right
right
sudoku 5 11
right
right
sudoku 7 11
# reached 7 11

# rmove down 6 from 7 11 (line 73)...
down
down
sudoku 7 9
down
down
sudoku 7 7
down
down
sudoku 7 5
# reached 7 5

# rmove right 2 from 7 5 (line 74)...
right
right
sudoku 9 5
# reached 9 5

# rmove up 8 from 9 5 (line 75)...
up
up
sudoku 9 7
up
up
sudoku 9 9
up
up
sudoku 9 11
up
up
sudoku 9 13
# reached 9 13

# rmove left 4 from 9 13 (line 76)...
left
left
sudoku 7 13
left
left
sudoku 5 13
# reached 5 13

# rmove up 2 from 5 13 (line 77)...
up
up
sudoku 5 15
# reached 5 15

# rmove right 2 from 5 15 (line 78)...
right
right
sudoku 7 15
# reached 7 15

# rmove up 2 from 7 15 (line 79)...
up
up
sudoku 7 17
# reached 7 17

# rmove right 2 from 7 17 (line 80)...
right
right
breadcrumb
sudoku 9 17
# reached 9 17

finish