vous pouvez retrouver les fichiers joint avec le chall ici
Découverte du challenge
Dans ce challenge de reverse, on tombait sur une VM un peu spéciale, fonctionnant à l’aide de tree-sitter.
Tree-sitter est une bibliothèque qui sert à analyser du code source de manière rapide et structurée.
Elle transforme un fichier de code en un arbre syntaxique (AST) facilement parcourable, avec des mises à jour incrémentales en temps réel, idéal pour des outils comme les éditeurs de texte ou l’analyse de code.Source : ChatGPT
Dans ce writeup, on va voir comment résoudre un challenge de reverse de VM sans nécessairement avoir besoin de comprendre le fonctionnement de celle-ci.
L’archive fournie avec le challenge nous donne 4 fichiers :
- un ELF
fcsclang - une lib partagée
libfcsclang.so - un programme pour la vm
program.fcsc - un fichier Dockerfile
- un fichier
run.shpermettant de lancer le docker
Analyse du binaire
Lorsque l’on ouvre la fonction principale du binaire on observe que celui-ci prend en argument un fichier contenant un programme pour la VM, initialise un parser et va parser notre programme à l’aide tree-sitter.
__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
__int64 v4; // rax
int v5; // eax
size_t v6; // rax
_QWORD v7[4]; // [rsp+10h] [rbp-F0h] BYREF
_BYTE v8[8]; // [rsp+30h] [rbp-D0h] BYREF
unsigned int v9; // [rsp+38h] [rbp-C8h]
stat buf; // [rsp+40h] [rbp-C0h] BYREF
__int64 v11; // [rsp+D8h] [rbp-28h]
unsigned __int64 st_size; // [rsp+E0h] [rbp-20h]
FILE *stream; // [rsp+E8h] [rbp-18h]
__int64 v14; // [rsp+F0h] [rbp-10h]
unsigned __int64 i; // [rsp+F8h] [rbp-8h]
if ( (int)a1 > 1 )
{
v14 = ts_parser_new(a1, a2, a3);
v4 = tree_sitter_fcsclang();
ts_parser_set_language(v14, v4);
stream = fopen(a2[1], "r");
if ( stream )
{
v5 = fileno(stream);
fstat(v5, &buf);
st_size = buf.st_size;
program = do_malloc(buf.st_size);
for ( i = 0LL; i < st_size; i += v6 )
v6 = fread(program, 1uLL, st_size - i, stream);
v11 = ts_parser_parse_string(v14, 0LL, program, (unsigned int)st_size);
if ( v11 )
{
qword_7150 = (__int64)sub_1561();
qword_7158 = sub_3A01();
sub_1329(v11, v7);
exec_instr((__int64)v7, (__int64)v8);
sub_1657(qword_7150);
sub_3A52((_QWORD *)qword_7158);
free(program);
ts_tree_delete(v11);
ts_parser_delete(v14);
return v9;
}
else
{
return 0xFFFFFFFFLL;
}
}
else
{
return 0xFFFFFFFFLL;
}
}
else
{
printf("Usage: %s <program>\n", *a2);
return 0xFFFFFFFFLL;
}
}
Lorsque l’on lance le binaire, celui-ci se lance mais rien ne semble se passer. Je décide donc de lancer un ltrace avec celui-ci afin d’avoir une idée de ce qu’il se passe. Pour ce faire, on modifie l’entrypoint de notre Dockerfile par ["ltrace", "./fcsclang", "program.fcsc"] et on relance notre programme.
La trace d’exécution générée par ltrace est conséquente, on va donc pipe celle-ci vers vscode.
run.sh 2>&1 | code -
Si nous jetons un oeil à la trace d’exécution, nous pouvoir voir l’initialisation du parser
ts_parser_new(3, 0x7ffcd3821168, 0x7ffcd3821188, 0x63b3a1e11db8) = 0x63b3b18622a0
tree_sitter_fcsclang(0x63b3b1862a40, 232, 1, 0) = 0x715c8c6a0d80
ts_parser_set_language(0x63b3b18622a0, 0x715c8c6a0d80, 0x715c8c6a0d80, 0) = 1
fopen("program.fcsc", "r") = 0x63b3b1862ea0
Et surtout nous pouvons voir qu’il prend notre entrée et va effectuer un atoi dessus. Cette fonction permet de convertir une string en entier.
getline("aaaaaaa\n", 120, 0x715c8c3008e0) = 8
atoi(0x63b3b18cf140, 0xa61616161616161, 1, 0xa61616161616161) = 0
En parcourant rapidemment les fonctions, on trouve la fonction que j’ai renommé exec_instr qui semble intéressante. Celle-ci contient un switch-case semblant contenir les différentes instructions de la machine virtuelle. Certaines instructions ont des noms explicites, tandis que d’autres, qui commencent par undocumented_, sont beaucoup moins parlantes.
__int64 __fastcall exec_instr(__int64 a1, __int64 a2)
{
char *s1; // [rsp+18h] [rbp-8h]
if ( (unsigned __int8)sub_1A2C(a1) )
{
fwrite("Syntax error\n", 1uLL, 0xDuLL, stderr);
exit(1);
}
s1 = (char *)get_node_type(a1);
if ( !strcmp(s1, "function_definition") )
return sub_30AF(a1, a2);
if ( !strcmp(s1, "number") )
return sub_1C3A(a1, a2);
if ( !strcmp(s1, "undocumented_732293a7c7094ffd") )
return set_0(a1, a2);
if ( !strcmp(s1, "undocumented_f9bfceb10223dcd6") )
return set_1(a1, a2);
if ( !strcmp(s1, "undocumented_d53cabc7357ff2a5") )
return set_2(a1, a2);
if ( !strcmp(s1, "undocumented_210eb81a94b8b633") )
return set_3(a1, a2);
if ( !strcmp(s1, "undocumented_c589a8f3aaff75f7") )
return set_4(a1, a2);
if ( !strcmp(s1, "undocumented_ac7469dafc6e9c77") )
return set_5(a1, a2);
if ( !strcmp(s1, "undocumented_8212463fe42cc213") )
return set_6(a1, a2);
if ( !strcmp(s1, "undocumented_791df7d09856e81f") )
return set_7(a1, a2);
if ( !strcmp(s1, "undocumented_db9dce746e821769") )
return set_8(a1, a2);
if ( !strcmp(s1, "undocumented_ac3fcec30d0b6a40") )
return set_9(a1, a2);
if ( !strcmp(s1, "str") )
return get_string(a1, a2);
if ( !strcmp(s1, "array") )
return get_array(a1, a2);
if ( !strcmp(s1, "identifier") )
return sub_22FC(a1, a2);
if ( !strcmp(s1, "function_call") )
return function_call(a1, a2);
if ( !strcmp(s1, "scope") )
return sub_306B(a1, a2);
if ( !strcmp(s1, "lvalue") )
return sub_2192(a1, a2);
if ( !strcmp(s1, "assign") )
return assign(a1, a2);
if ( !strcmp(s1, "subscript") )
return subscript(a1, a2);
if ( !strcmp(s1, "binexp") )
return do_operation(a1, a2);
if ( !strcmp(s1, "unexp") )
return do_unexp(a1, a2);
if ( !strcmp(s1, "undocumented_9bfdf82a969d10c2") )
return get_user_input(a1, a2);
if ( !strcmp(s1, "undocumented_af0dbc52101afc49") )
return maybe_a_printf(a1, a2);
if ( !strcmp(s1, "undocumented_0fe135eb8cd073ef") )
return sub_2C3C(a1, a2);
if ( !strcmp(s1, "undocumented_48359b1cc713e5a1") )
return sub_2CCD(a1, a2);
if ( !strcmp(s1, "undocumented_c44ff70e0a035b84") )
return sub_2D91(a1, a2);
return sub_1B7A(a1, a2);
}
On peut par exemple retrouver l’instruction undocumented_9bfdf82a969d10c2 qui fait un getline et un atoi, on peut donc en déduire que c’est cette fonction va lire notre entrée utilisateur.
getline(&lineptr, &n, stdin);
v5 = atoi(lineptr);
Reverse de la VM
A partir de là, ma façon de procéder pour le reverse de VM est de chercher pour des instructions intéressantes et hook celles-ci afin de générer une trace d’exécution et potentiellement comprendre le programme en entrée sans avoir à comprendre le fonctionnement de la machine virtuelle. Je trouve donc la fonction que j’ai renommé do_operation() qui semble particulièrement intéressante.
__int64 __fastcall do_operation(_QWORD *a1, __int64 a2)
{
_BOOL4 v3; // eax
int v4; // [rsp+10h] [rbp-90h] BYREF
__int64 v5; // [rsp+18h] [rbp-88h]
int v6; // [rsp+20h] [rbp-80h] BYREF
__int64 v7; // [rsp+28h] [rbp-78h]
_QWORD v8[4]; // [rsp+30h] [rbp-70h] BYREF
_QWORD v9[4]; // [rsp+50h] [rbp-50h] BYREF
_QWORD v10[5]; // [rsp+70h] [rbp-30h] BYREF
char *s1; // [rsp+98h] [rbp-8h]
search_node_child_by_field_name(a1, "op", v10);
search_node_child_by_field_name(v10, "left", v9);
search_node_child_by_field_name(v10, "right", v8);
exec_instr((__int64)v9, (__int64)&v6);
exec_instr((__int64)v8, (__int64)&v4);
s1 = (char *)get_node_type(v10);
if ( v6 != 1 || v4 != 1 )
{
fwrite("Invalid type\n", 1uLL, 0xDuLL, stderr);
exit(1);
}
if ( !strcmp(s1, "undocumented_46eb8e8b7b15c3d5") )
return sub_3BF0((int)v5 + (int)v7, a2);
if ( !strcmp(s1, "undocumented_cfd09200be51d38f") )
return sub_3BF0((int)v7 - (int)v5, a2);
if ( !strcmp(s1, "undocumented_b341f271c655aaee") )
return sub_3BF0((int)v7 * (int)v5, a2);
if ( !strcmp(s1, "undocumented_956dd300d7424ff3") )
return sub_3BF0(v7 == v5, a2);
if ( !strcmp(s1, "undocumented_0162f13a50afff09") )
return sub_3BF0(v7 != v5, a2);
if ( !strcmp(s1, "undocumented_a91bdbbce9e82238") )
return sub_3BF0((unsigned int)v7 < (unsigned int)v5, a2);
if ( !strcmp(s1, "undocumented_589a700aed48e3a4") )
return sub_3BF0((unsigned int)v5 < (unsigned int)v7, a2);
if ( !strcmp(s1, "undocumented_2d5b46a88151170b") )
return sub_3BF0((unsigned int)v5 >= (unsigned int)v7, a2);
if ( !strcmp(s1, "undocumented_4c3cc3b8907e3db5") )
return sub_3BF0((unsigned int)v7 >= (unsigned int)v5, a2);
if ( !strcmp(s1, "undocumented_aa1bd5b44f53714d") )
{
v3 = v7 && v5;
return sub_3BF0(v3, a2);
}
if ( !strcmp(s1, "undocumented_0e772940f0fd3008") )
{
v3 = v7 || v5;
return sub_3BF0(v3, a2);
}
if ( !strcmp(s1, "undocumented_13932b8a4b1bd439") )
return sub_3BF0((_DWORD)v7 << v5, a2);
if ( !strcmp(s1, "undocumented_0cd2df8843187030") )
return sub_3BF0((unsigned int)v7 >> v5, a2);
if ( !strcmp(s1, "undocumented_b858202486aecd0f") )
return sub_3BF0((unsigned int)v5 | (unsigned int)v7, a2);
if ( strcmp(s1, "undocumented_24e094c9759dc06c") )
{
fwrite("Not implemented\n", 1uLL, 0x10uLL, stderr);
exit(1);
}
return sub_3BF0((unsigned int)v5 & (unsigned int)v7, a2);
}
En effet, dans cette fonction se trouve un switch case pour différentes opérations mathématiques et binaire. Ce sera donc notre premier hook.
J’ai pour cela simplement utilisé un script gdb avec python. J’ai également exporté les symboles depuis IDA à l’aide de l’extension syms2elf.
import gdb
class BreakDoOperation(gdb.Breakpoint):
def __init__(self):
super().__init__('*do_operation + 244', internal=False)
def stop(self):
try:
rdi = gdb.parse_and_eval("$rdi")
char_ptr = rdi.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
v5 = gdb.parse_and_eval("*(int*)($rbp - 0x88)")
v7 = gdb.parse_and_eval("*(int*)($rbp - 0x78)")
if string == "undocumented_46eb8e8b7b15c3d5":
print(f"{v5} + {v7}")
elif string == "undocumented_cfd09200be51d38f":
print(f"{v7} - {v5}")
elif string == "undocumented_b341f271c655aaee":
print(f"{v7} * {v5}")
elif string == "undocumented_956dd300d7424ff3":
print(f"{v7} == {v5}")
elif string == "undocumented_0162f13a50afff09":
print(f"{v7} != {v5}")
elif string == "undocumented_a91bdbbce9e82238":
print(f"{v7} < {v5}")
elif string == "undocumented_589a700aed48e3a4":
print(f"{v5} < {v7}")
elif string == "undocumented_2d5b46a88151170b":
print(f"{v5} >= {v7}")
elif string == "undocumented_4c3cc3b8907e3db5":
print(f"{v7} >= {v5}")
elif string == "undocumented_aa1bd5b44f53714d":
print(f"{v7} && {v5}")
elif string == "undocumented_0e772940f0fd3008":
print(f"{v7} || {v5}")
elif string == "undocumented_13932b8a4b1bd439":
print(f"{v7} << {v5}")
elif string == "undocumented_0cd2df8843187030":
print(f"{v7} >> {v5}")
elif string == "undocumented_b858202486aecd0f":
print(f"{v5} | {v7}")
elif string == "undocumented_24e094c9759dc06c":
print(f"{v5} & {v7}")
else:
print("not implemented !!!!")
return False
De plus, j’ai hooké les fonctions qui étaient “guessable” à partir de leur noms ou en survolant rapidemment leur code.
function_names = [
"do_unexp",
"maybe_a_printf",
"get_user_input",
"function_call",
"get_array",
"get_string",
# j'ai renommé ces fonctions ainsi car elles semblaient mettre des valeurs de 0 à 9, peut être un push sur une stack ou un registre, je n'ai pas creusé mais ça nous permet d'avoir une idée dans notre trace.
"set_0",
"set_1",
"set_2",
"set_3",
"set_4",
"set_5",
"set_6",
"set_7",
"set_8",
"set_9"
]
class FunctionBreakpoint(gdb.Breakpoint):
def __init__(self, func_name):
super().__init__(func_name, internal=False)
self.func_name = func_name
def stop(self):
print(f"executing {self.func_name}")
return False
Maintenant si on relance le binaire avec le Dockerfile suivant :
FROM debian:sid
RUN apt update && apt install -y libtree-sitter-dev=0.22.6-6 ltrace gdb python3
COPY . /fcsclang
WORKDIR /fcsclang
ENV LD_LIBRARY_PATH .
ENTRYPOINT ["gdb", "-q", "-ex", "source gdb_do_operation_hook.py", "-ex", "run program.fcsc", "-ex", "quit", "fcsclang_symbols"]
On obtient en sortie une trace d’exécution gigantesque.
On peut tout de même voir que dans les premières instructions le programme semble stocker l’entrée utilisateur dans un tableau 9x9.
0 < 9
executing set_0
executing set_9
0 < 9
executing get_user_input
executing set_1
1 + 0
executing set_9
1 < 9
executing get_user_input
executing set_1
1 + 1
executing set_9
2 < 9
executing get_user_input
executing set_1
1 + 2
executing set_9
3 < 9
executing get_user_input
executing set_1
[...]
Malheureusement, la trace d’exécution étant beaucoup trop grande, il est très compliqué de comprendre son fonctionnement. Heureusement, le programme semble utiliser des fonctions ! Dans le switch case permettant de gérer les instructions de la machine virtuelle on retrouve un appel très intéressant : function_call
On va donc créer 2 hook, un function_call et un function_end, ainsi il sera possible de séparer les traces d’executions par fonction et de grandement simplifier le processus de reverse.
class BreakFunctionCall(gdb.Breakpoint):
def __init__(self):
super().__init__('*function_call + 66', internal=False)
def stop(self):
try:
rax = gdb.parse_and_eval("$rax")
char_ptr = rax.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
print(f"calling function {string}")
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
class ExitingFunctionCall(gdb.Breakpoint):
def __init__(self):
super().__init__('*function_call + 308', internal=False)
def stop(self):
try:
rax = gdb.parse_and_eval("$rax")
char_ptr = rax.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
print(f"end of function {string}")
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
Un dernier hook qui me semble important est le hook de subscript, celui-ci va nous permettre de voir quel element d’une array est lu.
class BreakSubscript(gdb.Breakpoint):
def __init__(self):
super().__init__("*subscript + 221", internal=False)
def stop(self):
rdx = gdb.parse_and_eval("$rdx")
print(f"get array[{rdx}]")
return False
Voici le script complet permettant de générer notre trace d’exécution :
import gdb
class BreakFunctionCall(gdb.Breakpoint):
def __init__(self):
super().__init__('*function_call + 66', internal=False)
def stop(self):
try:
rax = gdb.parse_and_eval("$rax")
char_ptr = rax.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
print(f"calling function {string}")
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
class ExitingFunctionCall(gdb.Breakpoint):
def __init__(self):
super().__init__('*function_call + 308', internal=False)
def stop(self):
try:
rax = gdb.parse_and_eval("$rax")
char_ptr = rax.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
print(f"end of function {string}")
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
class FunctionBreakpoint(gdb.Breakpoint):
def __init__(self, func_name):
super().__init__(func_name, internal=False)
self.func_name = func_name
def stop(self):
print(f"executing {self.func_name}")
return False
class BreakDoOperation(gdb.Breakpoint):
def __init__(self):
super().__init__('*do_operation + 244', internal=False)
def stop(self):
print("\nBreakpoint at do_operation+244")
try:
rdi = gdb.parse_and_eval("$rdi")
char_ptr = rdi.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
v5 = gdb.parse_and_eval("*(int*)($rbp - 0x88)")
v7 = gdb.parse_and_eval("*(int*)($rbp - 0x78)")
if string == "undocumented_46eb8e8b7b15c3d5":
print(f"{v5} + {v7}")
elif string == "undocumented_cfd09200be51d38f":
print(f"{v7} - {v5}")
elif string == "undocumented_b341f271c655aaee":
print(f"{v7} * {v5}")
elif string == "undocumented_956dd300d7424ff3":
print(f"{v7} == {v5}")
elif string == "undocumented_0162f13a50afff09":
print(f"{v7} != {v5}")
elif string == "undocumented_a91bdbbce9e82238":
print(f"{v7} < {v5}")
elif string == "undocumented_589a700aed48e3a4":
print(f"{v5} < {v7}")
elif string == "undocumented_2d5b46a88151170b":
print(f"{v5} >= {v7}")
elif string == "undocumented_4c3cc3b8907e3db5":
print(f"{v7} >= {v5}")
elif string == "undocumented_aa1bd5b44f53714d":
print(f"{v7} && {v5}")
elif string == "undocumented_0e772940f0fd3008":
print(f"{v7} || {v5}")
elif string == "undocumented_13932b8a4b1bd439":
print(f"{v7} << {v5}")
elif string == "undocumented_0cd2df8843187030":
print(f"{v7} >> {v5}")
elif string == "undocumented_b858202486aecd0f":
print(f"{v5} | {v7}")
elif string == "undocumented_24e094c9759dc06c":
print(f"{v5} & {v7}")
else:
print("not implemented !!!!")
return False
class BreakGetString(gdb.Breakpoint):
def __init__(self):
super().__init__('*get_string + 97', internal=False)
def stop(self):
try:
rdi = gdb.parse_and_eval("$rdi")
char_ptr = rdi.cast(gdb.lookup_type("char").pointer())
string = char_ptr.string()
print(f"getting string {string}")
except Exception as e:
print(f"Unable to read string at $rdi: {e}")
class BreakSubscript(gdb.Breakpoint):
def __init__(self):
super().__init__("*subscript + 221", internal=False)
def stop(self):
rdx = gdb.parse_and_eval("$rdx")
print(f"get array[{rdx}]")
return False
BreakDoOperation()
BreakFunctionCall()
ExitingFunctionCall()
BreakGetString()
BreakSubscript()
function_names = [
"do_unexp",
"assign",
"maybe_a_printf",
"get_user_input",
"function_call",
"get_array",
"set_0",
"set_1",
"set_2",
"set_3",
"set_4",
"set_5",
"set_6",
"set_7",
"set_8",
"set_9"
]
for name in function_names:
FunctionBreakpoint(name)
Etude du programme
Il est maintenant temps de commencer à étudier le programme.
Pour ça j’ai utilisé le script suivant :
from pwn import *
p = process("./run.sh")
for i in range(9*9):
p.sendline(f"1337{i:02}")
p.interactive()
Celui-ci envoie des valeurs commençant par 1337, ainsi il est facilement possible de les retrouver dans notre trace d’exécution. De plus la valeur i nous permet de connaitre l’index dans notre tableau, si l’opération est effectuée sur 133714 on pourra en déduire qu’il a effectué l’opération sur user_input[14 // 9][14 % 9] -> user_input[1][5].
Durant le reverse, j’ai également utilisé d’autres valeurs que 1337XX afin d’étudier les différents comportements et ne rien louper.
Je vais ici détailler seulement une ou deux fonctions de la trace d’exécution afin de ne pas rendre l’article trop assommant car le processus ensuite est très répétitif.
Je vous ai néanmoins mis une trace d’exécution d’exemple ici si vous souhaitez voir à quoi cela ressemble.
Afin d’avoir une vision plus clair de l’execution des fonctions, on peut faire un grep de calling|end of sur notre trace d’exécution, ainsi après avoir indenté tout ça on se retrouve avec quelque chose de plus clair. On distingue par exemple des appels répétitifs, on peut deviner que ce sont probablement des boucles, etc.
calling function pipe
end of function pipe
calling function lancinante
calling function bidonner
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
calling function inattendu
end of function inattendu
end of function bidonner
calling function symboles
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
calling function mendiant
end of function mendiant
end of function symboles
calling function discutable
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
calling function aux
calling function copie
end of function copie
end of function aux
end of function discutable
calling function ferrailleur
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
calling function gerber
calling function central
end of function central
end of function gerber
end of function ferrailleur
end of function lancinante
La première fonction pipe va lire l’entrée utilisateur.
Nous allons en premier nous intéresser à la fonction innatendue.
En analysant cette fonction, on retrouve 9 fois le même pattern, on peut donc en déduire que c’est une boucle. On retrouve également la condition suivante à chaque itération du pattern : 0 < 9.
Je vous ai mis ici 2 itérations de cette boucle :
get array[0]
Breakpoint at do_operation+244
1 << 133700
Breakpoint at do_operation+244
16 & 0
Breakpoint at do_operation+244
1 && 1
Breakpoint at do_operation+244
9 >= 133700
Breakpoint at do_operation+244
0 < 133700
Breakpoint at do_operation+244
0 && 1
Breakpoint at do_operation+244
0 && 1
Breakpoint at do_operation+244
16 | 0
Breakpoint at do_operation+244
1 + 0
Breakpoint at do_operation+244
1 < 9
get array[1]
Breakpoint at do_operation+244
1 << 133701
Breakpoint at do_operation+244
32 & 16
Breakpoint at do_operation+244
1 && 0
Breakpoint at do_operation+244
9 >= 133701
Breakpoint at do_operation+244
0 < 133701
Breakpoint at do_operation+244
0 && 1
Breakpoint at do_operation+244
0 && 0
Breakpoint at do_operation+244
32 | 16
Breakpoint at do_operation+244
1 + 1
Le code semble itérer sur la première ligne de notre entrée utilsateur, il va prendre le premier élément en user_input[0][0] et vérifier que celui-ci se trouve entre 1 et 9 et que la valeur n’apparaît pas deux fois sur la ligne.
Voici un pseudo code de ce que fais cette fonction :
function inattendu(line) {
val = 0
is_ok = true
for (i in range 9) {
x = user_input[line][i]
if (x < 1 or x > 9) {
is_ok = false
}
shifted = 1 << x
if (shifted & val) {
is_ok = false
}
val = val | shifted
}
return is_ok
}
Cette fonction est appelé 9 fois donc très probablement pour chaque ligne de notre input.
Ensuite une autre fonction très similaire est appelée 9 fois, celle-ci effectue les mêmes opérations mais cette fois sur chaque colonne.
A partir de là, on peut se douter que le programme implémenté est un sudoku. Je n’ai pas reverse la fonction discutable mais celle-ci effectuant des multiplications par 3 et étant donné le contexte du challenge on peut très facilement deviner qu’elle va vérifier que chaque région du sudoku est valide.
À la suite de cela, le programme va itérer sur un tableau 9x9 qu’il possède en mémoire.
on le comprend grâce aux extraits suivants de notre trace d’exécution :
get array[0]
get array[0]
0 != 0
[...]
get array[0]
get array[1]
0 != 0
[...]
get array[0]
get array[2]
0 != 0
[...]
get array[0]
get array[7]
1 != 0
[...]
get array[0]
get array[8]
8 != 0
[...]
Lorsque la valeur extraite de ce tableau est différente de 0, le programme appelle la fonction gerber.
On peut ainsi reconstruire le contenu du tableau, qui ressemble à ceci :
0 0 0 0 0 0 0 1 8
0 0 5 6 1 0 0 2 0
3 0 0 0 0 0 5 1 0
0 0 0 0 0 0 0 0 2
1 0 0 0 3 0 0 4 4
0 0 0 0 2 1 0 0 5
0 0 0 0 4 3 0 6 1
3 1 0 1 0 6 0 0 0
0 0 4 7 0 0 0 6 7
La fonction gerber, à partir de la position et de la valeur non nulle, appelle ensuite la fonction central. Celle-ci génère quatre nouvelles positions autour de la position d’origine, dans un rayon (horizontal et vertical, pas en diagonale) de N cases, où N correspond à la valeur lue dans notre grille à la position de départ.
Le programme va ensuite vérifier si au moins une de ces 4 nouvelles positions contient la valeur N.
Voici un exemple avec les valeurs 3 et 1 afin que ce soit plus parlant.
Résolution
Nous avons donc maintenant toutes les conditions en mains pour pouvoir écrire notre script de solve.
Pour cela, j’ai utilisé un script z3 permettant de résoudre un sudoku auquel j’ai ajouté nos conditions.
from z3 import *
grid = [[Int(f"cell_{i}_{j}") for j in range(9)] for i in range(9)]
s = Solver()
for i in range(9):
for j in range(9):
s.add(And(grid[i][j] >= 1, grid[i][j] <= 9))
for i in range(9):
s.add(Distinct(*grid[i]))
for j in range(9):
col = [grid[i][j] for i in range(9)]
s.add(Distinct(*col))
for bi in range(3):
for bj in range(3):
block = [grid[3*bi + di][3*bj + dj] for di in range(3) for dj in range(3)]
s.add(Distinct(*block))
condition_grid = [
[0, 0, 0, 0, 0, 0, 0, 1, 8],
[0, 0, 5, 6, 1, 0, 0, 2, 0],
[3, 0, 0, 0, 0, 0, 5, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 2],
[1, 0, 0, 0, 3, 0, 0, 4, 4],
[0, 0, 0, 0, 2, 1, 0, 0, 5],
[0, 0, 0, 0, 4, 3, 0, 6, 1],
[3, 1, 0, 1, 0, 6, 0, 0, 0],
[0, 0, 4, 7, 0, 0, 0, 6, 7],
]
def get_positions(i,j,k):
return [(a, b) for a,b in [
(i + k, j),
(i, j + k),
(i, j - k),
(i - k, j),
] if a < 9 and b < 9 and a >= 0 and b >= 0]
# on ajoute nos conditions spécifiques à partir de notre grille de condition
for i in range(9):
for j in range(9):
k = condition_grid[i][j]
if k:
pos = get_positions(i,j, k)
s.add(Or(*[ grid[x][y] == k for x,y in pos ]))
if s.check() == sat:
m = s.model()
solution = [[m.evaluate(grid[i][j]).as_long() for j in range(9)] for i in range(9)]
for ligne in solution:
print(ligne)
else:
print("Pas de solution trouvée.")
On lance notre script z3 et on obtiens notre grille de solution.
8 3 6 2 1 9 7 5 4
5 4 9 7 8 6 3 1 2
1 2 7 3 4 5 9 6 8
6 5 8 1 9 3 4 2 7
3 1 4 8 2 7 6 9 5
7 9 2 5 6 4 8 3 1
9 6 5 4 7 1 2 8 3
4 8 1 6 3 2 5 7 9
2 7 3 9 5 8 1 4 6
On peut maintenant l’envoyer à notre programme et celui-ci nous renvoie le flag !
FCSC{836219754549786312127345968658193427314827695792564831965471283481632579273958146}