collatz.md

Using ghidra, we can decompile the binary. Annotating some variables, and inferring the size and type of the array we obtain the following:

undefined8 main(void)
{
  int num;
  uint index;
  uint n;
  int matchcount;
  int collatz_selector;
  
  index = 0;
  do {
    if (0x29f7 < index) {
      putchar(10);
      return 0;
    }
    collatz_selector = int_array[index];
    matchcount = int_array[index + 1];
    n = 1;
    while (n < 900000000) {
      num = collatz(n);
      if (collatz_selector == num) {
        matchcount = matchcount + -1;
      }
      if (matchcount == 0) {
        putchar(n + 0xca5b17ff);
        fflush(stdout);
        break;
      }
      n = n + 1;
    }
    index = index + 2;
  } while( true );
}

The collatz function is as follows:

int collatz(uint n)

{
  uint current;
  int collatz_number;
  
  collatz_number = 0;
  current = n;
  while (current != 1) {
    if ((current & 1) == 0) {
      current = current >> 1;
    }
    else {
      current = current * 3 + 1;
    }
    collatz_number = collatz_number + 1;
  }
  return collatz_number;
}

so our payload is in the int_array, which is an array of pairs. The first entry is the collatz number, and the second is a count. Iterating over 900,000,000 values of n, once the match count for a given collatz number is reached, the value, offset by a constant, is printed out.

Obviously, there is a lot of recalculation. Storing 900,000,000 ints will take 3.6 gigabytes, which I didn't happen to have on hand. However, we can immediately stop collatz once it reaches 360. There are only 60 distinct (collatz number, count) pairs so you can just sweep through the entire 900,000,000 numbers and simply mark them as you go along.

    for(unsigned int n = 1; n < 900000000; ++n) {
        i = collatz(n);
        if(nums[i] == 0) {
            continue;
        }
        if(nums[i] == 1) {
            unsigned int count = nums_map[i][0];
            nums_map[i].erase(nums_map[i].begin());
            if (nums_map[i].size() == 0) {
                nums[i] = 0;
            } else {
                nums[i] = nums_map[i][0] - count;
            }
            printf("(%d, %d) %d %d %c\n",
                i, count, n,
                (unsigned char)(n+0xca5b17ff),
                (unsigned char)(n+0xca5b17ff));
        } else {
            nums[i] -= 1;
        }
    }

Here we've dumped the unique symbols into num_maps : map<uint, vector<int>. This runs in about 5 minutes in a single thread on a 1.6 Ghz i5. We can then take this list and decode the entire array.

That said, there's another way that I thought was necessary because I miscounted the number of 0's in 900000000.

The 1100 byte array is simply an array of 60 unique symbols for english. You can just use frequency analysis on it to decode almost all the characters. You know which ascii characters are still available at the end, and since it's a 1337 sp34k flag you can just guess the rest.