Discovery

After downloading the binary, we launch it and... it never ends. While waiting, we can disassemble it with Ida.

Source code

Main method

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // ebx
  int v4; // eax
  int seed; // [rsp+20h] [rbp-20h]
  unsigned int seeda; // [rsp+20h] [rbp-20h]
  int j; // [rsp+24h] [rbp-1Ch]
  unsigned __int64 i; // [rsp+28h] [rbp-18h]

  seed = 0;
  for ( i = 50LL; i <= 0x4E; ++i )
  {
    seeda = (unsigned __int8)fibonacci(i) ^ seed;
    seed = ((unsigned __int8)seeda << 24) | (seeda >> 8);
  }
  srand(seed);
  for ( j = 0; j <= 28; ++j )
  {
    v3 = FLAG[j];
    v4 = rand();
    putchar((v4 % 255) ^ v3);
  }
  puts("\nGood you can validate the chall with this password ;)!");
  return 0;
}

This code should be fast to run. The sole exception is a call to a method fibonacci.

Fibonacci

__int64 __fastcall fibonacci(__int64 a1)
{
  __int64 v2; // rbx

  if ( !a1 )
    return 0LL;
  if ( a1 == 1 )
    return 1LL;
  v2 = fibonacci(a1 - 1);
  return v2 + fibonacci(a1 - 2);
}

This is truly the fibonacci function. However the way it is coded is very simple and known to be astronamically slow.
This explain why the code never ends to run, if we had an infinite amount of time it would finish and certainly gives us the flag.

FLAG variable

.data:0000000000004050                 public FLAG
.data:0000000000004050 ; unsigned __int8 FLAG[29]
.data:0000000000004050 FLAG            db 0B5h, 63h, 98h, 3Dh, 0B5h, 6, 46h, 0BAh, 0Fh, 0D5h
.data:0000000000004050                                         ; DATA XREF: main+6F↑o
.data:0000000000004050                 db 47h, 0CEh, 97h, 0EFh, 7Bh, 28h, 0DBh, 0E7h, 39h, 10h
.data:0000000000004050                 db 0B0h, 0F5h, 44h, 0ECh, 30h, 88h, 46h, 0F6h, 88h
.data:0000000000004050 _data           ends
.data:0000000000004050

After cleaning, the flag is array is:

0xB5, 0x63, 0x98, 0x3D, 0xB5, 0x06, 0x46, 0xBA, 0x0F, 0xD5, 0x47, 0xCE, 0x97, 0xEF, 0x7B, 0x28, 0xDB, 0xE7, 0x39, 0x10, 0xB0, 0xF5, 0x44, 0xEC, 0x30, 0x88, 0x46, 0xF6, 0x88

Recreate the script locally

Now that we know the issue is with the call to fibonacci, we can re-write the script ourselves and then optimise it.
What is slow is that fibonacci calls itself an exponential number of time.
The usual optimisation in this case is called memoization. The purpose is to remember the result of each call to the method. Once you know the result of fibonacci(23) and fibonacci(24), you can compute fibonacci(25) in a single operation.

For this purpose we create a cache array that will contain fibonacci results, and keep the rest of the code as its disassembled version.

#include <stdio.h>
#include <stdlib.h>

static size_t count = 0;

/**
* Build a cache representing the Fibonacci sequence.
* Note that the second parameter is an array index which allows the cache to
* be checked for the required element. 
*/
int fibonacci(int *cache, int n)
{
    if (cache[n] == -1) {
        cache[n] = fibonacci(cache, n - 1) + fibonacci(cache, n - 2);
    }
    return cache[n];
}

int main()
{
  int v3; // ebx
  int v4; // eax
  int seed; // [rsp+20h] [rbp-20h]
  unsigned int seeda; // [rsp+20h] [rbp-20h]
  int j; // [rsp+24h] [rbp-1Ch]
  unsigned long long i; // [rsp+28h] [rbp-18h]
  char FLAG[29] = { 0xB5, 0x63, 0x98, 0x3D, 0xB5, 0x06, 0x46, 0xBA, 0x0F, 0xD5, 0x47, 0xCE, 0x97, 0xEF, 0x7B, 0x28, 0xDB, 0xE7, 0x39, 0x10, 0xB0, 0xF5, 0x44, 0xEC, 0x30, 0x88, 0x46, 0xF6, 0x88 };

  int cache[100] = { [0 ... 99] = -1 };

  // Set the first two elements in the sequence, which are known
  cache[0] = 0;
  cache[1] = 1;

  seed = 0;
  for ( i = 50; i <= 0x4E; ++i )
  {
    seeda = (unsigned char)fibonacci(cache, i) ^ seed;
    seed = ((unsigned char)seeda << 24) | (seeda >> 8);
  }
  srand(seed);
  for ( j = 0; j <= 28; ++j )
  {
    v3 = FLAG[j];
    v4 = rand();
    putchar((v4 % 255) ^ v3);
  }
  puts("\nGood you can validate the chall with this password ;)!");
  return 0;
}

CYBERTF{Fuck_Fibo_3v3ryWhere}
Good you can validate the chall with this password ;)!