Phase 8 (300 pts)
A very data structure related question. The difficulty was high and I only managed to solve it after the competition with some help from the challenge writer and others on Discord.
Problem Statement
Go touch grass!
Update: The final flag should resemble human-readable words
Author: treap_treap
Ghidra analysis
From the different functions, we can see that it is indeed creating a character binary tree. It will first use the input to create the tree where a character will traverse through the tree until it finds the lowest leaf and will be placed at position 1
if it is smaller or position 2
if it is larger then the element in position 0
.
- phase8
- func8_1
- func8_2
uint phase8(undefined8 param_1,undefined4 param_2,undefined4 param_3,undefined4 param_4,
undefined4 param_5,undefined4 param_6,undefined4 param_7,undefined4 param_8,char *param_9
)
{
int iVar1;
size_t target_len;
ulong another_counter?;
undefined8 in_R8;
undefined8 in_R9;
long in_FS_OFFSET;
undefined4 extraout_XMM0_Da;
undefined in_stack_ffffffffffffffa8;
int local_44;
int counter;
uint local_3c;
char *local_38;
char *target;
char *input;
long local_20;
local_20 = *(long *)(in_FS_OFFSET + 0x28);
puts("\nGo touch grass!");
target = "T30G343DDERh_TWT_e_ror";
input = (char *)calloc(0x29,1);
getInput(extraout_XMM0_Da,param_2,param_3,param_4,param_5,param_6,param_7,param_8,8,param_9,
&DAT_001028d1,input,in_R8,in_R9,in_stack_ffffffffffffffa8);
local_38 = (char *)0x0;
counter = 0;
while( true ) {
another_counter? = SEXT48(counter);
target_len = strlen(target);
if (target_len <= another_counter?) break;
local_38 = func8_1(input[counter],local_38);
counter = counter + 1;
}
local_44 = 0;
func8_2(local_38,(long)input,&local_44);
func8_3(local_38);
iVar1 = strcmp(input,target);
local_3c = (uint)(iVar1 == 0);
free(input);
if (local_20 != *(long *)(in_FS_OFFSET + 0x28)) {
/* WARNING: Subroutine does not return */
__stack_chk_fail();
}
return local_3c;
}
char * func8_1(char param_1,char *param_2)
{
char *pcVar1;
if (param_2 == (char *)0x0) {
param_2 = (char *)malloc(0x18);
*param_2 = param_1;
*(undefined8 *)(param_2 + 0x10) = 0;
*(undefined8 *)(param_2 + 8) = *(undefined8 *)(param_2 + 0x10);
}
else {
if (param_1 < *param_2) {
pcVar1 = func8_1(param_1,*(char **)(param_2 + 8));
*(char **)(param_2 + 8) = pcVar1;
}
else {
pcVar1 = func8_1(param_1,*(char **)(param_2 + 0x10));
*(char **)(param_2 + 0x10) = pcVar1;
}
}
return param_2;
}
void func8_2(undefined *param_1,long param_2,int *param_3)
{
if (param_1 != (undefined *)0x0) {
*(undefined *)(*param_3 + param_2) = *param_1;
*param_3 = *param_3 + 1;
func8_2(*(undefined **)(param_1 + 8),param_2,param_3);
func8_2(*(undefined **)(param_1 + 0x10),param_2,param_3);
}
return;
}
Solution
I am not a guru in data structures but I have a rough idea of what it is doing:
- It constructs the tree based on user input
- It concats the elements by traversing depth first down the left side of the tree before the right side
- Then it compares the concatenated string to
T30G343DDERh_TWT_e_ror
This method seems to be called Preorder Depth First Traversal
. More details can be found here
Solving it
Instead of scripting for it (since I am not familiar with data structures), I have used pen and paper (as suggested by those in Discord)
As seen, there can be multiple solutions. With hints that it would seem like human readable text, some permutations might include:
Th3_Gr34T_ReDW0oD_Tr3E
Th3_GR34T_reDWo0D_TrE3
Th3_GR34T_reDW0oD_TrE3
Since this was solved after the competition, the author disclosed that the flag is Th3_Gr34T_ReDW0oD_Tr3E
.
Flag
DawgCTF{Th3_Gr34T_ReDW0oD_Tr3E}