Mazeware
Category: rev
Points: 1000
Solves: 2
Description:
finally… looks like a normal reversing challenge written in C… (or isit?)
( ͡° ͜ʖ ͡°)
Author: Elma
Note: This is a pretty comprehensive writeup detailing almost all the steps I took to reach the flag. If some of the parts bore you feel free to skip around.
This writeup is also broken up into 4 parts for ease of navigation:
Thank you Elma for blessing us with this challenge!
Part I: Playing the Game
We are given a binary to explore. Scrolling through the decompilation nothing immediately jumps out. In fact it is simple enough for me to describe each function here:
__int64 __fastcall main(int a1, char **a2, char **a3)
{
printf("%s", byte_4041C0);
getchar();
sub_4019E1();
return 0LL;
}The welcome screen. byte_4041C0 points to the welcome banner:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⣘⣩⣅⣤⣤⣄⣠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠄⢈⣻⣿⣿⢷⣾⣭⣯⣯⡳⣤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣧⠻⠿⡻⢿⠿⡾⣽⣿⣳⣧⡷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢰⡶⢈⠐⡀⠀⠀⠁⠀⠀⠀⠈⢿⡽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢫⢅⢠⣥⣐⡀⠀⠀⠀⠀⠀⠀⢸⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠆⠡⠱⠒⠖⣙⠂⠈⠵⣖⡂⠄⢸⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⠆⠀⠰⡈⢆⣑⠂⠀⠀⠀⠀⠀⠏⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢗⠀⠱⡈⢆⠙⠉⠃⠀⠀⠀⠀⠃⠁⠀⠀⠀COOK TOO MUCH⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠦⡡⢘⠩⠯⠒⠀⠀⠀⢀⠐⠀⠀⠀⠀⠀AND YOU WILL⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⢔⡢⢡⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀GET RICKED!!⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⢆⠸⡁⠋⠃⠁⠀⢀⢠⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡰⠌⣒⠡⠄⠀⢀⠔⠁⣸⣿⣷⣤⣀⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣐⣤⡄⠀⠀⠘⢚⣒⢂⠇⣜⠒⠉⠀⢀⣿⣿⣿⣿⣿⣿⣿⣷⣶⣶⣦⣔⣀⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⡀⢀⢠⣤⣶⣿⣿⣿⡆⠀⠀⠐⡂⠌⠐⠝⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢨⣶⣿⣿⣿⣿⣿⣿⣿⣿⣤⡶⢐⡑⣊⠀⡴⢤⣀⣀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠷⡈⠀⠶⢶⣰⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣉⠑⠚⣙⡒⠒⠲⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀
⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠶⠀⠀⠤⣬⣍⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀
⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣛⣙⠀⢠⠲⠖⠶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣭⣰⢘⣙⣛⣲⣿⣿⣿⣿⡿⡻⠿⠿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀
⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠶⢾⡠⢤⣭⣽⣿⣿⣿⣿⡟⣱⠦⠄⠤⠐⡄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡀⠀
⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡛⣻⡕⠶⠶⣿⣿⣿⣿⣿⣿⣗⣎⠒⣀⠃⡐⢀⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀
⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣭⣹⣏⣛⣛⣿⣿⣿⣿⣿⣿⣿⣞⣍⣉⢉⠰⠀⠠⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠅
⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠶⢼⡧⢤⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣣⣡⣛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣅
⡿⣷⣽⡿⠛⠋⠉⣉⡐⠶⣾⣾⣟⣻⡕⠶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣹⣫⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠗
⢸⣿⣟⣥⡶⢘⡻⢶⡹⣛⣼⣿⣯⣽⢯⣙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⡿⠿⠟⠁⠀
⠘⢟⣾⣿⣿⣚⠷⣳⢳⣫⣽⣿⣛⣾⡷⢾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠁⠀⠈⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠙⢋⣿⣿⣯⣙⣯⣵⣿⣿⣯⣽⣟⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠉⠛⢻⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣟⡟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣡⣿⣿⣿⣿⡗⣮⢻⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
PRESS ENTER TO BEGIN YOUR ADVENTURE!And sub_4019E1 is of course our game loop. Below is how the game looks like, after pressing enter:
W A S D to navigate
###########
#^# #
# ### # ###
# # # #
# ### ### #
# #F #
###########void sub_4019E1()
{
unsigned __int8 v0; // [rsp+5h] [rbp-Bh]
unsigned __int8 v1; // [rsp+6h] [rbp-Ah]
unsigned __int8 v2; // [rsp+7h] [rbp-9h]
unsigned __int8 v3; // [rsp+7h] [rbp-9h]
char v4; // [rsp+7h] [rbp-9h]
int i; // [rsp+8h] [rbp-8h]
for ( i = 0; i <= 2; i = 4 )
{
do
{
v0 = (unsigned __int16)sub_401704((__int64)*(&off_4058B0 + i)) >> 8;
v1 = sub_401704((__int64)*(&off_4058B0 + i)) & 0xF;
sub_4017CD((char *)*(&off_4058B0 + i), v0, v1);
do
{
v2 = getchar();
if ( v2 > 0x60u )
v2 -= 32;
if ( v2 > 0x40u )
{
v3 = v2 - 65;
if ( v3 )
{
if ( v3 / 3u - v3 % 3u == 1 )
{
if ( sub_40173D((__int64)*(&off_4058B0 + i), v0 + 1, v1) )
++v0;
}
else
{
v4 = v3 - 18;
if ( v4 )
{
if ( v4 == 4 && sub_40173D((__int64)*(&off_4058B0 + i), v0, v1 - 1) )
--v1;
}
else if ( sub_40173D((__int64)*(&off_4058B0 + i), v0, v1 + 1) )
{
++v1;
}
}
}
else if ( sub_40173D((__int64)*(&off_4058B0 + i), v0 - 1, v1) )
{
--v0;
}
}
}
while ( !(unsigned int)sub_4017CD((char *)*(&off_4058B0 + i), v0, v1) );
printf("\n\tNext level? Enter to continue...");
getchar();
getchar();
++i;
}
while ( i != 3 );
sub_40147C();
}
}The outermost for loop
for ( i = 0; i <= 2; i = 4 )seems completely unnecessary as it is implied the block only gets accessed exactly once. But other than that the control flow is pretty intuitive, especially with the contextual clue from the string in the printf that the outer do-while loop makes up the 3 levels of the maze while the inner do-while loop prints the maze level until the win condition for the level is reached.
The v2 and v3 if branches should also be pretty obvious to anyone who has done 2D terminal game reversing, with
if ( v2 > 0x60u )
v2 -= 32;
if ( v2 > 0x40u )signalling the program does not distinguish upper and lower case input, as well as 4 separate calls to the same function with only slightly differing arguments
sub_40173D((__int64)*(&off_4058B0 + i), v0 + 1, v1)
sub_40173D((__int64)*(&off_4058B0 + i), v0, v1 - 1)
sub_40173D((__int64)*(&off_4058B0 + i), v0, v1 + 1)
sub_40173D((__int64)*(&off_4058B0 + i), v0 - 1, v1)instantly jumping out that v0 and v1 should represent the x and y coordinates. By extension off_4058B0 shall be the level data, and in the context of
if ( sub_40173D((__int64)*(&off_4058B0 + i), v0 + 1, v1) )
++v0;it is sufficiently clear (without even analysing the function itself) that sub_40173D checks for valid move (since it is a maze game). Matching the varied calls to the corresponding input tells us that v0 is x and v1 is y.
Note that each of the interpretations can be independently verified by cracking the functions open and scrutinising what they do, but for the sake of this writeup it shall be omitted.
But just as an example, sub_4017CD, which controls the inner do-while loop, looks like this:
__int64 __fastcall sub_4017CD(char *a1, int a2, int a3)
{
int v5; // [rsp+4h] [rbp-3Ch]
int v6; // [rsp+14h] [rbp-2Ch]
int i; // [rsp+18h] [rbp-28h]
int v8; // [rsp+1Ch] [rbp-24h]
unsigned int v9; // [rsp+20h] [rbp-20h]
int j; // [rsp+24h] [rbp-1Ch]
int v11; // [rsp+30h] [rbp-10h]
int v12; // [rsp+38h] [rbp-8h]
v5 = a2;
puts("\x1B[H\x1B[2J\n\n");
puts("\tW A S D to navigate");
if ( a2 == -1 && a3 == -1 )
{
a3 = a1[1];
v5 = a1[3];
}
v11 = a1[4];
v6 = 0;
for ( i = 0; i < v11; ++i )
v6 += a1[5];
v12 = v11 * *a1 + a1[2];
v8 = 0;
v9 = 0;
putchar(9); // \t, or left padding
for ( j = 0; j < v6; ++j )
{
if ( v8 == v11 * a3 + v5 )
{
if ( v8 == v12 )
v9 = 1;
putchar(94); // ^ i.e. player
}
else if ( v8 == v12 )
{
putchar(70); // F i.e. flag
}
else if ( (((int)(unsigned __int8)a1[v8 / 8 + 6] >> (7 - v8 % 8)) & 1) != 0 )
{
putchar(35); // # i.e. wall
}
else
{
putchar(32); // ' ' i.e. space
}
if ( !(++v8 % v11) )
printf("\n\t"); // newline + left padding
}
return v9;
}Matching up the characters that are displayed by putchar we see that it pretty much matches what we would expect to see just by playing the game, so we can know that it does what we expect it to do and confirms our previous educated guesses. (Right…?)
Another thing is that a relevant result is also actually returned in the function:
v9 = 0;
// ...
if ( v8 == v12 )
v9 = 1;
// ...
return v9;This means that the function returns true if the player has the same coordinates as the flag, i.e. we have cleared the level.
Finally, it is pretty obvious at this point that sub_40147C outside the two do-while loops of the game function will lead us to victory. But before that, based on how simple this game seems to be, how about we just… play the game properly?
W A S D to navigate
###########
# # #
# ### # ###
# # # #
# ### ### #
# #^ #
###########
Next level? Enter to continue.. W A S D to navigate
#########################################
# ^# # # # # # #
# ####### # ### ##### # # # # # ### ### #
# # # # # # # # # # # # #
# # ### # # ### ##### ### ####### # #####
# # # # # # # # # # # #
# # # # ### ### # ### ### # ########### #
# # # # # # # # # # #
##### ####### # ### ### ### ##### # # # #
# # # # # # # # # #
# ####### # ##### ######### # # # ### ###
# # # # # # # # # # #F#
# ### ####### ##### ### # # ####### # # #
# # # # # # # # # # # # #
# # # ### ### ### # # ### ### # ### ### #
# # # # # # # # # # # # #
# ### ### ##### # ### # # ##### ### ### #
# # # # # # # # # #
# # # ### # ### # # ### ### ### ### ### #
# # # # # # # #
#########################################Okay…
W A S D to navigate
#################
# ^ #
# #
# #
# #######
# # #
# # F #
# # #
#################Never mind then.
But wait! We are professional hackers :)
gdb mazeware
...
gef➤ rWe play the game normally until the last level, where we break out and set a breakpoint to the call to the draw-and-check-win function (which is the inner do-while loop condition):
W A S D to navigate
#################
# ^ #
# #
# #
# #######
# # #
# # F #
# # #
#################
^C
Program received signal SIGINT, Interrupt.
...
gef➤ b *0x401bf6
gef➤ c
a●→ 0x401bf6 call 0x4017cd
...
gef➤ niHere the function will of course return 0x0 as we have not reached the flag yet, but we pretend it did:
$rax : 0x0
...
gef➤ set $rax=0x1
gef➤ c
Continuing.
Next level? Enter to continue...
https://www.youtube.com/watch?v=dQw4w9WgXcQI guess we got to the end…? (By the way if you somehow don’t recognise the link feel free to click here)
Note that this method is sometimes risky as the win function may only return the desired result if legitimate steps are taken to get there (anti-cheat essentially, for instance the x and y values must be correct etc.). But long story short this was not the case for this challenge, you can crack the win function open if you want.
Part II: More Than Meets the Eye
Part IIA: Just Beneath Plainsight
Actually never mind, I’ll just do it for you:
int sub_40147C()
{
char *s; // [rsp+8h] [rbp-8h]
s = (char *)malloc(0x2CuLL);
sub_4013F5(byte_405340, &unk_4040C0, s);
return puts(s);
}__int64 __fastcall sub_4013F5(__int64 a1, __int64 a2, __int64 a3)
{
char v5[264]; // [rsp+20h] [rbp-110h] BYREF
unsigned __int64 v6; // [rsp+128h] [rbp-8h]
v6 = __readfsqword(0x28u);
sub_40122E(a1, v5);
sub_4012FB(v5, a2, a3);
return 0LL;
}__int64 __fastcall sub_40122E(const char *a1, __int64 a2)
{
unsigned int v3; // [rsp+10h] [rbp-10h]
int i; // [rsp+14h] [rbp-Ch]
int j; // [rsp+18h] [rbp-8h]
int v6; // [rsp+1Ch] [rbp-4h]
v6 = strlen(a1);
LOBYTE(v3) = 0;
for ( i = 0; i <= 255; ++i )
*(_BYTE *)(i + a2) = i;
for ( j = 0; j <= 255; ++j )
{
v3 = (unsigned __int8)(*(_BYTE *)(j + a2) + v3 + a1[j % v6]);
sub_4011F6(j + a2, a2 + v3);
}
return 0LL;
}
__int64 __fastcall sub_4012FB(__int64 a1, const char *a2, __int64 a3)
{
unsigned int v5; // [rsp+24h] [rbp-1Ch]
unsigned int v6; // [rsp+28h] [rbp-18h]
size_t v7; // [rsp+30h] [rbp-10h]
size_t v8; // [rsp+38h] [rbp-8h]
LOBYTE(v5) = 0;
LOBYTE(v6) = 0;
v7 = 0LL;
v8 = strlen(a2);
while ( v7 < v8 )
{
v5 = (unsigned __int8)(v5 + 1);
v6 = (unsigned __int8)(*(_BYTE *)(v5 + a1) + v6);
sub_4011F6((char *)(v5 + a1), (char *)(a1 + v6));
*(_BYTE *)(a3 + v7) = *(_BYTE *)((unsigned __int8)(*(_BYTE *)(v5 + a1) + *(_BYTE *)(v6 + a1)) + a1) ^ a2[v7];
++v7;
}
return 0LL;
}
/*
* simple byte swap function, will not elaborate further
*/
char *__fastcall sub_4011F6(char *a1, char *a2)
{
char *result; // rax
char v3; // [rsp+1Ch] [rbp-4h]
v3 = *a1;
*a1 = *a2;
result = a2;
*a2 = v3;
return result;
}In case you are unaware, this is apparently the RC4 algorithm. (I should probably get this algorithm into my pattern recognition database, it has popped up enough times already HAHA)
Either way, whatever it is, we know that the function applies some algorithm on two strings in the binary and outputs the result (the rickroll URL above). Rev chal spidey-senses are now tingling telling us that the strings must be tampered somewhere along the way in order to switch to outputting the flag at the end, and this is especially likely given that they are both stored in .data.
The first thing to do is hence to check out their cross-references.
.data:00000000004040C0 unk_4040C0 db 8Bh ; DATA XREF: sub_40147C+21↑oOkay, looks all good.
.data:0000000000405340 ; _BYTE byte_405340[64]
.data:0000000000405340 byte_405340 db 44h, 55h, 62h, 1Dh, 5Dh, 46h, 0F9h, 2Ch, 32h, 5Eh, 62h
.data:0000000000405340 ; DATA XREF: sub_40147C+2B↑o
.data:0000000000405340 ; sub_4014C5+AE↑oOoh, something’s up, isn’t it? Unknown function at 0x4014c5?
.text:00000000004014C5 ; void sub_4014C5()
.text:00000000004014C5 sub_4014C5 proc near ; DATA XREF: sub_4014C5+156↓o
.text:00000000004014C5 ; .data:00000000004058D8↓oPerhaps we just keep backtracking until we reach somewhere familiar.
.data:00000000004058D0 off_4058D0 dq offset loc_4016FE ; DATA XREF: sub_4017CD+204↑o
.data:00000000004058D8 dq offset sub_4014C5.text:00000000004019C5 loc_4019C5: ; CODE XREF: sub_4017CD+126↑j
.text:00000000004019C5 mov eax, [rbp+var_1C]
.text:00000000004019C8 cmp eax, [rbp+var_2C]
.text:00000000004019CB jl loc_4018F8
.text:00000000004019D1 mov rsp, offset off_4058D0
.text:00000000004019D8 mov eax, [rbp+var_20]
.text:00000000004019DB retn
.text:00000000004019DB sub_4017CD endp
.text:00000000004019DB
.text:00000000004019DC ; ---------------------------------------------------------------------------
.text:00000000004019DC mov eax, [rbp-20h]
.text:00000000004019DF leave
.text:00000000004019E0 retn
.text:00000000004019E0 ; } // starts at 4017CDHere we are! If you forgot, sub_4017CD is the draw-and-check-win function.
We see that a retn has been secretly sneaked in at 4019DB, which perhaps IDA somehow didn’t quite recognise?
Either way, this basically means that at the end of the draw-and-check-win function (which is actually first called before the first iteration of the inner do-while loop), the program jumps to a secret shadow function that tampers with our stored string.
Why do I call it a shadow function? Well, it’s because I first analysed this on Ghidra (IDK why but IDA Free decompilation didn’t want to work at first), and all Ghidra rev players would probably understand the ecstacy upon seeing the purple decompilation background:
Part IIB: Caught in the Act
Realistically, this process of reaching our shadow function can easily been disrupted at multiple stages. For example our function could have referenced the string indirectly. Or perhaps the true win function could have had nothing to do with the fake win function at all. It would have made the discovery process much more difficult.
But ultimately, like a forensic scene, there are multiple clues we could perhaps piece together to reach our final conclusion. The above XREF is just one of them.
For example, where we broke out of the game while trying to hack it, if we just ran a simple vmmap:
gef➤ vmmap
[ Legend: Code | Heap | Stack ]
Start End Offset Perm Path
0x000000003ff000 0x00000000400000 0x00000000000000 rw- [REDACTED]/mazeware
0x00000000400000 0x00000000401000 0x00000000001000 r-- [REDACTED]/mazeware
0x00000000401000 0x00000000402000 0x00000000002000 r-x [REDACTED]/mazeware
0x00000000402000 0x00000000403000 0x00000000003000 r-- [REDACTED]/mazeware
0x00000000403000 0x00000000404000 0x00000000003000 r-- [REDACTED]/mazeware
0x00000000404000 0x00000000406000 0x00000000004000 rw- [REDACTED]/mazeware
0x00000000406000 0x00000000427000 0x00000000000000 rw- [heap]
0x007ffff7d8f000 0x007ffff7d92000 0x00000000000000 rw-
0x007ffff7d92000 0x007ffff7dba000 0x00000000000000 r-- [REDACTED]/lib/libc.so.6
0x007ffff7dba000 0x007ffff7f4e000 0x00000000028000 r-x [REDACTED]/lib/libc.so.6
0x007ffff7f4e000 0x007ffff7f4f000 0x000000001bc000 r-x [REDACTED]/lib/libc.so.6
0x007ffff7f4f000 0x007ffff7fa7000 0x000000001bd000 r-- [REDACTED]/lib/libc.so.6
0x007ffff7fa7000 0x007ffff7fa8000 0x00000000215000 --- [REDACTED]/lib/libc.so.6
0x007ffff7fa8000 0x007ffff7fac000 0x00000000215000 r-- [REDACTED]/lib/libc.so.6
0x007ffff7fac000 0x007ffff7fae000 0x00000000219000 rw- [REDACTED]/lib/libc.so.6
0x007ffff7fae000 0x007ffff7fbd000 0x00000000000000 rw-
0x007ffff7fbd000 0x007ffff7fc1000 0x00000000000000 r-- [vvar]
0x007ffff7fc1000 0x007ffff7fc3000 0x00000000000000 r-x [vdso]
0x007ffff7fc3000 0x007ffff7fc5000 0x00000000000000 r-- [REDACTED]/lib/ld-linux-x86-64.so.2
0x007ffff7fc5000 0x007ffff7fef000 0x00000000002000 r-x [REDACTED]/lib/ld-linux-x86-64.so.2
0x007ffff7fef000 0x007ffff7ffa000 0x0000000002c000 r-- [REDACTED]/lib/ld-linux-x86-64.so.2
0x007ffff7ffb000 0x007ffff7ffd000 0x00000000037000 r-- [REDACTED]/lib/ld-linux-x86-64.so.2
0x007ffff7ffd000 0x007ffff7fff000 0x00000000039000 rw- [REDACTED]/lib/ld-linux-x86-64.so.2
0x007ffffffde000 0x007ffffffff000 0x00000000000000 rw- [stack]It is much more obvious with syntax highlighting, but suspiciously there are two contiguous r-x segments inside libc, which we can verify did not exist at the start of the program.
0x007ffff7dba000 0x007ffff7f4e000 0x00000000028000 r-x [REDACTED]/lib/libc.so.6
0x007ffff7f4e000 0x007ffff7f4f000 0x000000001bc000 r-x [REDACTED]/lib/libc.so.6Could the memory have been tampered?
gef➤ watch *(char [4096]*)0x7ffff7f4e000
Watchpoint 1: *(char [4096]*)0x7ffff7f4e000
gef➤ r$r8 : 0x0
$r9 : 0x0
$r10 : 0x007ffff7f4e350 → 0x00000000000000c3
...
0x40158a mov BYTE PTR [r10+r8*1], al
→ 0x40158e inc rcx
...
gef➤ vmmap
...
0x007ffff7dba000 0x007ffff7f4e000 0x00000000028000 r-x [REDACTED]/lib/libc.so.6
0x007ffff7f4e000 0x007ffff7f4f000 0x000000001bc000 rwx [REDACTED]/lib/libc.so.6
...And 0x40158a is inside the shadow function.
Important note: The challenge was actually patched halfway through the CTF:
- we have updated the dist file for mazeware to include libc and ld, to avoid unintentional behaviour. the solution has not changed.
where the binary links to a specific provided libc instead of the default system one. Before the patch, on some libc versions (like mine), the program crashes at the start of the second maze within the tampered address range, immediately drawing suspicion and hence making detection easier.
(To be fair, this is before the much more giveaway hint was released, so)
Part IIC: Forensic Investigation
Above are the traces I’ve caught during my solve, but there are other traces left behind as well:
- Running
straceon the binary, at the first maze:
write(1, "\tW A S D to navigate\n", 21 W A S D to navigate
) = 21
write(1, "\t###########\n", 13 ###########
) = 13
write(1, "\t#^# #\n", 13 #^# #
) = 13
write(1, "\t# ### # ###\n", 13 # ### # ###
) = 13
write(1, "\t# # # #\n", 13 # # # #
) = 13
write(1, "\t# ### ### #\n", 13 # ### ### #
) = 13
write(1, "\t# #F #\n", 13 # #F #
) = 13
write(1, "\t###########\n", 13 ###########
) = 13
mprotect(0x7fbf7b6b9000, 4096, PROT_READ|PROT_WRITE|PROT_EXEC) = 0
mprotect(0x7fbf7b6b9000, 4096, PROT_READ|PROT_EXEC) = 0
mprotect(0x401000, 4096, PROT_READ|PROT_WRITE|PROT_EXEC) = 0
mprotect(0x401000, 4096, PROT_READ|PROT_EXEC) = 0These mprotects are completely out of the ordinary and can be immediately investigated further (see the part above).
- If you break into the debugger right at the start of the second maze you could notice a suspicious unlabeled function (#3) between the ones in the binary and the libc calls:
[#0] 0x7ffff7ea67e2 → read()
[#1] 0x7ffff7e1ec36 → _IO_file_underflow()
[#2] 0x7ffff7e1fd96 → _IO_default_uflow()
[#3] 0x7ffff7f4e50d → mov rbx, rax
[#4] 0x401a7c → mov BYTE PTR [rbp-0x9], al
[#5] 0x401d05 → mov eax, 0x0
[#6] 0x7ffff7dbbd90 → mov edi, eax
[#7] 0x7ffff7dbbe40 → __libc_start_main()
[#8] 0x401135 → hltThe function is indeed within the tampered address range. Also further investigation tells us that the instructions located there has been modified since the start of the program.
- While investigating one of the global variables used in the
RC4algorithm we notice a suspicious and large nonsensical global variable right below that hasn’t seem to be discovered by us yet:
.data:0000000000405380 ; unsigned __int16 word_405380[664]
.data:0000000000405380 word_405380 dw 1B5h, 887h, 0E189h, 0AD05h, 0DF03h, 1696h, 9FA5h, 95BFh
.data:0000000000405380 ; DATA XREF: sub_4014C5+94↑o
.data:0000000000405390 dw 9EF6h, 0CA2Fh, 29DDh, 0F368h, 0D812h, 2EDEh, 0A4C1h
...
.data:000000000040552A dw 997Ah, 5AA0h, 95B5h, 91F6h, 7C62h, 9729h, 22h, 4 dup(0)
.data:0000000000405540 dw 362h, 0FFA1h, 52F8h, 895Dh, 6363h, 9132h, 7DE8h, 0D50h
.data:0000000000405550 dw 2740h, 88FBh, 5B07h, 7CCDh, 6515h, 7AFCh, 655Ch, 3412h
...
.data:000000000040589C dw 45B4h, 0B255h, 5A36h, 8731h, 6 dup(0)And guess what, it XREFs into the shadow function.
Part III: Shellcode Train
Part IIIA: Trojan Wrapper
Let us finally explore the shadow function.
void sub_4014C5()
{
void (*v0)(); // rbx
_BYTE *v1; // rdi
bool v2; // zf
_BYTE *v3; // rsi
__int64 v4; // rcx
_QWORD *v5; // rbx
__int64 i; // r9
_QWORD *v7; // r10
__int64 v8; // r8
char *v9; // rdi
__int64 v10; // rcx
__int64 v11; // r9
void *v12; // r10
void (*v13)(); // rax
__int64 (__fastcall *v14)(char *, int, int); // rax
__int64 j; // rcx
_QWORD v16[3]; // [rsp+0h] [rbp-28h]
void (*v17)(); // [rsp+18h] [rbp-10h]
v0 = (void (*)())((unsigned __int64)&printf & 0xFFFFFFFFFFFFF000LL);
do
{
v0 = (void (*)())((char *)v0 + 4096);
v1 = (char *)v0 - 1;
v3 = (char *)v0 - 513;
v2 = v0 == (void (*)())513;
v4 = 512LL;
do
{
if ( !v4 )
break;
v2 = *v3-- == *v1--;
--v4;
}
while ( v2 );
}
while ( !v2 );
__asm { syscall; LINUX - }
v17 = v0;
v5 = (_QWORD *)((char *)v0 - 4096);
while ( 1 )
{
for ( i = 10LL; ; --i )
{
if ( !i )
{
v7 = v5 - 18;
v8 = 0LL;
v9 = (char *)&word_405380[1] + word_405380[0];
v10 = -(__int64)word_405380[0];
v11 = 0LL;
while ( 1 )
{
*((_BYTE *)v7 + v8++) = byte_405340[v11] ^ v9[v10++];
if ( ++v11 == 32 )
v11 = 0LL;
if ( !v10 )
{
*(_QWORD *)((char *)v7 + 78) = &getchar;
__asm { syscall; LINUX - }
v12 = (char *)v7 + 41;
off_404040 = v12;
__asm { syscall; LINUX - sys_mprotect }
v13 = sub_4014C5;
v17 = sub_4014C5;
do
v13 = (void (*)())((char *)v13 + 1);
while ( *(_DWORD *)v13 != -98693133 );
v16[2] = (char *)v13 - (char *)sub_4014C5;
v14 = sub_4017CD;
do
v14 = (__int64 (__fastcall *)(char *, int, int))((char *)v14 + 1);
while ( (*(_DWORD *)v14 ^ 0xDEADBEEF) != 491649892 );
v16[1] = 15LL;
v16[0] = 0x52C89480A000000LL;
for ( j = 0LL; ; ++j )
{
*((_BYTE *)v14 + j) ^= *((_BYTE *)v16 + j);
if ( j == 9 )
break;
}
*(_QWORD *)((char *)v14 - 7) = 0x8B90909090909090LL;
*(_BYTE *)v17 = 0;
__asm { retn }
}
}
}
v5 += 2;
if ( *v5 )
break;
}
}
}To be honest I found the decompilation annoying to read so I went to read the assembly instead. (Perhaps also honouring the author who crafted the entire remaining portion of the challenge by hand o7)
Firstly some introduction. There is a snippet commonly found in subsequent shellcodes:
mov rax, 1
shl rax, 3
sub rax, 0FFFFFFFFFFFFFFFEh
mov rdi, rbx
sub rdi, 1000h
mov rsi, 1000h
mov rdx, 7
syscallwith mov rdx, 5, they make up the mprotect calls (rax = 0b1010) that allow shellcode to be constantly loaded and unloaded beneath detection. After it is used up, each shellcode loads in its subsequent chunk of shellcode and also deletes itself in the process, forming a shellcode train. This is also why mprotect is run on the binary portion of the memory and why the shadow function is only run once despite it being hooked to the draw-and-check-win function. We will see it in action later.
Let’s start from the beginning:
sub_4014C5 proc near
var_28= byte ptr -28h
anonymous_0= qword ptr -10h
push rdi
mov rbx, ds:off_404038
and rbx, 0FFFFFFFFFFFFF000h
loc_4014D5:
add rbx, 1000h
mov rdi, rbx
sub rdi, 1
mov rsi, rdi
sub rsi, 200h
mov rcx, 200h
std
repe cmpsb
jnz short loc_4014D5This seems that the shellcode is attempting to locate a suitable location to home itself in. Basically the last 0x400 bytes of each page were compared (as two strings of length 0x200) until they are the same. Probably an interesting approach to find a null region (don’t fully understand).
mov rax, 1
shl rax, 3
sub rax, 0FFFFFFFFFFFFFFFEh
mov rdi, rbx
sub rdi, 1000h
mov rsi, 1000h
mov rdx, 7
syscall ; LINUX -
push rbx
sub rbx, 1000hOnce found, the page is converted to rwx, the location is saved (on the stack), and the pointer now points to the start (instead of end) of the page.
Now we enter a more interesting loop, the graph of which was generated in IDA in an extremely ugly way:
loc_40152A:
mov r9, 0Ah
loc_401531:
test r9, r9
jz short loc_401547
add rbx, 10h
mov rax, [rbx]
test rax, rax
jnz short loc_40152A
dec r9
jmp short loc_401531The program basically tries to find 10 consecutive blocks (owords) of 0x0 (only the starting qword is checked though). If any starting qword is not 0x0 in the process the loop restarts from the beginning.
Exiting the loop:
loc_401547:
mov r10, rbx
sub r10, 90h
mov r15, ds:off_404040
lea rdi, word_405380
xor rcx, rcx
mov r8, rcx
mov cx, [rdi]
add rdi, rcx
inc rdi
inc rdi
lea rsi, byte_405340
neg rcx
xor r9, r9Firstly, the start of the mini null region and the GOT entry for getchar are saved in r10 and r15 respectively.
Next, see point 3 of Part IIC. Here the first word (saved in rcx) seems to be treated as the size of the data, with rdi pointing to the end of the data. rsi in turn points to what seems like a key (as mentioned, used in the RC4 algorithm).
Now another loop:
loc_401581:
mov al, [rdi+rcx]
mov dl, [rsi+r9]
xor al, dl
mov [r10+r8], al
inc rcx
inc r8
inc r9
cmp r9, 20h ; ' '
jnz short loc_4015A4
mov r9, 0
loc_4015A4:
test rcx, rcx
jnz short loc_401581The loop counter is quite interesting, but ltimately the bytes still get iterated in the standard fashion.
for rcx in range(-len(DATA), 0):
cur = DATA[len(DATA)+rcx]
# ...r8 and r9 iterate over rsi (the key) and r10 (the target memory region) respectively. r9 is of course modulo-treated with the length of the key. But other than that we can see that this is but a simple xor decryption to get our next shellcode.
We can try looking at it directly in IDA, but for some reason even the disassembly is incredibly disgusting, so I gave up and explored it inside GDB instead (but this will be for later).
mov [r10+4Eh], r15
pop rbx
mov rax, 1
shl rax, 3
sub rax, 0FFFFFFFFFFFFFFFEh
mov rdi, rbx
sub rdi, 1000h
mov rsi, 1000h
mov rdx, 5
syscall ; LINUX -
add r10, 29h ; ')'
mov ds:off_404040, r10This hooks the decrypted shellcode to the getchar function, by making the getchar call jump to the shellcode (r10+0x29) and allowing the shellcode (r10+0x4e) jump to getchar afterwards.
At the same time the page gets closed off from writing (r-x) to avoid suspicion.
The rest of the shellcode focuses on removing itself from the binary, since a new shellcode is hooked to a different function and we don’t want this particular shellcode to run anymore. But I would not detail it here.
sub r10, 22h ; '"'
push r10
retn
sub_4014C5 endp ; sp-analysis failedNear the end, we jump to a specific offset in the new shellcode. As mentioned we will explore the new shellcode in GDB instead:
gef➤ b *0x4016fd
Breakpoint 1 at 0x4016fd
gef➤ r
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x4016f6 cld
0x4016f7 sub r10, 0x22
0x4016fb push r10
●→ 0x4016fd ret
↳ 0x7ffff7f4e357 rep movs BYTE PTR es:[rdi], BYTE PTR ds:[rsi]
0x7ffff7f4e359 mov rax, 0xa
0x7ffff7f4e360 and rdi, 0xfff000
0x7ffff7f4e367 mov rsi, 0x1000
0x7ffff7f4e36e mov rdx, 0x5
0x7ffff7f4e375 syscall
...
gef➤ x/6i 0x7ffff7f4e350
0x7ffff7f4e350: ret
0x7ffff7f4e351: pop rbp
0x7ffff7f4e352: jmp 0x7ffff7f4e350
0x7ffff7f4e354: pop rax
0x7ffff7f4e355: jmp 0x7ffff7f4e351
0x7ffff7f4e357: rep movs BYTE PTR es:[rdi],BYTE PTR ds:[rsi]
0x7ffff7f4e359: mov rax,0xa
0x7ffff7f4e360: and rdi,0xfff000
0x7ffff7f4e367: mov rsi,0x1000
0x7ffff7f4e36e: mov rdx,0x5
0x7ffff7f4e375: syscall
0x7ffff7f4e377: jmp 0x7ffff7f4e354Honestly not much here also, just a continuation of the shellcode wipe and closing off .text from writes. The program then returns to normal execution and the injection is complete.
Part IIIB: Logic Bomb
Remember the GOT modification from above?
gef➤ x/gx 0x404040
0x404040 <getchar@got.plt>: 0x00007ffff7f4e379This points to the start of our second carriage of the shellcode train. We shall take a look at the assembly:
gef➤ x/100i 0x00007ffff7f4e379
0x7ffff7f4e379: mov rax,rsp
0x7ffff7f4e37c: add rax,0x4
0x7ffff7f4e380: movabs rbx,0xdeadbeef
0x7ffff7f4e38a: xor ebx,DWORD PTR [rax]
0x7ffff7f4e38c: cmp ebx,0xd1beafe5
0x7ffff7f4e392: jne 0x7ffff7f4e37c
0x7ffff7f4e394: mov ecx,DWORD PTR [rax-0x4]
0x7ffff7f4e397: cmp ecx,0x1
0x7ffff7f4e39a: je 0x7ffff7f4e3a8
0x7ffff7f4e39c: movabs rbx,0x7ffff7e19ae0
0x7ffff7f4e3a6: jmp rbx
...The program seems to be looking for a specific variable on the stack demarcated through a loaded signature. We don’t have to carry out extra analysis, we can simply set a breakpoint there:
gef➤ b *0x7ffff7f4e394
Breakpoint 2 at 0x7ffff7f4e394
gef➤ c
Continuing.
...
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x007fffffffdfbc → 0xffffdfd00f13110a
...
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x007fffffffdfa8│+0x0000: 0x00000000401a7c → mov BYTE PTR [rbp-0x9], al ← $rsp
0x007fffffffdfb0│+0x0008: 0x0001010000000000
0x007fffffffdfb8│+0x0010: 0x0f13110a00000000
0x007fffffffdfc0│+0x0018: 0x007fffffffdfd0 → 0x0000000000000001 ← $rbpecx seems to be rbp-0x8 in the game loop function, which we can easily figure out (from e.g. IDA but honestly anywhere) that that is used by the level variable. We need our level to be 0x1 (i.e. second level), otherwise the shellcode short-circuits and the regular getchar libc function is run.
The rest of the shellcode is honestly not that interesting and can be skipped dynamically, but the main gist is:
- Open the current page for writes again
- Load
0x39intor15(singled out; its importance will be shown later) - Load another signature onto the stack (??)
- Decrypt a new shellcode from (A) to (B) using the same method
- (A)
0x405540(right below the first shellcode in.data) - (B) The memory location marked by yet another signature (
0xbabe1337), which we can easily find to be just right below where this current shellcode is located
- (A)
- Hook
getcharto the new shellcode - Clear the current shellcode
- Close the current page from writes
- The program continues off where the new shellcode is written to.
Part IIIC: Keylogger Maze…?
Based on our deductions above, we will be able to view our next stage of shellcode after entering level 2. Once again this shellcode is hooked to getchar. Let us now analyse it:
gef➤ x/213i 0x7ffff7f4e501
0x7ffff7f4e501: movabs rbx,0x7ffff7e19ae0
0x7ffff7f4e50b: call rbx
0x7ffff7f4e50d: mov rbx,rax
0x7ffff7f4e510: xor rdx,rdx
0x7ffff7f4e513: cmp rax,0x61
0x7ffff7f4e517: jb 0x7ffff7f4e51d
0x7ffff7f4e519: sub rax,0x20
0x7ffff7f4e51d: cmp rax,0x41
0x7ffff7f4e521: je 0x7ffff7f4e547
0x7ffff7f4e523: cmp rax,0x57
0x7ffff7f4e527: je 0x7ffff7f4e53a
0x7ffff7f4e529: cmp rax,0x53
0x7ffff7f4e52d: je 0x7ffff7f4e554
0x7ffff7f4e52f: cmp rax,0x44
0x7ffff7f4e533: je 0x7ffff7f4e561
0x7ffff7f4e535: jmp 0x7ffff7f4e85f
0x7ffff7f4e53a: mov rdi,0x1
0x7ffff7f4e541: sub r15,0x12
0x7ffff7f4e545: jmp 0x7ffff7f4e56e
0x7ffff7f4e547: mov rdi,0x2
0x7ffff7f4e54e: sub r15,0x1
0x7ffff7f4e552: jmp 0x7ffff7f4e56e
0x7ffff7f4e554: mov rdi,0x3
0x7ffff7f4e55b: add r15,0x12
0x7ffff7f4e55f: jmp 0x7ffff7f4e56e
0x7ffff7f4e561: mov rdi,0x4
0x7ffff7f4e568: add r15,0x1
0x7ffff7f4e56c: jmp 0x7ffff7f4e56e
...
0x7ffff7f4e85f: mov rax,rbx
0x7ffff7f4e862: retInterestingly the shellcode starts off by calling the actual getchar function. Obviously this stage of hook attempts to do something with our input.
Based on the je branches, we can tell that the program matches our input against WASD (case insensitive due to the branch right before). For invalid input, the program short-circuits immediately.
Now you see the r15? Recall that it was set to 0x39 in the previous shellcode, and interestingly it did not get modified at all between getchar calls (according to dynamic analysis). Either way, the sub and adds are immediately remeniscent of 2D maze controls.
0x7ffff7f4e56e: movabs rcx,0xffff
0x7ffff7f4e578: push rcx
0x7ffff7f4e579: movabs rcx,0xffffff
0x7ffff7f4e583: push rcx
0x7ffff7f4e584: movabs rcx,0xcff03c00
0x7ffff7f4e58e: push rcx
0x7ffff7f4e58f: movabs rcx,0x3c300fff
0x7ffff7f4e599: push rcx
0x7ffff7f4e59a: movabs rcx,0xcffff00c
0x7ffff7f4e5a4: push rcx
0x7ffff7f4e5a5: movabs rcx,0xc033cf3
0x7ffff7f4e5af: push rcx
0x7ffff7f4e5b0: movabs rcx,0xcf30c03c
0x7ffff7f4e5ba: push rcx
0x7ffff7f4e5bb: movabs rcx,0xf3cffffc
0x7ffff7f4e5c5: push rcx
0x7ffff7f4e5c6: movabs rcx,0xc03c0c
0x7ffff7f4e5d0: push rcx
0x7ffff7f4e5d1: movabs rcx,0xfcf3cfcf
0x7ffff7f4e5db: push rcx
0x7ffff7f4e5dc: movabs rcx,0xc3cdcff
0x7ffff7f4e5e6: push rcx
0x7ffff7f4e5e7: movabs rcx,0xefccc303
0x7ffff7f4e5f1: push rcx
0x7ffff7f4e5f2: movabs rcx,0xfc0f0303
0x7ffff7f4e5fc: push rcx
0x7ffff7f4e5fd: movabs rcx,0xffffffff
0x7ffff7f4e607: push rcxFor now it seems like a bunch of irrelevant stuff is pushed onto the stack. We will understand its significance very soon.
0x7ffff7f4e608: mov rax,r15
0x7ffff7f4e60b: mov rcx,0x10
0x7ffff7f4e612: div ecx
0x7ffff7f4e614: nop
0x7ffff7f4e615: inc rax
0x7ffff7f4e618: mov r9,rax
0x7ffff7f4e61b: mov r10,raxNote that div in assembly is essentially divmod, where
rax = rax // <operand>andrdx = rax % <operand>.
0x7ffff7f4e61e: pop r8
0x7ffff7f4e620: dec eax
0x7ffff7f4e622: test eax,eax
0x7ffff7f4e624: jne 0x7ffff7f4e61eo
...
0x7ffff7f4e642: mov rax,r9
0x7ffff7f4e645: neg rax
0x7ffff7f4e648: add rax,0xe
0x7ffff7f4e64c: pop r9
0x7ffff7f4e64e: dec eax
0x7ffff7f4e650: test eax,eax
0x7ffff7f4e652: jne 0x7ffff7f4e64cThis loop pops the top of the stack into r8 a number of times equal to (r15//0x10) + 1. Afterwards, correspondingly, the stack is popped 14 - ((r15//0x10)+1) times, to clear the stack of the junk added earlier.
0x7ffff7f4e626: shl edx,1
0x7ffff7f4e628: neg edx
0x7ffff7f4e62a: add edx,0x1e
0x7ffff7f4e62d: mov r11,rdx
0x7ffff7f4e630: test rdx,rdx
0x7ffff7f4e633: je 0x7ffff7f4e63e
0x7ffff7f4e635: shr r8,1
0x7ffff7f4e638: dec edx
0x7ffff7f4e63a: test edx,edx
0x7ffff7f4e63c: jne 0x7ffff7f4e635
0x7ffff7f4e63e: and r8,0x3Here our loop value is 0x1e - 2*(r15%0x10). The equivalent number of bits is shifted off r8, and only the 2 LSBs are kept at the end.
Combined, this mimics x,y-indexing of a 2D structure (16 wide by 14 tall). Each cell in the structure has 4 possible values, taking up 2 bits each. The indexing comes purely from r15 — the div by 0x10 part makes perfect sense (since the structure is 16 wide), but the up/down controls changing r15 by 0x12 is pretty unintuitive and I just assumed that up/down moves the player diagonally.
0x7ffff7f4e654: cmp r8,0x2
0x7ffff7f4e658: je 0x7ffff7f4e71a
0x7ffff7f4e65e: test r8,r8
0x7ffff7f4e661: jne 0x7ffff7f4e7c0Here, values 0x1 and 0x3 are treated the same: The program unhooks the shellcode, clears itself, and returns, i.e. the hidden functionality ends with no apparent effect at all.
For 0x0, stripping away the mprotects, the main functionality is:
0x7ffff7f4e6a1: mov rdi,0x1
0x7ffff7f4e6a8: test r11,r11
0x7ffff7f4e6ab: je 0x7ffff7f4e6b8
0x7ffff7f4e6ad: shl rdi,1
0x7ffff7f4e6b0: dec r11
0x7ffff7f4e6b3: test r11,r11
0x7ffff7f4e6b6: jne 0x7ffff7f4e6ad
0x7ffff7f4e6b8: lea rsi,[rip+0xffffffffffffff40] # 0x7ffff7f4e5ff
0x7ffff7f4e6bf: mov rcx,r10
0x7ffff7f4e6c2: xor r10,r10
0x7ffff7f4e6c5: mov rax,0xb
0x7ffff7f4e6cc: mul rcx
0x7ffff7f4e6cf: sub rsi,rax
0x7ffff7f4e6d2: add rsi,0xb
0x7ffff7f4e6d6: mov rdx,QWORD PTR [rsi]
0x7ffff7f4e6d9: or rdx,rdi
0x7ffff7f4e6dc: mov QWORD PTR [rsi],rdxRecalling what was previously saved, r10 and r11 correspond to the y and x coordinates respectively. This is really interesting — the program generates a pointer that points to the maze (within the instructions), offsets it according to the player position, and marks the corresponding spot with 0x1. To explain the
0x7ffff7f4e6c5: mov rax,0xbEach of the set of instructions pushing a line of maze onto the stack is 0xb bytes, for example:
0x7ffff7f4e5b0: movabs rcx,0xcf30c03c
0x7ffff7f4e5ba: push rcx
0x7ffff7f4e5bb: movabs rcx,0xf3cffffcSo essentially the instructions are indexed like a 2D structure. Either way the gist is that the program marks off the current position of the player from the maze presumably so that the player cannot return to where it went (since 0x1 (our mark) and 0x3 (probably the walls) are treated the same way).
Finally we have our 0x2 branch. I’m not going to analyse this further as it is pretty clear from here that that will be our win branch, but essentially the program modifies the RC4-encrypted string from the initial maze game (the one that turned out to be the rickroll URL) and writes in the actual encrypted flag. Which means that we should now get the flag upon reaching the end in the initial game.
Part IV: Home Stretch
Let us now solve the embedded maze. The maze has 2 main gimmicks:
- Up/down moves go diagonal instead.
- Left/right has the potential to wrap around (flow to the previous / next line).
To combat this, we can print multiple copies of the maze side by side and offset each copy / line by 1:
MAZE = [
0xffff,
0xffffff,
0xcff03c00,
0x3c300fff,
0xcffff00c,
0xc033cf3,
0xcf30c03c,
0xf3cffffc,
0xc03c0c,
0xfcf3cfcf,
0xc3cdcff,
0xefccc303,
0xfc0f0303,
0xffffffff,
][::-1]
CHR = ' #E#'
for y in range(len(MAZE)):
print(' '*(15-y)*2, end='|')
for k in range(-3, 3):
if y+k >= len(MAZE):
break
line = MAZE[y+k]
tmp = f'{line:032b}'
for x in range(len(tmp)//2):
cur = int(tmp[x*2:(x+1)*2], 2)
if (y+k, x) == (3, 9):
print('S', end='')
continue
print(CHR[cur], end='')
print('|')$ python3 solve.py
|# #### ## ############ ########################### ## # ##E### # # # #|
| ############ ########################### ## # ##E### # # # # # ## #S# ####|
| ########################### ## # ##E### # # # # # ## #S# ####### ## ## ### ##|
|################### ## # ##E### # # # # # ## #S# ####### ## ## ### ## # ## # |
|### ## # ##E### # # # # # ## #S# ####### ## ## ### ## # ## # ## ## ######### |
|#E### # # # # # ## #S# ####### ## ## ### ## # ## # ## ## ######### # ## # # ## |
| # ## #S# ####### ## ## ### ## # ## # ## ## ######### # ## # # ## # # ## ## #|
|### ## ## ### ## # ## # ## ## ######### # ## # # ## # # ## ## ## ######## # |
| # ## # ## ## ######### # ## # # ## # # ## ## ## ######## # ## # ######|
|## ## ######### # ## # # ## # # ## ## ## ######## # ## # ####### #### ## |
|# ## # # ## # # ## ## ## ######## # ## # ####### #### ## ############|
| # # ## ## ## ######## # ## # ####### #### ## ############ ########|
|# ######## # ## # ####### #### ## ############ ########|
| ## # ####### #### ## ############ ########|Solving the maze manually, we get
wwaassssddssaassdsddwdddsddddddddwwdwwaaassaaawwdwwaaasssaaawwwwwdwddsddwddsdssdddwwawAfter entering the payload while in level 2, we manually jump straight to the win function and that will yield us the flag.
gef➤ set $rip=0x401c2b
gef➤ c
Continuing.
grey{h1dd3n_1n_pl41n51gh7_35ffcbede152a94e}Cooking Mama
Category: rev
Points: 999
Solves: 3
Description:
im new to rust, so i cooked this :)
Author: kestryix
Part I: Introduction
$ ./cooking_mama
⠀⠀⢀⣴⣿⣿⣷⣦⣌⠛⢦⡀⠀⠈⠓⢦⣀⡀⠀⣸⣿⣿⣿⡀⠀
⠀⠀⡾⠋⠉⢿⣿⣿⡿⠟⠦⣝⡲⣄⣀⠀⠈⠉⠉⣽⡿⢿⣿⡇⠀
⠀⠀⣷⠀⣠⣿⡿⠋⠀⠀⣶⢤⣙⠳⢭⣙⠲⠤⠴⠋⠑⠀⠁⣧⠀
⠀⠀⢸⡼⠛⠛⠀⠀⠀⣼⠉⢿⣿⣧⣶⡿⠛⠶⢤⣀⠀⠀⠀⣻
⠀⠀⢨⡇⠀⠀⠀⠀⠀⠈⠉⠉⢸⡟⣺⠃⠀⠀⠀⠈⠙⠲⠶⠋⠀
⠀⠀⣸⠁⠀⠀⠀⠀⠀⢀⡀⠀⢸⡷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣰⠃⠀⠀⠀⠠⣄⡀⠀⠉⣳⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀WHO LET HIM COOK
⣞⠁⠀⠲⣄⠀⠀⠀⠉⠉⡷⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣌⠳⣤⡀⠈⠓⠦⢤⡴⠚⠁⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⠀⠀⠀⠀
⣿⣷⣤⡿⢷⠀⣀⡴⣷⠒⠒⢒⣶⢤⠞⠉⠙⢻⣿⣷⣄⠀⠀⠀⠀
⠙⠻⣿⣷⠈⠛⠙⡇⣿⠀⠀⢯⣽⢿⠀⠀⠀⣴⠚⠉⠛⠀⠀⠀⠀
⣶⣆⠀⢹⣠⠶⣄⡇⢻⠛⠓⠒⠚⠋⠙⠓⠲⠮⠿⠆⠀⠀⠀⠀⠀
⣿⣿⠀⢸⠙⠒⢃⣇⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
> grey{abcd}
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣠⠞⠉⢉⠩⢍⡙⠛⠋⣉⠉⠍⢉⣉⣉⣉⠩⢉⠉⠛⠲⣄⠀⠀⠀⠀
⠀⠀⠀⡴⠁⠀⠂⡠⠑⠀⠀⠀⠂⠀⠀⠀⠀⠠⠀⠀⠐⠁⢊⠀⠄⠈⢦⠀⠀⠀
⠀⣠⡾⠁⠀⠀⠄⣴⡪⠽⣿⡓⢦⠀⠀⡀⠀⣠⢖⣻⣿⣒⣦⠀⡀⢀⣈⢦⡀⠀
⣰⠑⢰⠋⢩⡙⠒⠦⠖⠋⠀⠈⠁⠀⠀⠀⠀⠈⠉⠀⠘⠦⠤⠴⠒⡟⠲⡌⠛⣆
⢹⡰⡸⠈⢻⣈⠓⡦⢤⣀⡀⢾⠩⠤⠀⠀⠤⠌⡳⠐⣒⣠⣤⠖⢋⡟⠒⡏⡄⡟ COOK HARDER
⠀⠙⢆⠀⠀⠻⡙⡿⢦⣄⣹⠙⠒⢲⠦⠴⡖⠒⠚⣏⣁⣤⣾⢚⡝⠁⠀⣨⠞⠀
⠀⠀⠈⢧⠀⠀⠙⢧⡀⠈⡟⠛⠷⡾⣶⣾⣷⠾⠛⢻⠉⢀⡽⠋⠀⠀⣰⠃⠀⠀
⠀⠀⠀⠀⠑⢤⡠⢂⠌⡛⠦⠤⣄⣇⣀⣀⣸⣀⡤⠼⠚⡉⢄⠠⣠⠞⠁⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠉⠓⠮⣔⡁⠦⠀⣤⠤⠤⣤⠄⠰⠌⣂⡬⠖⠋⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠒⠤⢤⣀⣀⡤⠴⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀Rust rev is particularly annoying because its “ABI is not extremely well-defined” apparently, and the decompilation is all over the place (to be fair the disassembly too). Plus there are way too many error checks built into the functions that don’t add substance to the logic but clutter the disassembly.
As usual, we will start from the strings. Near the end of the main function there are two print blocks side by side, which look pretty much identical except for of course the string that is printed out (0x49882 vs 0x4948c).
loc_9721:
lea rax, unk_49882
mov [rsp+308h+var_2C8], rax
mov qword ptr [rsp+48h], 407h
mov qword ptr [rsp+308h+var_308], r14
mov qword ptr [rsp+308h+var_308+8], r15
mov qword ptr [rsp+308h+var_2B8], r12
mov qword ptr [rsp+308h+var_2B8+8], 1
mov [rsp+308h+var_298], 0
mov qword ptr [rsp+308h+var_2A8], rbx
mov qword ptr [rsp+308h+var_2A8+8], 1
lea rdi, [rsp+308h+var_2B8]
call cs:_ZN3std2io5stdio6_print17ha0212c65ac6652d4E_ptr ; std::io::stdio::_print::ha0212c65ac6652d4 ...gef➤ x/s 0x55555559d882
0x55555559d882: "⢻⣿⡗⢶⣤⣀", '⠀' <repeats 21 times>, "⣀⣠⣄\n⠀⢻⣇⠀⠈⠙⠳⣦⣀", '⠀' <repeats 13 times>, "⣀⣤⠶⠛⠋⣹⣿⡿\n⠀⠀⠹⣆⠀⠀⠀⠀⠙⢷⣄⣀⣀⣀⣤⣤⣤⣄⣀⣴⠞⠋⠉⠀⠀⠀⢀⣿⡟⠁\n⠀⠀⠀⠙⢷⡀⠀⠀⠀⠀⠉⠉⠉", '⠀' <repeats 12 times>, "⣠⡾⠋⠀⠀\n⠀⠀⠀⠀⠈⠻⡶⠂", '⠀' <repeats 14 times>, "⢠⣠⡾⠋⠀⠀⠀⠀\n⠀⠀⠀⠀⠀⣼⠃⠀⢠⠒⣆⠀⠀⠀⠀⠀⠀⢠⢲⣄⠀⠀⠀⢻⣆⠀⠀⠀⠀⠀\n⠀⠀⠀⠀⢰⡏⠀⠀⠈⠛⠋⠀⢀⣀⡀⠀⠀⠘⠛⠃⠀⠀⠀⠈⣿⡀⠀⠀⠀⠀\n⠀⠀⠀⠀⣾⡟⠛⢳⠀⠀⠀⠀⠀⣉⣀⠀⠀⠀⠀⣰⢛⠙⣶⠀⢹⣇⠀⠀⠀⠀ flag is grey{your_input_here} :)\n⠀⠀⠀⠀⢿⡗⠛⠋⠀⠀⠀⠀⣾⠋⠀⢱⠀⠀⠀⠘⠲⠗⠋⠀⠈⣿⠀⠀⠀⠀\n⠀⠀⠀⠀⠘⢷⡀⠀⠀⠀⠀⠀⠈⠓⠒⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡇⠀⠀⠀\n⠀⠀⠀⠀⠀⠈⡇", '⠀' <repeats 18 times>, "⢸⣧⠀⠀\n"
gef➤ x/s 0x55555559d48c
0x55555559d48c: '⠀' <repeats 30 times>, "\n⠀⠀⠀⠀⣠⠞⠉⢉⠩⢍⡙⠛⠋⣉⠉⠍⢉⣉⣉⣉⠩⢉⠉⠛⠲⣄⠀⠀⠀⠀\n⠀⠀⠀⡴⠁⠀⠂⡠⠑⠀⠀⠀⠂⠀⠀⠀⠀⠠⠀⠀⠐⠁⢊⠀⠄⠈⢦⠀⠀⠀\n⠀⣠⡾⠁⠀⠀⠄⣴⡪⠽⣿⡓⢦⠀⠀⡀⠀⣠⢖⣻⣿⣒⣦⠀⡀⢀⣈⢦⡀⠀\n⣰⠑⢰⠋⢩⡙⠒⠦⠖⠋⠀⠈⠁⠀⠀⠀⠀⠈⠉⠀⠘⠦⠤⠴⠒⡟⠲⡌⠛⣆\n⢹⡰⡸⠈⢻⣈⠓⡦⢤⣀⡀⢾⠩⠤⠀⠀⠤⠌⡳⠐⣒⣠⣤⠖⢋⡟⠒⡏⡄⡟ COOK HARDER\n⠀⠙⢆⠀⠀⠻⡙⡿⢦⣄⣹⠙⠒⢲⠦⠴⡖⠒⠚⣏⣁⣤⣾⢚⡝⠁⠀⣨⠞⠀\n⠀⠀⠈⢧⠀⠀⠙⢧⡀⠈⡟⠛⠷⡾⣶⣾⣷⠾⠛⢻⠉⢀⡽⠋⠀⠀⣰⠃⠀⠀\n⠀⠀⠀⠀⠑⢤⡠⢂⠌⡛⠦⠤⣄⣇⣀⣀⣸⣀⡤⠼⠚⡉⢄⠠⣠⠞⠁⠀⠀⠀\n⠀⠀⠀⠀⠀⠀⠉⠓⠮⣔⡁⠦⠀⣤⠤⠤⣤⠄⠰⠌⣂⡬⠖⠋⠀⠀⠀⠀⠀⠀\n⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠒⠤⢤⣀⣀⡤⠴⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀\n⢻⣿⡗⢶⣤⣀", '⠀' <repeats 21 times>, "⣀⣠⣄\n⠀⢻⣇⠀⠈⠙⠳⣦⣀", '⠀' <repeats 13 times>, "⣀⣤⠶⠛⠋⣹⣿⡿\n⠀⠀⠹⣆⠀⠀⠀⠀⠙⢷⣄⣀⣀⣀⣤⣤⣤⣄⣀⣴⠞⠋⠉⠀⠀⠀⢀⣿⡟⠁\n⠀⠀⠀⠙⢷⡀⠀⠀⠀⠀⠉⠉⠉", '⠀' <repeats 12 times>, "⣠⡾⠋⠀⠀\n⠀⠀⠀⠀⠈⠻⡶⠂", '⠀' <repeats 14 times>, "⢠⣠⡾⠋⠀⠀⠀⠀\n⠀⠀⠀⠀⠀⣼⠃⠀⢠⠒⣆⠀⠀⠀⠀⠀⠀⢠⢲⣄⠀⠀⠀⢻⣆⠀⠀⠀⠀⠀\n⠀⠀⠀⠀⢰⡏⠀⠀⠈⠛⠋⠀⢀⣀⡀⠀⠀⠘⠛⠃⠀⠀⠀⠈⣿⡀⠀⠀⠀⠀\n⠀⠀⠀⠀⣾⡟⠛⢳⠀⠀⠀⠀⠀⣉⣀⠀⠀⠀⠀⣰⢛⠙⣶⠀⢹⣇⠀⠀⠀⠀ flag is grey{your_input_here} :)\n⠀⠀⠀⠀⢿⡗⠛⠋⠀⠀⠀⠀⣾⠋⠀⢱⠀⠀⠀⠘⠲⠗⠋⠀⠈⣿⠀⠀⠀⠀\n⠀⠀⠀⠀⠘⢷⡀⠀⠀⠀⠀⠀⠈⠓⠒⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡇⠀⠀⠀\n⠀⠀⠀⠀⠀⠈⡇", '⠀' <repeats 18 times>, "⢸⣧⠀⠀\n"Oh right, Rust strings are not null-terminated. Either way, we can tell that 0x49882 is the win branch while 0x4948c is the lose branch.
Now, the control flow. The graph generated by IDA looks extremely daunting, but upon closer inspection we can actually see that it can be broken into multiple constituent parts:
Additionally, we see that a lot of the mess is contributed by the jmps to the error (bounds check?) and lose branches. Look at how much cleaner the graph becomes once we hide them (I simply undefined the nodes in IDA):
Still, with the verbosity and repetitiveness, I can’t help to wonder whether the challenge is slightly obfuscated or whether assembling Rust just sucks.
But now we can at least break the problem into parts for us to work on — refer to the table of contents at the top for navigation.
Part II: Head
We shall start scanning through the disassembly from the beginning.
One tip I generally follow in Rust disassembly is to understand the big picture first before delving into specifics as needed, which we can easily accomplish by looking at what functions are called. Of course this is not foolproof and may cause us to miss out critical information in well-structured binaries, but this works 90% of the time.
For this, we can enable basic block boundaries in IDA (Options > General > Disassembly > Display disassembly lines) for an easier time scanning too.
For example, we can basically skip over the very first block as we can tell that the functions referenced and called are all related to printing stuff on the screen. We then look at the second block:
mov rax, 500000000h
mov qword ptr [rsp+308h+var_168], rax
pxor xmm0, xmm0
movdqu [rsp+308h+var_168+8], xmm0
mov dword ptr [rsp+308h+var_158+8], 0
movaps xmm1, cs:xmmword_49000
movups [rsp+308h+var_158+0Ch], xmm1
mov rax, 600000000h
mov [rsp+308h+var_13C], rax
movdqu [rsp+308h+var_134], xmm0
movdqu [rsp+308h+var_124], xmm0
mov [rsp+308h+var_114], 0
mov rax, 400000008h
mov [rsp+308h+var_10C], rax
movdqu [rsp+308h+var_104], xmm0
movdqu [rsp+308h+var_104+0Ch], xmm0
movaps xmm1, cs:xmmword_49010
movups [rsp+308h+var_E8], xmm1
movdqu [rsp+308h+var_D8], xmm0
movaps xmm1, cs:xmmword_49020
movups [rsp+308h+var_C8], xmm1
movaps xmm1, cs:xmmword_49030
movups [rsp+308h+var_B8], xmm1
movdqu [rsp+308h+var_A8], xmm0
mov [rsp+308h+var_98], 0
movaps xmm1, cs:xmmword_49040
movups [rsp+308h+var_94], xmm1
mov [rsp+308h+var_84], 1
movdqu [rsp+308h+var_74], xmm0
movdqu xmmword ptr [rsp+288h], xmm0
mov rax, 800000001h
mov [rsp+308h+var_64], rax
mov [rsp+308h+var_5C], 9
movdqu [rsp+308h+var_58], xmm0
mov [rsp+308h+var_48], 0
movaps xmm1, cs:xmmword_49050
movups [rsp+308h+var_40], xmm1
mov rax, 300000005h
mov [rsp+308h+var_30], rax
mov [rsp+308h+var_28], 0This block consists almost exclusively of instructions that load values into stack memory. Again Rust uses a lot of owords which I find annoying to rev. So instead of trying to piece them together we can just get the result dynamically.
The memcpyed region spans from rsp+(0x308-0x168) to rsp+(0x308-0x28), which is 41 qwords starting from rsp+0x1a0.
gef➤ b *0x55555555ce68
Breakpoint 1 at 0x55555555ce68
gef➤ r
...
gef➤ x/41gx $rsp+0x1a0
0x7fffffffdcc0: 0x0000000500000000 0x0000000000000000
0x7fffffffdcd0: 0x0000000000000000 0x0000000800000000
0x7fffffffdce0: 0x0000000700000009 0x0000000000000000
0x7fffffffdcf0: 0x0000000000000006 0x0000000000000000
0x7fffffffdd00: 0x0000000000000000 0x0000000000000000
0x7fffffffdd10: 0x0000000000000000 0x0000000800000000
0x7fffffffdd20: 0x0000000000000004 0x0000000000000000
0x7fffffffdd30: 0x0000000000000000 0x0000000000000000
0x7fffffffdd40: 0x0000000000000001 0x0000000700000009
0x7fffffffdd50: 0x0000000000000000 0x0000000000000000
0x7fffffffdd60: 0x0000000600000003 0x0000000000000002
0x7fffffffdd70: 0x0000000200000000 0x0000000400000000
0x7fffffffdd80: 0x0000000000000000 0x0000000000000000
0x7fffffffdd90: 0x0000000500000000 0x0000000400000006
0x7fffffffdda0: 0x0000000100000002 0x0000000000000000
0x7fffffffddb0: 0x0000000000000000 0x0000000000000000
0x7fffffffddc0: 0x0000000100000000 0x0000000900000008
0x7fffffffddd0: 0x0000000000000000 0x0000000000000000
0x7fffffffdde0: 0x0000000000000000 0x0000000000000008
0x7fffffffddf0: 0x0000000000000006 0x0000000300000005
0x7fffffffde00: 0x0000000000000000This looks very interesting. Even though the values are loaded into memory in a weird way, the end result consists almost exclusively of dwords with values from 0 to 9. We will keep a mental note of this memory region for later.
gef➤ x/82wx $rsp+0x1a0
0x7fffffffdcc0: 0x00000000 0x00000005 0x00000000 0x00000000
0x7fffffffdcd0: 0x00000000 0x00000000 0x00000000 0x00000008
0x7fffffffdce0: 0x00000009 0x00000007 0x00000000 0x00000000
0x7fffffffdcf0: 0x00000006 0x00000000 0x00000000 0x00000000
0x7fffffffdd00: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdd10: 0x00000000 0x00000000 0x00000000 0x00000008
0x7fffffffdd20: 0x00000004 0x00000000 0x00000000 0x00000000
0x7fffffffdd30: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdd40: 0x00000001 0x00000000 0x00000009 0x00000007
0x7fffffffdd50: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdd60: 0x00000003 0x00000006 0x00000002 0x00000000
0x7fffffffdd70: 0x00000000 0x00000002 0x00000000 0x00000004
0x7fffffffdd80: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdd90: 0x00000000 0x00000005 0x00000006 0x00000004
0x7fffffffdda0: 0x00000002 0x00000001 0x00000000 0x00000000
0x7fffffffddb0: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffddc0: 0x00000000 0x00000001 0x00000008 0x00000009
0x7fffffffddd0: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdde0: 0x00000000 0x00000000 0x00000008 0x00000000
0x7fffffffddf0: 0x00000006 0x00000000 0x00000005 0x00000003
0x7fffffffde00: 0x00000000 0x00000000The next few lines in the node basically prints something again and calls
io::stdout().flush().unwrap();(Irrelevant, but did it for run / practice.)
Part IIA: Rust Calling Convention? (Extra)
Disclaimer: This part is not extremely important to the writeup and more for my own practice (and reference in the future). I believe Rust disassembly is not as intuitive to me partly due to the extensive reliance on structs, with its complexities overflowing into the calling convention, and this part aims to demystify that a little.
Now we go to the next node. The other node from the jnz branch is irrelevant as it is just error handling.
call cs:_ZN3std2io5stdio5stdin17h821c04443a399516E_ptr ; std::io::stdio::stdin::h821c04443a399516 ...
mov [rsp+308h+var_2C8], rax
lea rdi, [rsp+308h+var_2B8]
lea r14, [rsp+308h+var_2C8]
lea rdx, [rsp+308h+PTR_2E0]
mov rsi, r14
call cs:_ZN3std2io5stdio5Stdin9read_line17h75874c24c55eccd0E_ptr ; std::io::stdio::Stdin::read_line::h75874c24c55eccd0 ...
cmp qword ptr [rsp+308h+var_2B8], 0
jnz loc_9824From the function names we know that
io::stdin().read_line(&mut input).unwrap()was called. But the arguments and return values seem all over the place. For curiosity sake let’s crack this open in GDB:
gef➤ b *0x55555555ced8
Breakpoint 2 at 0x55555555ced8
gef➤ c
Continuing.
>
Breakpoint 2, 0x000055555555ced8 in cooking_mama::main ()
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555cecb <cooking_mama::main+587> lea r14, [rsp+0x40]
0x55555555ced0 <cooking_mama::main+592> lea rdx, [rsp+0x28]
0x55555555ced5 <cooking_mama::main+597> mov rsi, r14
●→ 0x55555555ced8 <cooking_mama::main+600> call QWORD PTR [rip+0x540e2] # 0x5555555b0fc0
0x55555555cede <cooking_mama::main+606> cmp QWORD PTR [rsp+0x50], 0x0
0x55555555cee4 <cooking_mama::main+612> jne 0x55555555d824 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2980>
0x55555555ceea <cooking_mama::main+618> mov rax, QWORD PTR [rsp+0x38]
0x55555555ceef <cooking_mama::main+623> test rax, rax
0x55555555cef2 <cooking_mama::main+626> je 0x55555555d0bd <_ZN12cooking_mama4main17h61864c778b35fb2fE+1085>
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── arguments (guessed) ────
*0x5555555b0fc0 (
$rdi = 0x007fffffffdb70 → 0x005555555ae1f8 → 0x0055555559d09b → and BYTE PTR ds:[rbx+0x72], dh,
$rsi = 0x007fffffffdb60 → 0x005555555b1040 → <std::io::stdio::stdin::INSTANCE+0> add BYTE PTR [rax], al,
$rdx = 0x007fffffffdb48 → 0x0000000000000001,
$rcx = 0x005555555b2ba0 → 0x0000000000000000
)
...
gef➤ x/4gx 0x007fffffffdb48
0x7fffffffdb48: 0x0000000000000001 0x0000000000000000
0x7fffffffdb58: 0x0000000000000000 0x00005555555b1040The breakpoint is set right before read_line. Our landmark being rsi which points to the stdin instance, and matching against the Rust documentation
pub fn read_line(&self, buf: &mut String) -> Result<usize>it seems that the arguments start at rsi with rdx being the input buffer. For now it seems to be unused, but upon stepping over:
gef➤ ni
grey{abcd}
...
gef➤ x/4gx 0x007fffffffdb70
0x7fffffffdb70: 0x0000000000000000 0x000000000000000b
0x7fffffffdb80: 0x000055555559d070 0x0000000000000000
gef➤ x/4gx 0x007fffffffdb48
0x7fffffffdb48: 0x00005555555b4bb0 0x000000000000000b
0x7fffffffdb58: 0x000000000000000b 0x00005555555b1040
gef➤ x/8gx 0x00005555555b4bb0-0x10
0x5555555b4ba0: 0x0000000000000000 0x0000000000000021
0x5555555b4bb0: 0x6362617b79657267 0x00000000000a7d64
0x5555555b4bc0: 0x0000000000000000 0x000000000001e441
0x5555555b4bd0: 0x0000000000000000 0x0000000000000000
gef➤ x/s 0x00005555555b4bb0
0x5555555b4bb0: "grey{abcd}\n"Everything seems to line up:
rdiis used to store the return value as, at least in this case,Resultcannot fit into a single register.- Again, the actual arguments start at
rsi.rdxin this case is indeed our input buffer, a pretty commonptr-cap-lenimplementation of RustStrings.
Again the unwrap branch can be skipped over.
Part III: Parsing
mov rax, qword ptr [rsp+308h+var_2D8+8]
test rax, rax
jz loc_90BDAs the String struct is located in rsp+(0x308-0x2C8), rax retrieves the length of our input. If zero, we jump straight to the checking stage, skipping over both the parsing and loading stages directly. But obviously our input cannot be empty, so we have no choice but to take a quick look at what this group of nodes does.
mov rcx, [rsp+308h+PTR_2E0]
add rax, rcx
jmp short loc_8F1Brcx and rax now point to the start and end of the byte string respectively.
After the above node we seem to enter a loop (see the rightmost red arrow in the parsing group in the image near the start), do keep a mental note of this.
loc_8F1B:
movzx edx, byte ptr [rcx]
test dl, dl
js short loc_8F40
; ...
loc_8F40:
mov esi, edx
and esi, 1Fh
movzx r8d, byte ptr [rcx+1]
and r8d, 3Fh
cmp dl, 0DFh
jbe short loc_8F94
movzx edi, byte ptr [rcx+2]
shl r8d, 6
and edi, 3Fh
or edi, r8d
cmp dl, 0F0h
jb short loc_8FAE
movzx edx, byte ptr [rcx+3]
and esi, 7
shl esi, 12h
shl edi, 6
and edx, 3Fh
or edx, edi
or edx, esi
cmp edx, 110000h
jz loc_90BDFirstly we shall take care of the branches. It might seem complicated with all the registers shuffling around and stuff, but if we stare at it closely we see that the conditions only concern byte ptr [rcx] with cutoffs at 0x80, 0xE0 and 0xF0. At the very end if all branches fail it seems to short-circuit straight to the checking stage (like when the length is zero).
Now we take a look at how the different branches are handled:
inc rcx
lea esi, [rdx-31h]
cmp esi, 9
jnb short loc_8F12
jmp loc_8FD0loc_8F94:
add rcx, 2
shl esi, 6
or esi, r8d
mov edx, esi
lea esi, [rdx-31h]
cmp esi, 9
jnb loc_8F12
jmp short loc_8FD0loc_8FAE:
add rcx, 3
shl esi, 0Ch
or edi, esi
mov edx, edi
lea esi, [rdx-31h]
cmp esi, 9
jnb loc_8F12
db 66h, 66h, 2Eh
nop word ptr [rax+rax+00000000h]
; 8FD0add rcx, 4
lea esi, [rdx-31h]
cmp esi, 9
jnb short loc_8F12
jmp short loc_8FD0Fortunately for us they all jmp to the same two nodes at the end (aside from the weird disassembly at the end of the third node).
loc_8F12:
cmp rcx, rax
jz loc_90BDwhich marks the end of the loop, subsequently entering the checking stage. If not taken, we go all the way to the top of the loop. (If taken, the program short-circuits as mentioned above.)
And if you were observant enough you may have noticed that rax remained unchanged throughout the whole operation. Now it is pretty clear that here it functions as an anchor to mark the end of the string so that we know where to stop and break out of the loop. rcx meanwhile acts as a pointer iterating over the bytes in the string and marking out the bytes “consumed” by the loop.
loc_8FD0:
add edx, 0FFFFFFD0h
xor esi, esiwhich marks the end of the parsing stage, subsequently entering the loading stage. The add instruction is practically equivalent to subtracting edx by 0x30.
So what is edx? Or more generally, which registers have been modified from the branches above?
We take the branch that traverses the most checks, which we get by combining the whole of this block and this branch.
This would require byte ptr [rcx] to have its first 4 MSBs all set to true. Crucially, after the end of the whole chunk, we end up with
MEM = b'...'
edx = (
(MEM[rcx+0] & 0b00000111) << 18 # from sil
| (MEM[rcx+1] & 0b00111111) << 12 # from r8d
| (MEM[rcx+2] & 0b00111111) << 6 # from dil
| (MEM[rcx+3] & 0b00111111) # from dl
)The other branches are also pretty similar, differing just by the number of bytes consumed. We can work just with this information, but for a more intuitive understanding this is actually just UTF-8. (I was able to skip this part entirely once I saw that the format is practically identical to another chal that I solved like a week prior :P)
Then I recalled, yeah, Rust Strings are UTF-8-compliant u8 vectors which can be iterated to spit out chars (Unicode codepoints). So this is probably what’s going on here. I guess this is good closure after solving two chals related to the same concept.
Part IV: Loading
Within the loop described in the part above, after extracting the current iteration of char from the String, we find ourselves in another loop.
Fortunately the structure of the loop is, again, very simple. We start from the head:
loc_8FD5:
cmp dword ptr [rsp+rsi+308h+var_168], 0
jz loc_8F02
; ...
loc_8F02:
add rsi, rsp
add rsi, 1A0h
nop dword ptr [rax+00h]
loc_8F10:
mov [rsi], edx
; 8F12The short cmp instruction simply checks if the dword slot at that memory region is “filled” or “marked”.
8F12 here breaks out of the inner loop, but also recall that it marks the end of the outer loop (here).
Then we realise, the branches within the loop are all practically identical. This is the next branch if jz loc_8F02 is not taken:
cmp dword ptr [rsp+rsi+308h+var_168+4], 0
jz short loc_9045
; ...
loc_9045:
add rsi, rsp
add rsi, 1A4h
jmp loc_8F10And if jz loc_9045 is not taken:
cmp dword ptr [rsp+rsi+308h+var_168+8], 0
jz short loc_9054
; ...
loc_9054:
add rsi, rsp
add rsi, 1A8h
jmp loc_8F10And on and on. At the end if none of the jzs are taken:
; loc_9033:
add rsi, 24h ; '$'
cmp rsi, 144h
jnz short loc_8FD5
jmp loc_8F12If jnz is taken, we return to the start of this current loop. If not, we jmp to 8F12, breaking out of the loop just like above.
In simpler code:
# python automatically iterates over unicode chars
ARR = [] # of dwords, starting at rsp+(0x308-0x168)
for c in input(): # 8F12
cur = ord(c)
if not (0 <= cur-0x31 < 9):
continue
cur -= 0x30 # 8FD0
idx = 0
while idx != 0x144: # 9033
if ARR[(idx+0x0)//4] == 0: # 8FD5
idx += 0x0
elif ARR[(idx+0x4)//4] == 0:
idx += 0x4
elif ARR[(idx+0x8)//4] == 0:
idx += 0x8
# ...
elif ARR[(idx+0x20)//4] == 0:
idx += 0x20
else:
# 0x24 * 9 = 0x144
idx += 0x24 # 9033
continue
idx //= 4 # to account for dword size
break
else: # 9033
continue
ARR[idx] = cur # 8F10Note that 0x144 = 0x4 * 9 * 9. We are seeing a lot of 9s here and there…
Either way we can further abstract the code:
# pre-populated with numbers above
ARR = [0 for _ in range(81)]
for c in input():
if (cur := ord(c)-0x30) not in range(1, 10):
continue
try:
ARR[ARR.index(0)] = cur
except ValueError:
continue # break works here tooBy “numbers above” I mean these. In fact if we represent them as a 9x9 matrix as it seems to be intended to:
DATA = [0, 5, 0, 0, 0, 0, 0, 8, 9, 7, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 9, 7, 0, 0, 0, 0, 3, 6, 2, 0, 0, 2, 0, 4, 0, 0, 0, 0, 0, 5, 6, 4, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 8, 9, 0, 0, 0, 0, 0, 0, 8, 0, 6, 0, 5, 3, 0]
assert len(DATA) == 81
print('\n'.join(
' '.join(map(str, DATA[i*9:(i+1)*9]))
for i in range(len(DATA)//9)
).replace('0', '_'))_ 5 _ _ _ _ _ 8 9
7 _ _ 6 _ _ _ _ _
_ _ _ _ _ 8 4 _ _
_ _ _ _ _ 1 _ 9 7
_ _ _ _ 3 6 2 _ _
2 _ 4 _ _ _ _ _ 5
6 4 2 1 _ _ _ _ _
_ _ 1 8 9 _ _ _ _
_ _ 8 _ 6 _ 5 3 _I think at this point it is quite obvious what we are looking at. But in the spirit of rev let’s just take a look at the checks to be doubly sure.
Part V: Checking
Initially a mess, this part becomes beautifully straightforward once the two “sink nodes” are hidden: the bounds checking (error; 97E8) and the failure route (fail; 9771). We will soon see that there is just one simple loop involved.
loc_90BD:
xorps xmm1, xmm1
movaps [rsp+308h+var_2A8], xmm1
movaps [rsp+308h+var_2B8], xmm1
mov dword ptr [rsp+308h+var_298], 0
mov esi, dword ptr [rsp+308h+var_168]
test esi, esi
jz near ptr unk_9771The region in the stack from rsp+0x50 to rsp+0x74 is cleared, with a size equivalent to 9 dwords.
Then again, our dear sudoku input region (rsp+(0x308-0x168)) is referenced again, and again checking whether the dword slot is filled. Why this check is done at the very beginning even before the loop is beyond me, possibly just compiler shenanigans?
lea rax, [rsp+308h+var_48]
lea rcx, [rsp+308h+var_144]
xor r9d, r9d
lea rdx, off_5A238
movdqa xmm0, cs:xmmword_49060
mov r10, rcx
mov edi, esi
xor r8d, r8dThe node right before the start of the loop. rax and rdx don’t seem very important to me, r8 and r9 are cleared (at least where dwords are concerned), r10 is set to rsp+(0x308-0x168)+0x24, and xmm0 is a concatenation of 4 0x00000001s.
loc_910B:
movsxd rdi, edi
cmp edi, 9
ja near ptr unk_97E8Bounds check ensuring that edi <= 9. Sort of a Rust sanity check because only 1 <= x <= 9 can enter our input memory. edi == 0 can be seen being taken care of separately, but jumping to(wards) fail instead of error.
mov [rsp+rdi*4+308h+var_2BC], 1
movsxd rdi, dword ptr [r10-20h]
test rdi, rdi
jz loc_9260
cmp edi, 9
ja near ptr unk_97E8Similar code is repeated 7 more times differing only in the -20h part (the 9th iteration is split between the start and the end of the loop). They all commonly jz to 9260, essentially breaking out of the loop, which is:
loc_9260:
test r8b, 1
jz near ptr unk_9771Here we clearly see that r8 is used as a check flag. If all tests pass and the program did not prematurely break out of the loop, the LSB in r8 will be set and we will not jump to fail.
So we first figure out what the 9 iterations of code do. Stripping away the checks we are essentially left with:
movsxd rdi, dword ptr [r10-20h]
mov [rsp+rdi*4+308h+var_2BC], 1If you recall that rsp+(0x308-0x2BC)+0x4 is the start of the 9 dwords cleared out before entering the loop, we have our answer! Each of the 9 dwords act as mini-flags that check if their corresponding index is present. In more readable code,
MARKED = [0 for _ in range(9)]
for num in ARR[:9]:
MARKED[num] = 1Then at the end of the iteration the mini flags are checked against.
mov [rsp+rdi*4+308h+var_2BC], 1
movdqa xmm2, [rsp+308h+var_2A8]
pcmpeqd xmm2, xmm0
movdqa xmm3, [rsp+308h+var_2B8]
pcmpeqd xmm3, xmm0
pand xmm3, xmm2
movmskps edi, xmm3
xor edi, 0Fh
jnz short loc_9260We have to deal with SIMD instructions which are annoying, but they can become slightly more intuitive if we view the xmm registers as arrays of 4 dwords.
import numpy as np
xmm0 = np.array([0x1]*4, dtype=np.int32) # (defined earlier)
xmm2 = np.array(MARKED[4:8], dtype=np.int32) # movdqa
xmm2 = (xmm2 == xmm0).astype(np.int32) * -1 # pcmpeqd
xmm3 = np.array(MARKED[:4], dtype=np.int32) # movdqa
xmm3 = (xmm3 == xmm0).astype(np.int32) * -1 # pcmpeqd
xmm3 &= xmm2 # pand; -1 is 0xffffffff
edi = np.packbits(xmm3 < 0, bitorder='little')[0] # movmskps
assert edi ^ 0xf == 0x0Or even more abstract:
assert all(x == 1 for x in MARKED[:8])The last element in the 9-element MARKED array is checked on its own as it can’t cleanly fit into the 2 xmm registers (no point using SIMD anyway).
cmp dword ptr [rsp+308h+var_298], 1
jnz short loc_9260(A reminder that 9260 breaks out of the loop, which we don’t want happen so early.)
movaps [rsp+308h+var_2A8], xmm1
movaps [rsp+308h+var_2B8], xmm1
mov dword ptr [rsp+308h+var_298], 0
cmp r9, 8
jz short loc_926A
setnb r8b
mov edi, [r10]
add r10, 24h ; '$'
inc r9
test edi, edi
jnz loc_910BThen here we realise the r8 flag isn’t even necessary at all: Once the loop counter (r9) hits its target (from 0 to 8, iterating 9 times total) we automatically jump to the start of the second check, essentially passing the first check automatically.
Notice the r10 increase over there? We see that the 81-dword array is indeed treated as 9 rows (0x144 // 0x24 = 0x9) of 9 dwords (0x9 * 0x4 = 0x24). All in all, this check is functionally equivalent to:
for i in range(9):
MARKED = [0 for _ in range(9)]
for j in range(9):
MARKED[ARR[i*9+j]] = 1
assert all(x == 1 for x in MARKED)Or,
assert all(
set(ARR[i*9:(i+1)*9]) == set(range(1, 10))
for i in range(9)
)Drawing comparisons to sudoku, it is abundantly clear that this checks the uniqueness requirement for each row. It is pretty easy to deduce (and verify) that the subsequent two checks check each column and grid as well.
And with that, I believe there is sufficient evidence to deduce that we are looking at a sudoku puzzle. Plugging the above puzzle (scroll up a bit from Part V) into any online solver we get
463127894512312397563654288975141789365397853764297241$ ./cooking_mama
⠀⠀⢀⣴⣿⣿⣷⣦⣌⠛⢦⡀⠀⠈⠓⢦⣀⡀⠀⣸⣿⣿⣿⡀⠀
⠀⠀⡾⠋⠉⢿⣿⣿⡿⠟⠦⣝⡲⣄⣀⠀⠈⠉⠉⣽⡿⢿⣿⡇⠀
⠀⠀⣷⠀⣠⣿⡿⠋⠀⠀⣶⢤⣙⠳⢭⣙⠲⠤⠴⠋⠑⠀⠁⣧⠀
⠀⠀⢸⡼⠛⠛⠀⠀⠀⣼⠉⢿⣿⣧⣶⡿⠛⠶⢤⣀⠀⠀⠀⣻
⠀⠀⢨⡇⠀⠀⠀⠀⠀⠈⠉⠉⢸⡟⣺⠃⠀⠀⠀⠈⠙⠲⠶⠋⠀
⠀⠀⣸⠁⠀⠀⠀⠀⠀⢀⡀⠀⢸⡷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣰⠃⠀⠀⠀⠠⣄⡀⠀⠉⣳⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀WHO LET HIM COOK
⣞⠁⠀⠲⣄⠀⠀⠀⠉⠉⡷⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣌⠳⣤⡀⠈⠓⠦⢤⡴⠚⠁⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⠀⠀⠀⠀
⣿⣷⣤⡿⢷⠀⣀⡴⣷⠒⠒⢒⣶⢤⠞⠉⠙⢻⣿⣷⣄⠀⠀⠀⠀
⠙⠻⣿⣷⠈⠛⠙⡇⣿⠀⠀⢯⣽⢿⠀⠀⠀⣴⠚⠉⠛⠀⠀⠀⠀
⣶⣆⠀⢹⣠⠶⣄⡇⢻⠛⠓⠒⠚⠋⠙⠓⠲⠮⠿⠆⠀⠀⠀⠀⠀
⣿⣿⠀⢸⠙⠒⢃⣇⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
> 463127894512312397563654288975141789365397853764297241
⢻⣿⡗⢶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣄
⠀⢻⣇⠀⠈⠙⠳⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⠛⠋⣹⣿⡿
⠀⠀⠹⣆⠀⠀⠀⠀⠙⢷⣄⣀⣀⣀⣤⣤⣤⣄⣀⣴⠞⠋⠉⠀⠀⠀⢀⣿⡟⠁
⠀⠀⠀⠙⢷⡀⠀⠀⠀⠀⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡾⠋⠀⠀
⠀⠀⠀⠀⠈⠻⡶⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣠⡾⠋⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣼⠃⠀⢠⠒⣆⠀⠀⠀⠀⠀⠀⢠⢲⣄⠀⠀⠀⢻⣆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢰⡏⠀⠀⠈⠛⠋⠀⢀⣀⡀⠀⠀⠘⠛⠃⠀⠀⠀⠈⣿⡀⠀⠀⠀⠀
⠀⠀⠀⠀⣾⡟⠛⢳⠀⠀⠀⠀⠀⣉⣀⠀⠀⠀⠀⣰⢛⠙⣶⠀⢹⣇⠀⠀⠀⠀ flag is grey{your_input_here} :)
⠀⠀⠀⠀⢿⡗⠛⠋⠀⠀⠀⠀⣾⠋⠀⢱⠀⠀⠀⠘⠲⠗⠋⠀⠈⣿⠀⠀⠀⠀
⠀⠀⠀⠀⠘⢷⡀⠀⠀⠀⠀⠀⠈⠓⠒⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡇⠀⠀⠀
⠀⠀⠀⠀⠀⠈⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣧⠀⠀grey{463127894512312397563654288975141789365397853764297241}Appendix: Dynamic Analysis
To be completely honest I would be lying if I claimed I did not rely on actually running the binary to understand like half of the disassembly because I got tired of reading it.
After figuring out the input format (which I believe is still pretty straightforward in Part III just by looking at it) we can just plug in some numbers and see what happens.
Part IV
First we have the mess that starts with this (and many similar copies of itself):
cmp dword ptr [rsp+rsi+308h+var_168], 0Knowing rsi is 0x0 at the start (literally right after the xor instruction), we can refresh ourselves on how the memory region we are dealing with looks like at the very beginning of this stage:
$ gdb cooking_mama
...
gef➤ b *0x55555555cfd5
Breakpoint 1 at 0x55555555cfd5
gef➤ r
...
⠀⠀⢀⣴⣿⣿⣷⣦⣌⠛⢦⡀⠀⠈⠓⢦⣀⡀⠀⣸⣿⣿⣿⡀⠀
⠀⠀⡾⠋⠉⢿⣿⣿⡿⠟⠦⣝⡲⣄⣀⠀⠈⠉⠉⣽⡿⢿⣿⡇⠀
⠀⠀⣷⠀⣠⣿⡿⠋⠀⠀⣶⢤⣙⠳⢭⣙⠲⠤⠴⠋⠑⠀⠁⣧⠀
⠀⠀⢸⡼⠛⠛⠀⠀⠀⣼⠉⢿⣿⣧⣶⡿⠛⠶⢤⣀⠀⠀⠀⣻
⠀⠀⢨⡇⠀⠀⠀⠀⠀⠈⠉⠉⢸⡟⣺⠃⠀⠀⠀⠈⠙⠲⠶⠋⠀
⠀⠀⣸⠁⠀⠀⠀⠀⠀⢀⡀⠀⢸⡷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣰⠃⠀⠀⠀⠠⣄⡀⠀⠉⣳⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀WHO LET HIM COOK
⣞⠁⠀⠲⣄⠀⠀⠀⠉⠉⡷⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣌⠳⣤⡀⠈⠓⠦⢤⡴⠚⠁⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⠀⠀⠀⠀
⣿⣷⣤⡿⢷⠀⣀⡴⣷⠒⠒⢒⣶⢤⠞⠉⠙⢻⣿⣷⣄⠀⠀⠀⠀
⠙⠻⣿⣷⠈⠛⠙⡇⣿⠀⠀⢯⣽⢿⠀⠀⠀⣴⠚⠉⠛⠀⠀⠀⠀
⣶⣆⠀⢹⣠⠶⣄⡇⢻⠛⠓⠒⠚⠋⠙⠓⠲⠮⠿⠆⠀⠀⠀⠀⠀
⣿⣿⠀⢸⠙⠒⢃⣇⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
> 1
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555cfc5 <cooking_mama::main+837> data16 nop WORD PTR cs:[rax+rax*1+0x0]
0x55555555cfd0 <cooking_mama::main+848> add edx, 0xffffffd0
0x55555555cfd3 <cooking_mama::main+851> xor esi, esi
●→ 0x55555555cfd5 <cooking_mama::main+853> cmp DWORD PTR [rsp+rsi*1+0x1a0], 0x0
0x55555555cfdd <cooking_mama::main+861> je 0x55555555cf02 <_ZN12cooking_mama4main17h61864c778b35fb2fE+642>
0x55555555cfe3 <cooking_mama::main+867> cmp DWORD PTR [rsp+rsi*1+0x1a4], 0x0
0x55555555cfeb <cooking_mama::main+875> je 0x55555555d045 <_ZN12cooking_mama4main17h61864c778b35fb2fE+965>
0x55555555cfed <cooking_mama::main+877> cmp DWORD PTR [rsp+rsi*1+0x1a8], 0x0
0x55555555cff5 <cooking_mama::main+885> je 0x55555555d054 <_ZN12cooking_mama4main17h61864c778b35fb2fE+980>
...
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/16gx $rsp+0x1a0
0x7fffffffdcd0: 0x0000000500000000 0x0000000000000000
0x7fffffffdce0: 0x0000000000000000 0x0000000800000000
0x7fffffffdcf0: 0x0000000700000009 0x0000000000000000
0x7fffffffdd00: 0x0000000000000006 0x0000000000000000
0x7fffffffdd10: 0x0000000000000000 0x0000000000000000
0x7fffffffdd20: 0x0000000000000000 0x0000000800000000
0x7fffffffdd30: 0x0000000000000004 0x0000000000000000
0x7fffffffdd40: 0x0000000000000000 0x0000000000000000We are reminded that the dword locations are already semi-prefilled (all the way back in Part II).
Stepping over a few instructions we eventually see our input 1 getting filled into the first dword slot, matching up with both what we already sort of expect and what we analysed earlier.
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555cf05 <cooking_mama::main+645> add rsi, 0x1a0
0x55555555cf0c <cooking_mama::main+652> nop DWORD PTR [rax+0x0]
0x55555555cf10 <cooking_mama::main+656> mov DWORD PTR [rsi], edx
→ 0x55555555cf12 <cooking_mama::main+658> cmp rcx, rax
0x55555555cf15 <cooking_mama::main+661> je 0x55555555d0bd <_ZN12cooking_mama4main17h61864c778b35fb2fE+1085>
0x55555555cf1b <cooking_mama::main+667> movzx edx, BYTE PTR [rcx]
0x55555555cf1e <cooking_mama::main+670> test dl, dl
0x55555555cf20 <cooking_mama::main+672> js 0x55555555cf40 <_ZN12cooking_mama4main17h61864c778b35fb2fE+704>
0x55555555cf22 <cooking_mama::main+674> inc rcx
...
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/16gx $rsp+0x1a0
0x7fffffffdcd0: 0x0000000500000001 0x0000000000000000
0x7fffffffdce0: 0x0000000000000000 0x0000000800000000
0x7fffffffdcf0: 0x0000000700000009 0x0000000000000000
0x7fffffffdd00: 0x0000000000000006 0x0000000000000000
0x7fffffffdd10: 0x0000000000000000 0x0000000000000000
0x7fffffffdd20: 0x0000000000000000 0x0000000800000000
0x7fffffffdd30: 0x0000000000000004 0x0000000000000000
0x7fffffffdd40: 0x0000000000000000 0x0000000000000000Now let’s see what happens when we add more numbers. In this case having 7 numbers will already “overflow” the branches.
gef➤ r
...
⠀⠀⢀⣴⣿⣿⣷⣦⣌⠛⢦⡀⠀⠈⠓⢦⣀⡀⠀⣸⣿⣿⣿⡀⠀
⠀⠀⡾⠋⠉⢿⣿⣿⡿⠟⠦⣝⡲⣄⣀⠀⠈⠉⠉⣽⡿⢿⣿⡇⠀
⠀⠀⣷⠀⣠⣿⡿⠋⠀⠀⣶⢤⣙⠳⢭⣙⠲⠤⠴⠋⠑⠀⠁⣧⠀
⠀⠀⢸⡼⠛⠛⠀⠀⠀⣼⠉⢿⣿⣧⣶⡿⠛⠶⢤⣀⠀⠀⠀⣻
⠀⠀⢨⡇⠀⠀⠀⠀⠀⠈⠉⠉⢸⡟⣺⠃⠀⠀⠀⠈⠙⠲⠶⠋⠀
⠀⠀⣸⠁⠀⠀⠀⠀⠀⢀⡀⠀⢸⡷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣰⠃⠀⠀⠀⠠⣄⡀⠀⠉⣳⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀WHO LET HIM COOK
⣞⠁⠀⠲⣄⠀⠀⠀⠉⠉⡷⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣌⠳⣤⡀⠈⠓⠦⢤⡴⠚⠁⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⠀⠀⠀⠀
⣿⣷⣤⡿⢷⠀⣀⡴⣷⠒⠒⢒⣶⢤⠞⠉⠙⢻⣿⣷⣄⠀⠀⠀⠀
⠙⠻⣿⣷⠈⠛⠙⡇⣿⠀⠀⢯⣽⢿⠀⠀⠀⣴⠚⠉⠛⠀⠀⠀⠀
⣶⣆⠀⢹⣠⠶⣄⡇⢻⠛⠓⠒⠚⠋⠙⠓⠲⠮⠿⠆⠀⠀⠀⠀⠀
⣿⣿⠀⢸⠙⠒⢃⣇⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
> 1111111
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ c
Continuing.
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555cfc5 <cooking_mama::main+837> data16 nop WORD PTR cs:[rax+rax*1+0x0]
0x55555555cfd0 <cooking_mama::main+848> add edx, 0xffffffd0
0x55555555cfd3 <cooking_mama::main+851> xor esi, esi
●→ 0x55555555cfd5 <cooking_mama::main+853> cmp DWORD PTR [rsp+rsi*1+0x1a0], 0x0
0x55555555cfdd <cooking_mama::main+861> je 0x55555555cf02 <_ZN12cooking_mama4main17h61864c778b35fb2fE+642>
0x55555555cfe3 <cooking_mama::main+867> cmp DWORD PTR [rsp+rsi*1+0x1a4], 0x0
0x55555555cfeb <cooking_mama::main+875> je 0x55555555d045 <_ZN12cooking_mama4main17h61864c778b35fb2fE+965>
0x55555555cfed <cooking_mama::main+877> cmp DWORD PTR [rsp+rsi*1+0x1a8], 0x0
0x55555555cff5 <cooking_mama::main+885> je 0x55555555d054 <_ZN12cooking_mama4main17h61864c778b35fb2fE+980>
...
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/16gx $rsp+0x1a0
0x7fffffffdcd0: 0x0000000500000001 0x0000000100000001
0x7fffffffdce0: 0x0000000100000001 0x0000000800000001
0x7fffffffdcf0: 0x0000000700000009 0x0000000000000000
0x7fffffffdd00: 0x0000000000000006 0x0000000000000000
0x7fffffffdd10: 0x0000000000000000 0x0000000000000000
0x7fffffffdd20: 0x0000000000000000 0x0000000800000000
0x7fffffffdd30: 0x0000000000000004 0x0000000000000000
0x7fffffffdd40: 0x0000000000000000 0x0000000000000000At this point 6 out of 7 1s have been filled in and in the behaviour we expect. Now we are about to fill the 7th 1, being able to see in action both the “spot is taken” procedure and the overflow procedure.
(Stepping through the program with ni)
→ 0x55555555cfdd <cooking_mama::main+861> je 0x55555555cf02 <_ZN12cooking_mama4main17h61864c778b35fb2fE+642> NOT taken [Reason: !(Z)]
→ 0x55555555cfe3 <cooking_mama::main+867> cmp DWORD PTR [rsp+rsi*1+0x1a4], 0x0
→ 0x55555555cfeb <cooking_mama::main+875> je 0x55555555d045 <_ZN12cooking_mama4main17h61864c778b35fb2fE+965> NOT taken [Reason: !(Z)]
→ 0x55555555cfed <cooking_mama::main+877> cmp DWORD PTR [rsp+rsi*1+0x1a8], 0x0
→ 0x55555555cff5 <cooking_mama::main+885> je 0x55555555d054 <_ZN12cooking_mama4main17h61864c778b35fb2fE+980> NOT taken [Reason: !(Z)]
→ 0x55555555cff7 <cooking_mama::main+887> cmp DWORD PTR [rsp+rsi*1+0x1ac], 0x0
→ 0x55555555cfff <cooking_mama::main+895> je 0x55555555d063 <_ZN12cooking_mama4main17h61864c778b35fb2fE+995> NOT taken [Reason: !(Z)]
→ 0x55555555d001 <cooking_mama::main+897> cmp DWORD PTR [rsp+rsi*1+0x1b0], 0x0
→ 0x55555555d009 <cooking_mama::main+905> je 0x55555555d072 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1010> NOT taken [Reason: !(Z)]
→ 0x55555555d00b <cooking_mama::main+907> cmp DWORD PTR [rsp+rsi*1+0x1b4], 0x0
→ 0x55555555d013 <cooking_mama::main+915> je 0x55555555d081 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1025> NOT taken [Reason: !(Z)]
→ 0x55555555d015 <cooking_mama::main+917> cmp DWORD PTR [rsp+rsi*1+0x1b8], 0x0
→ 0x55555555d01d <cooking_mama::main+925> je 0x55555555d090 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1040> NOT taken [Reason: !(Z)]
→ 0x55555555d01f <cooking_mama::main+927> cmp DWORD PTR [rsp+rsi*1+0x1bc], 0x0
→ 0x55555555d027 <cooking_mama::main+935> je 0x55555555d09f <_ZN12cooking_mama4main17h61864c778b35fb2fE+1055> NOT taken [Reason: !(Z)]
→ 0x55555555d029 <cooking_mama::main+937> cmp DWORD PTR [rsp+rsi*1+0x1c0], 0x0
→ 0x55555555d031 <cooking_mama::main+945> je 0x55555555d0ae <_ZN12cooking_mama4main17h61864c778b35fb2fE+1070> NOT taken [Reason: !(Z)]We see that none of the branches are taken as all 9 dword slots are filled.
→ 0x55555555d033 <cooking_mama::main+947> add rsi, 0x24
→ 0x55555555d037 <cooking_mama::main+951> cmp rsi, 0x144
→ 0x55555555d03e <cooking_mama::main+958> jne 0x55555555cfd5 <_ZN12cooking_mama4main17h61864c778b35fb2fE+853> TAKEN [Reason: !Z]For the overflow procedure, our memory pseudo-pointer is incremented by 9 dwords, and since we have not reached the end of our loop we continue looking for slots from the beginning again.
●→ 0x55555555cfd5 <cooking_mama::main+853> cmp DWORD PTR [rsp+rsi*1+0x1a0], 0x0
→ 0x55555555cfdd <cooking_mama::main+861> je 0x55555555cf02 <_ZN12cooking_mama4main17h61864c778b35fb2fE+642> NOT taken [Reason: !(Z)]
→ 0x55555555cfe3 <cooking_mama::main+867> cmp DWORD PTR [rsp+rsi*1+0x1a4], 0x0
→ 0x55555555cfeb <cooking_mama::main+875> je 0x55555555d045 <_ZN12cooking_mama4main17h61864c778b35fb2fE+965> TAKEN [Reason: Z]
↳ 0x55555555d045 <cooking_mama::main+965> add rsi, rsp
0x55555555d048 <cooking_mama::main+968> add rsi, 0x1a4
0x55555555d04f <cooking_mama::main+975> jmp 0x55555555cf10 <_ZN12cooking_mama4main17h61864c778b35fb2fE+656>Finally we found our slot. Our actualy pointer becomes rsp+0x24+0x1a4, which is (rsp+0x1a0)+0x4*(9+1) (i.e. ARR[10]).
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555cf05 <cooking_mama::main+645> add rsi, 0x1a0
0x55555555cf0c <cooking_mama::main+652> nop DWORD PTR [rax+0x0]
0x55555555cf10 <cooking_mama::main+656> mov DWORD PTR [rsi], edx
→ 0x55555555cf12 <cooking_mama::main+658> cmp rcx, rax
0x55555555cf15 <cooking_mama::main+661> je 0x55555555d0bd <_ZN12cooking_mama4main17h61864c778b35fb2fE+1085>
0x55555555cf1b <cooking_mama::main+667> movzx edx, BYTE PTR [rcx]
0x55555555cf1e <cooking_mama::main+670> test dl, dl
0x55555555cf20 <cooking_mama::main+672> js 0x55555555cf40 <_ZN12cooking_mama4main17h61864c778b35fb2fE+704>
0x55555555cf22 <cooking_mama::main+674> inc rcx
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/16gx $rsp+0x1a0
0x7fffffffdcd0: 0x0000000500000001 0x0000000100000001
0x7fffffffdce0: 0x0000000100000001 0x0000000800000001
0x7fffffffdcf0: 0x0000000700000009 0x0000000000000001
0x7fffffffdd00: 0x0000000000000006 0x0000000000000000
0x7fffffffdd10: 0x0000000000000000 0x0000000000000000
0x7fffffffdd20: 0x0000000000000000 0x0000000800000000
0x7fffffffdd30: 0x0000000000000004 0x0000000000000000
0x7fffffffdd40: 0x0000000000000000 0x0000000000000000Part V
Within the loop described above, the first real memory access is from the instruction
mov [rsp+rdi*4+308h+var_2BC], 1Simple register / variable tracing leads us to rdi -> rsi -> dword ptr [rsp+308h+var_168], our ARR[0]. Verifying in the binary,
gef➤ b *0x55555555d0d2
Breakpoint 2 at 0x55555555d0d2
gef➤ c
Continuing.
Breakpoint 2, 0x000055555555d0d2 in cooking_mama::main ()
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555d0c0 <cooking_mama::main+1088> movaps XMMWORD PTR [rsp+0x60], xmm1
0x55555555d0c5 <cooking_mama::main+1093> movaps XMMWORD PTR [rsp+0x50], xmm1
0x55555555d0ca <cooking_mama::main+1098> mov DWORD PTR [rsp+0x70], 0x0
●→ 0x55555555d0d2 <cooking_mama::main+1106> mov esi, DWORD PTR [rsp+0x1a0]
0x55555555d0d9 <cooking_mama::main+1113> test esi, esi
0x55555555d0db <cooking_mama::main+1115> je 0x55555555d771 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2801>
0x55555555d0e1 <cooking_mama::main+1121> lea rax, [rsp+0x2c0]
0x55555555d0e9 <cooking_mama::main+1129> lea rcx, [rsp+0x1c4]
0x55555555d0f1 <cooking_mama::main+1137> xor r9d, r9d
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/wx $rsp+0x1a0
0x7fffffffdcd0: 0x00000001
gef➤ b *0x55555555d117
Breakpoint 3 at 0x55555555d117
gef➤ c
Continuing.
Breakpoint 3, 0x000055555555d117 in cooking_mama::main ()
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555d10b <cooking_mama::main+1163> movsxd rdi, edi
0x55555555d10e <cooking_mama::main+1166> cmp edi, 0x9
0x55555555d111 <cooking_mama::main+1169> ja 0x55555555d7e8 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2920>
●→ 0x55555555d117 <cooking_mama::main+1175> mov DWORD PTR [rsp+rdi*4+0x4c], 0x1
0x55555555d11f <cooking_mama::main+1183> movsxd rdi, DWORD PTR [r10-0x20]
0x55555555d123 <cooking_mama::main+1187> test rdi, rdi
0x55555555d126 <cooking_mama::main+1190> je 0x55555555d260 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1504>
0x55555555d12c <cooking_mama::main+1196> cmp edi, 0x9
0x55555555d12f <cooking_mama::main+1199> ja 0x55555555d7e8 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2920>
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ p $rdi
$1 = 0x1
gef➤ ni
...
gef➤ x/9wx $rsp+0x4c+0x4
0x7fffffffdb80: 0x00000001 0x00000000 0x00000000 0x00000000
0x7fffffffdb90: 0x00000000 0x00000000 0x00000000 0x00000000
0x7fffffffdba0: 0x00000000See how the slot gets “marked” by the index. Looking at our next instruction we can figure out what r10 is directly:
gef➤ p $r10-0x20
$2 = 0x7fffffffdcd4
gef➤ x/9wx $rsp+0x1a0
0x7fffffffdcd0: 0x00000001 0x00000005 0x00000001 0x00000001
0x7fffffffdce0: 0x00000001 0x00000001 0x00000001 0x00000008
0x7fffffffdcf0: 0x00000009From the disassembly we know that this instruction reference just goes down the memory in 0x4 increments, effectively iterating over the array.
The test rdi, rdi instruction also makes sure that the entire array is filled (non-zero).
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555d12c <cooking_mama::main+1196> cmp edi, 0x9
0x55555555d12f <cooking_mama::main+1199> ja 0x55555555d7e8 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2920>
0x55555555d135 <cooking_mama::main+1205> mov DWORD PTR [rsp+rdi*4+0x4c], 0x1
→ 0x55555555d13d <cooking_mama::main+1213> movsxd rdi, DWORD PTR [r10-0x1c]
0x55555555d141 <cooking_mama::main+1217> test rdi, rdi
0x55555555d144 <cooking_mama::main+1220> je 0x55555555d260 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1504>
0x55555555d14a <cooking_mama::main+1226> cmp edi, 0x9
0x55555555d14d <cooking_mama::main+1229> ja 0x55555555d7e8 <_ZN12cooking_mama4main17h61864c778b35fb2fE+2920>
0x55555555d153 <cooking_mama::main+1235> mov DWORD PTR [rsp+rdi*4+0x4c], 0x1
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ x/9wx $rsp+0x4c+0x4
0x7fffffffdb80: 0x00000001 0x00000000 0x00000000 0x00000000
0x7fffffffdb90: 0x00000001 0x00000000 0x00000000 0x00000000
0x7fffffffdba0: 0x00000000Now we see that index 5 is also marked.
Jumping straight to the check at the end,
gef➤ b *0x55555555d20b
Breakpoint 4 at 0x55555555d20b
gef➤ c
Continuing.
Breakpoint 4, 0x000055555555d20b in cooking_mama::main ()
gef➤ x/9wx $rsp+0x1a0
0x7fffffffdcd0: 0x00000001 0x00000005 0x00000001 0x00000001
0x7fffffffdce0: 0x00000001 0x00000001 0x00000001 0x00000008
0x7fffffffdcf0: 0x00000009
gef➤ x/9wx $rsp+0x4c+0x4
0x7fffffffdb80: 0x00000001 0x00000000 0x00000000 0x00000000
0x7fffffffdb90: 0x00000001 0x00000000 0x00000000 0x00000001
0x7fffffffdba0: 0x00000001The result makes sense, as we only have indices 1, 5, 8 and 9 in our input.
And of course, static analysis already told us that we want all of them to be marked:
gef➤ del
gef➤ b *0x55555555d20b
Breakpoint 5 at 0x55555555d20b
gef➤ r
...
⠀⠀⢀⣴⣿⣿⣷⣦⣌⠛⢦⡀⠀⠈⠓⢦⣀⡀⠀⣸⣿⣿⣿⡀⠀
⠀⠀⡾⠋⠉⢿⣿⣿⡿⠟⠦⣝⡲⣄⣀⠀⠈⠉⠉⣽⡿⢿⣿⡇⠀
⠀⠀⣷⠀⣠⣿⡿⠋⠀⠀⣶⢤⣙⠳⢭⣙⠲⠤⠴⠋⠑⠀⠁⣧⠀
⠀⠀⢸⡼⠛⠛⠀⠀⠀⣼⠉⢿⣿⣧⣶⡿⠛⠶⢤⣀⠀⠀⠀⣻
⠀⠀⢨⡇⠀⠀⠀⠀⠀⠈⠉⠉⢸⡟⣺⠃⠀⠀⠀⠈⠙⠲⠶⠋⠀
⠀⠀⣸⠁⠀⠀⠀⠀⠀⢀⡀⠀⢸⡷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣰⠃⠀⠀⠀⠠⣄⡀⠀⠉⣳⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀WHO LET HIM COOK
⣞⠁⠀⠲⣄⠀⠀⠀⠉⠉⡷⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣌⠳⣤⡀⠈⠓⠦⢤⡴⠚⠁⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⠀⠀⠀⠀
⣿⣷⣤⡿⢷⠀⣀⡴⣷⠒⠒⢒⣶⢤⠞⠉⠙⢻⣿⣷⣄⠀⠀⠀⠀
⠙⠻⣿⣷⠈⠛⠙⡇⣿⠀⠀⢯⣽⢿⠀⠀⠀⣴⠚⠉⠛⠀⠀⠀⠀
⣶⣆⠀⢹⣠⠶⣄⡇⢻⠛⠓⠒⠚⠋⠙⠓⠲⠮⠿⠆⠀⠀⠀⠀⠀
⣿⣿⠀⢸⠙⠒⢃⣇⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
> 123467
Breakpoint 1, 0x000055555555cfd5 in cooking_mama::main ()
...
gef➤ x/9wx $rsp+0x1a0
0x7fffffffdcd0: 0x00000001 0x00000005 0x00000002 0x00000003
0x7fffffffdce0: 0x00000004 0x00000006 0x00000007 0x00000008
0x7fffffffdcf0: 0x00000009
gef➤ x/9wx $rsp+0x4c+0x4
0x7fffffffdb80: 0x00000001 0x00000001 0x00000001 0x00000001
0x7fffffffdb90: 0x00000001 0x00000001 0x00000001 0x00000001
0x7fffffffdba0: 0x00000001
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
gef➤ ni
...
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555d21f <cooking_mama::main+1439> pand xmm3, xmm2
0x55555555d223 <cooking_mama::main+1443> movmskps edi, xmm3
0x55555555d226 <cooking_mama::main+1446> xor edi, 0xf
→ 0x55555555d229 <cooking_mama::main+1449> jne 0x55555555d260 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1504> NOT taken [Reason: !(!Z)]
0x55555555d22b <cooking_mama::main+1451> cmp DWORD PTR [rsp+0x70], 0x1
0x55555555d230 <cooking_mama::main+1456> jne 0x55555555d260 <_ZN12cooking_mama4main17h61864c778b35fb2fE+1504>
0x55555555d232 <cooking_mama::main+1458> movaps XMMWORD PTR [rsp+0x60], xmm1
0x55555555d237 <cooking_mama::main+1463> movaps XMMWORD PTR [rsp+0x50], xmm1
0x55555555d23c <cooking_mama::main+1468> mov DWORD PTR [rsp+0x70], 0x0
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤ p $rdi
$3 = 0x0Passing the first iteration of the first check.