# UTCTF recur Write Up
## Details:Points: 624
Jeopardy style CTF
Category: reverse engineering
Comment:
I found this binary that is supposed to print flags.
It doesn't seem to work properly though...
## Write up:
Running the file we get the following output:
```./recur utflag{```
After this the program seems to keep chugging, if left for a bit of time we get one more letter, 0. 
Next I checked what type of file it was and saw that it was a 64 bit ELF file. At this point I started reverse engineering.
The main function was:
```cint __cdecl main(int argc, const char **argv, const char **envp){  char v3; // bl  unsigned __int8 v4; // al  int i; // [rsp+Ch] [rbp-14h]
  for ( i = 0; i <= 27; ++i )  {    v3 = flag[i];    v4 = recurrence(i * i);    putchar(v3 ^ v4);    fflush(stdout);  }  return 0;}```
This loops through some flag value and then passes the current place squared to the recurrence function before xor'ing them together.
The recurrence function looked like this:
```c__int64 __fastcall recurrence(int a1){  int v2; // ebx
  if ( !a1 )    return 3LL;  if ( a1 == 1 )    return 5LL;  v2 = 2 * recurrence(a1 - 1);  return v2 + 3 * (unsigned int)recurrence(a1 - 2);}```
I then also looked at the values of flag:
```pythonflag = [0x76, 0x71, 0xC5, 0xA9, 0xE2, 0x22, 0xD8, 0xB5, 0x73, 0xF1, 0x92, 0x28, 0xB2, 0xBF, 0x90, 0x5A, 0x76, 0x77, 0xFC, 0xA6, 0xB3, 0x21, 0x90, 0xDA, 0x6F, 0xB5, 0xCF, 0x38]```
As the purpose of this challenge was to complete this program I decided that to do this we would need to optimize the recurrence function. Rather than finding the same numbers over and over again I decided to store all found values in an array and return them. I decided to code this in python since I didn't want to deal with memory allocation in c.
```python# known flag valuesflag = [0x76, 0x71, 0xC5, 0xA9, 0xE2, 0x22, 0xD8, 0xB5, 0x73, 0xF1, 0x92, 0x28, 0xB2, 0xBF, 0x90, 0x5A, 0x76, 0x77, 0xFC, 0xA6, 0xB3, 0x21, 0x90, 0xDA, 0x6F, 0xB5, 0xCF, 0x38]
# string to store flag ins = ""
# known return valuesnums = [3, 5]
# modified recurrence functiondef recurrence(i):
    # if i is in the array then return the found value    if i < len(nums):        return nums[i]
    # otherwise do the normal stuff    x = 2*recurrence(i-1)    ret = x + 3* recurrence(i-2)
    # if i is the next number in the array then add it    if i == len(nums):        nums.append(ret)
    # return the value     return ret
# loop through the flagfor i in range(0,28):    # loop through the values from i to i*i -1	for j in range(i, i*i):        # add all values to the array		recurrence(j)    # add value to string, we need to and the result of recurrence with 0xFF     # since char only accepts 2 hex values	s += chr(flag[i]^(recurrence(i*i)&0xFF))
# print the stringprint(s)```
When run we get the flag:
```utflag{0pt1m1z3_ur_c0d3_l0l}```