Decode Me - a Write-Up
Decode Me was one of the challenge proposed during the one-month CTF organized by @ComCyberFR. This challenge was a reverse challenge. You have a binary which expects a password:
$ ./decode-me
./decode-me <password>
$ ./decode-me test
Bad password
So let’s start the reverse!
Static analysis - first service
Before starting reading the assembly, some basic analysis.
$ file decode-me
decode-me: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, for GNU/Linux 3.2.0, BuildID[sha1]=68d67f11189e9759d9b07e7de74d85690d3390b2, not stripped
The file is stripped. This will make the reverse a little bit harder as no debug information is present. Also, the file is statically linked. Which means that it would contains a lot of useless functions. We should also check if the file is packed:
The file doesn’t seem to be packed either. Ok, time to look at some binary.
Static analysis - second service
I used GHydra for the reverse. The entrypoint is:
void _start(void) {
__libc_start_main(main);
do {
/* WARNING: Do nothing block with infinite loop */
} while( true );
}
Nothing special here. And the function main:
void main(void){
code *pcVar1;
args = &stack0x00000004;
signal(5,authentification);
pcVar1 = (code *)swi(3);
(*pcVar1)();
return;
}
Ah! An anti-debugging technique! Here, the principle is to throw an INT3, which is a signal SIGTRAP. When a debugger reads this, it stops its execution. However, we can notice that the program set a signal. 5 is associated to SIGTRAP (you can find the list of signals in the file signal.h). Normally, the program will throw a SIGTRAP and call the function authentication. The debugger will overide the behavior. More information here (in french).
Let’s check the authentication function.
void authentification(void) {
undefined4 *puVar1;
short sVar2;
long lVar3;
puVar1 = (undefined4 *)args[1];
if (*args != 2) {
printf("%s <password>\n",*puVar1);
exit(1);
}
lVar3 = ptrace(PTRACE_TRACEME,0,1,0);
if (lVar3 == -1) {
puts("Checking password..");
check_password2(*puVar1);
puts("Bad password");
}
else {
sVar2 = check_password(puVar1[1]);
if (sVar2 == 0) {
puts("Bad password");
}
else {
puts("Good Job, you can validate with this password =)");
}
}
exit(0);
}
Here again, another anti-debugging technic. The program is calling ptrace(PTRACE_TRACEME,0,1,0) on itself.
If a debugger is present, the function will return -1, 0 otherwise. It is another way to prevent dynamic analysis.
You can easily confirm that because the result of check_password2 is ignored and the program always prints
“Bad password”!
Static analysis - final plate
Time to analyze real checking function check_password. The next snippet is a clean version of this function:
uint check_password(char *password) {
password_length = strlen(password);
MAX_LENGTH = 96;
local_3d = 0xf394b8b8;
local_39 = 0x9dabd7af;
local_35 = 0x593299a8;
local_31 = 0x1f20d82f;
local_2d = 0xceb6f6b0;
local_29 = 0xc92774cc;
local_25 = 0x5955f0e0;
local_21 = 0xcc26908d;
local_1d = 0xe6b5ab5e;
local_19 = 0x529cef69;
local_15 = 0x4e8d5d5;
local_11 = 0;
real_password = *local_3d;
real_password_length = 45;
if (password_length < MAX_LENGTH) {
gen_tab(password); // Randomly fill the variable array
next_function = /* calculate a value /;
int i = 0;
while(i < password_length) {
char c = array[i];
encrypted_password[i] = funcs[next_function](c);
// next doesn't exist in the binary,
// Just to make the code cleaner
next_function = next(next_function, encrypted_password[i]);
i++;
}
int j = 0;
int result = 1;
while(j < real_password_length - 1) {
if(real_password[j] != encrypted_password[j]) {
result = 0;
}
j++;
}
return result;
}
...
}
So, local_3d contains the encrypted password. The next snippet is a short version of gen_tab:
void gen_tab(char *password) {
...
hash = 0;
password_length = strlen(password);
i = 0;
while (i < password_length) {
hash += (int)password[i];
i += 1;
}
srandom(hash & 0x3ff);
j = 0;
while (j < 96) {
random_char = rand();
ascii[j] = (char)random_char;
j += 1;
}
}
The function randomly fills an array. Well, not so randomly. The seed is generated from a hash calculated from the password. We might think that there is a huge number of possibility. But, we can see that the hash is “anded” with 0x3FF or 1023. Which means that there will be no more than 1024 ways of filling the ascii array!
Let’s get back to check_password. The variable next_function is used with the array funcs. funcs is an array of 4 functions to decode. So, the first initialization of next_function is 0, 1, 2 or 3.
In fact, there will be no more than 4096 passwords possibles. We can easily generate all combinaisons of
(next_function, array) then called decode-me until we get the message Good job!
Decoding it
So, to decode the password, I wrote a program to generate all 1024 values of array ascii:
void main() {
for( int hash = 0; hash < 1024; hash++){
long lVar1;
srandom(hash & 0x3ff);
int j = 0;
while (j < 0x60) {
int lVar1 = rand();
char c = (char)(lVar1 & 0xFF);
printf("%02X", (unsigned int)(lVar1 & 0xFF));
j += 1;
}
printf("\n");
}
}
Then, I wrote a python script which, for an array ascii, it generates 4 passwords. The next snippet is the simplified algorithm of the script
For i in [0, 1, 2, 3]:
next_function = i
For c in local_3d:
r = reverse_functions[next_function](c)
print(r)
next_function = next(next_function, r)
The main job was to:
- Find the reverse function for each encoding functions of array funcs
- Write a correct implementation of function next
To do so, I needed to do some dynamic analysis
Dynamic analysis - the dessert!
Here, nothing special in fact. I have to bypass anti-debugging protections. One solution could have been to modify the binary and execute in gdb. I found it simplier just to add breakpoints before the execution of anti-debugging commands and directly jumps to the next correct line.
Once done, I retrieved some values from the program and check that reversed functions return the correct value.
The digestif!
Time to get the password!
$ gcc decode-me.c
$ ./a.out > decode-me.ascii # generate all 1024 random values of ascii
$ python3 decode-me.py > decode-me.res
$ $ for i in $(cat decode-me.res); do ./decode-me $i | grep Good && echo $i ; done
Good Job, you can validate with this password =)
Gr3aT-RevErS3*MY_FR13nD!+YoU_4R3-Th3-BEST_=)
The code can be found on my GitHub.
That’s all floks!