Small Brainfuck reversing challenge @ Grehack2024 - WTBF

Difficulty:    Medium
Description:   WTF if going on here?
Author:        Olivier

For this Chall, we’re given a single text file:

++++++++++++++[>+++>+++>+++>++++++>+++<<<<<-]
>>+++++>++++++>++++++++>>++++++++++++++++++
[>++++++>+++++>+++>++++>++++++++>+++++>++++++++
>+++>+++++++++++>+++++++>++>++++>++++++++>+++++++++++
+>++++++>++++++++++++>+++++++++++<<<<<<<<<<<<<<<<<-]
>++++++++++++>++++++++++>>+++>++++>++++++++++++>+>+++++++++++++++>+>
++++++++++>+++++++++>+++>++++>++++++++++++++++>++++++>+>++++++++++++++++
[>>,[<+++>-]<+[<->-]<[]<]
<
[.<]

This obviously looks like Brainfuck code.

The first reaction is to convert to another language. Lots of converters can be found online, such as brainfuck to C converters.

By doing so, it is easier to identify the program into three parts.

Part 1

++++++++++++++[>+++>+++>+++>++++++>+++<<<<<-]
>>+++++>++++++>++++++++>>++++++++++++++++++
[>++++++>+++++>+++>++++>++++++++>+++++>++++++++
>+++>+++++++++++>+++++++>++>++++>++++++++>+++++++++++
+>++++++>++++++++++++>+++++++++++<<<<<<<<<<<<<<<<<-]
>++++++++++++>++++++++++>>+++>++++>++++++++++++>+>+++++++++++++++>+>
++++++++++>+++++++++>+++>++++>++++++++++++++++>++++++>+>++++++++++++++++

The first part only consists of setting up variables on the tape. While it has multiple loops, is not worth looking up in detail, as we’re only looking for IO interactions that could give us the flag.

int size = 1000;
int tape[size];
int i = 0;

// [ part 1's code ]

for (int i = 0; i < ptr + 3; i++) {
    printf("tape[%d] = %d;\n", i, tape[i]);
}

By adding the following snippet after the end of the part 1 in the converted code, all the values of the tape are printed. The following output is then given by the progam:

tape[0] = 0;
tape[1] = 42;
tape[2] = 47;
tape[3] = 48;
tape[4] = 92;
tape[5] = 42;
tape[6] = 0;
tape[7] = 120;
tape[8] = 100;
tape[9] = 54;
tape[10] = 75;
tape[11] = 148;
tape[12] = 102;
tape[13] = 145;
tape[14] = 69;
tape[15] = 199;
tape[16] = 136;
tape[17] = 45;
tape[18] = 75;
tape[19] = 148;
tape[20] = 232;
tape[21] = 114;
tape[22] = 217;
tape[23] = 214;
tape[25] = 0;
tape[26] = 0;

Part 2

[>>,[<+++>-]<+[<->-]<[]<]

This is the interesting part of the code.

Here is its C equivalent.

while (tape[ptr] != 0) {
  ptr += 2;
  scanf("%1d",tape[ptr]);
  while (tape[ptr] != 0) {
    ptr -= 1;
    tape[ptr] += 3;
    ptr += 1;
    tape[ptr] -= 1;
  }
  ptr -= 1;
  tape[ptr] += 1;
  while (tape[ptr] != 0) {
    ptr -= 1;
    tape[ptr] -= 1;
    ptr += 1;
    tape[ptr] -= 1;
  }
  ptr -= 1;
  while (tape[ptr] != 0) { } // infinite loop, must avoid it to continue execution
  ptr -= 1;
} 

The code being pretty short and easy to read, it can be rewritten as the following.

while (tape[ptr] != 0) {
  scanf("%d",tape[ptr+2]);
  tape[ptr+1] = 3 * tape[ptr+2] + 1;
  if (tape[ptr+1] != tape[ptr]) {
    err(EXIT_FAILURE,"tape[%d] == %d != tape[%d] == %d",ptr+1,tape[ptr+1],ptr,tape[ptr]);
  }
  tape[ptr+2] = 0, tape[ptr+1] = 0, tape[ptr] = 0, ptr -=1;
}

By doing so, a pretty simple clearing condition can be found: we need tape[ptr] = 3*x+1 to be valid, with x as the character code of the character inputed.

By reversing the equation x = tape[ptr]/3 - 1 is obtained.

However these equations do not satisfy all of the equations on the tape, as every number can’t be decomposed as 3x + 1.

By looking at the values of on the tape after part 1 and guessing that we’re expected to type a flag in ascii, we write our equation once again: tape[ptr] = (3*x + 1) % 0x100

By using simple bruteforcing to find the corresponding values:

while (tape[ptr] != 0) {
  for (int i = 0; i < 0x100; i++) {
    if ((i*3+1)% 0x100 == tape[ptr]) {
      tape[ptr+2] = i;
      break;
    }
  }
  if (tape[ptr+2] == 0 && tape[ptr+1] != 1) {
    err(EXIT_FAILURE,"unable to find a valid number");
  }
  printf("%c",tape[ptr+2]);
  tape[ptr+1] = (3 * tape[ptr+2] + 1) % 0x100;
  if (tape[ptr + 1] != tape[ptr]) {
    err(EXIT_FAILURE,"tape[%d] == %d != tape[%d] == %d",ptr+1,tape[ptr+1],ptr,tape[ptr]);
  }
  tape[ptr+2] = 0, tape[ptr+1] = 0, tape[ptr] = 0, ptr -=1;
}  

The program can now be executed, and the flag is printed successfully

Flag: GH{M1nd-Bl0w1ng!}