Cybrics 2021 Walker Challenge

Challenge Description

Challenge files found here: https://cybrics.net/tasks/walker

Trigger The First Exception

Looking at main we see getline used to receive input from the flag file. By editing flag.txt to end with \x00 or \xFF we see the T1Exception is triggered.

Although no output from the binary has changed we now see the program does not immediately close. Instead there is a new prompt for more input. Almost every input will not do anything, except for a few notable characters. The characters f d l r u all lead to the program shutting down. Though the character c leads to new output being spit out (as seen below).

The next break through came by manually breaking each notable function in gdb to find which was responsible for the new output. From this slow process the function check_substr was discovered. Within IDA's generated psuedocode there is a print statement which uses three %d format characters. Oh good three arbitrary integers, that totally tells us a ton.

void __fastcall __noreturn check_substr(const char *a1, int a2)
{
    T5Exception *v2; // rbx
    T5Exception *v3; // rbx
    T8Exception *v4; // rbx
    unsigned __int8 v5; // [rsp+13h] [rbp-1Dh]
    int i; // [rsp+14h] [rbp-1Ch]
    char *v7; // [rsp+18h] [rbp-18h]

    v5 = map[10 * x_pos + y_pos];
    if ( (v5 & 1) == 0 )
    {
    v2 = (T5Exception *)__cxa_allocate_exception(8uLL);
    *(_QWORD *)v2 = 0LL;
    T5Exception::T5Exception(v2);
    __cxa_throw(v2, (struct type_info *)&`typeinfo for'T5Exception, T5Exception::~T5Exception);
    }
    v7 = strings[MOVES];
    for ( i = 0; i <= 4; ++i )
    {
    if ( (v5 ^ a1[a2 + i]) != v7[i] )
    {
        printf("%d %d %d\n", (unsigned int)(char)v5, (unsigned int)(char)(v5 ^ a1[a2 + i]), (unsigned int)v7[i]);
        v3 = (T5Exception *)__cxa_allocate_exception(8uLL);
        *(_QWORD *)v3 = 0LL;
        T5Exception::T5Exception(v3);
        __cxa_throw(v3, (struct type_info *)&`typeinfo for'T5Exception, T5Exception::~T5Exception);
    }
    }
    v4 = (T8Exception *)__cxa_allocate_exception(0x10uLL);
    T8Exception::T8Exception(v4, 5);
    __cxa_throw(v4, (struct type_info *)&`typeinfo for'T8Exception, T8Exception::~T8Exception);
}

Cracking The Substring

Looking right before the print statement there is an if statement which must fail for the print to occur. Essentially the second printed integer is being compared to the third. Upon playing with our input though we see the second printed value change.

Essentially the code is looping through each character provided before c and xor'ing it with the third printed integer. Once we have provided the correct character as input we see a whole new value replaces the first printed value which was previously 97.

Continuing the process eventually results in a new line prompting for more input. Though any attempt to follow the decoding formula we just performed results in non ascii characters being calculated. So something is different on this second input prompt. We need to take a closer look at the d l r u characters as inputs.

Traversal

Now would be a good time to mention the map variable. During the tedious work of digging through the assembly of the binary there were many references to a map variable which seems to be filled with arbitrary integers. Now there was no one thing that made the next piece of info "click" it just kind of became apparent after hours of digging. The characters d l r u stand for down left right up and used to navigate map.

We can prove that we start at the first value of the grid which is 97 (or hex 0x61), that number should be familar to you by now.

So I'm going to skip a bunch of trial and error explanation. This challenge took my teammate holz a shit ton of of time. Most of that was just tinkering with the binary via gdb. We eventually saw that whenever c is entered the check_substr function is only ran if an exception handler T6Exception:is_ok returns 1. There are four total T6Exception handler functions. But the guide for traversing the map can be found in the general T6Exception function.

void __fastcall T6Exception::T6Exception(T6Exception *this, int a2, int a3)
    {
      std::exception::exception(this);
      *(_QWORD *)this = off_7B10;
      *((_DWORD *)this + 2) = a2;
      *((_DWORD *)this + 3) = a3;
      *((_DWORD *)this + 4) = 1;
      if ( *((int *)this + 2) >= 0 && *((int *)this + 2) <= 9 )
      {
        if ( *((int *)this + 3) >= 0 && *((int *)this + 3) <= 9 )
        {
          if ( (char)map[10 * *((_DWORD *)this + 2) + *((_DWORD *)this + 3)] < 0 )
            *((_DWORD *)this + 4) = 0;
        }
        else
        {
          *((_DWORD *)this + 4) = 0;
        }
      }
      else
      {
        *((_DWORD *)this + 4) = 0;
      }

Alright now this function first checks the x (this + 3) and y (this + 2) positions to not be out of bounds as the map is only 10x10. Now the explanation for what (this + 4) represents is a little murky until you see it is returned by T6Exception:is_ok so we treat it as an is_ok variable which tells us if we are at a correct position in the map to run check_substr.

The function starts with is_ok being true. But if either our x or y coordinate is out of bounds then is_ok becomes false. More importantly the last condition that may set is_ok to false, is whether the current value in map is greater than or equal to 0x80. The innermost if checks if the number is less than 0. Notice inside the if statement that the map value is typecasted as char. Meaning that only 1 byte is being compared. Though remember how negative numbers are represented in binary and c. Any value whose most significant digit is greater than 0x80 is considered negative when treated as a signed integer. Therefore the single byte we are comparing must be smaller than 0x80 for check_substr to be ran.

The following gif shows map laid out in a 10x10 grid with the values below 0x80 indicated, and the path to reach them. At each position circled in the gif you need to enter a c input to run the check.