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

## Source code
### Main method
```c
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
```c
__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](https://en.wikipedia.org/wiki/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.

```c
#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 ;)!