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

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;
}

func8_1

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;
}

func8_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:

1. It constructs the tree based on user input
2. It concats the elements by traversing depth first down the left side of the tree before the right side
3. 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}