Rating:
Using ghidra, we can decompile the binary. Annotating some variables, and inferring the size and
type of the array we obtain the following:
```c
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:
```c
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.
```c
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
unsigned int collatz(unsigned int n) {
unsigned int i = 0;
if (n == 0) {
return 0;
}
while (n != 1 && i < 360) {
if ((n & 1) == 0) {
n /= 2;
} else {
n = 3*n + 1;
}
i += 1;
}
return i;
}
int main() {
int i;
unsigned int nums[1200];
/*Zero out nums*/
memset(nums, 0, sizeof(nums));
/* Map of counts for each selector. */
auto nums_map = std::map<unsigned int,std::vector<unsigned int> >();
/* initialize selectors */
nums_map[105] = std::vector<unsigned int>();
nums_map[110] = std::vector<unsigned int>();
nums_map[113] = std::vector<unsigned int>();
nums_map[116] = std::vector<unsigned int>();
nums_map[136] = std::vector<unsigned int>();
nums_map[160] = std::vector<unsigned int>();
nums_map[181] = std::vector<unsigned int>();
nums_map[185] = std::vector<unsigned int>();
nums_map[199] = std::vector<unsigned int>();
nums_map[202] = std::vector<unsigned int>();
nums_map[211] = std::vector<unsigned int>();
nums_map[247] = std::vector<unsigned int>();
nums_map[266] = std::vector<unsigned int>();
nums_map[271] = std::vector<unsigned int>();
nums_map[273] = std::vector<unsigned int>();
nums_map[303] = std::vector<unsigned int>();
nums_map[318] = std::vector<unsigned int>();
nums_map[341] = std::vector<unsigned int>();
nums_map[352] = std::vector<unsigned int>();
/* populate selectors */
nums_map[105].push_back(2020429);
nums_map[105].push_back(2020432);
nums_map[105].push_back(2020433);
nums_map[105].push_back(2020434);
nums_map[110].push_back(4399499);
nums_map[113].push_back(2166353);
nums_map[116].push_back(2711150);
nums_map[136].push_back(4253755);
nums_map[136].push_back(4253767);
nums_map[136].push_back(4253790);
nums_map[136].push_back(4253798);
nums_map[136].push_back(4253800);
nums_map[136].push_back(4253801);
nums_map[136].push_back(4253803);
nums_map[136].push_back(4253808);
nums_map[136].push_back(4253809);
nums_map[136].push_back(4253810);
nums_map[136].push_back(4253813);
nums_map[136].push_back(4253814);
nums_map[136].push_back(4253816);
nums_map[136].push_back(4253817);
nums_map[136].push_back(4253818);
nums_map[136].push_back(4253820);
nums_map[136].push_back(4253822);
nums_map[136].push_back(4253823);
nums_map[136].push_back(4253824);
nums_map[136].push_back(4253825);
nums_map[136].push_back(4253826);
nums_map[136].push_back(4253827);
nums_map[136].push_back(4253828);
nums_map[160].push_back(3678256);
nums_map[160].push_back(3678257);
nums_map[181].push_back(4130207);
nums_map[181].push_back(4130208);
nums_map[185].push_back(7553325);
nums_map[199].push_back(3861206);
nums_map[199].push_back(3861209);
nums_map[202].push_back(4806021);
nums_map[211].push_back(3144271);
nums_map[211].push_back(3144273);
nums_map[211].push_back(3144274);
nums_map[211].push_back(3144275);
nums_map[211].push_back(3144276);
nums_map[211].push_back(3144277);
nums_map[211].push_back(3144278);
nums_map[211].push_back(3144279);
nums_map[211].push_back(3144280);
nums_map[211].push_back(3144281);
nums_map[211].push_back(3144282);
nums_map[211].push_back(3144283);
nums_map[211].push_back(3144284);
nums_map[211].push_back(3144285);
nums_map[247].push_back(5973577);
nums_map[266].push_back(2039181);
nums_map[271].push_back(1779864);
nums_map[273].push_back(1867034);
nums_map[303].push_back(1522942);
nums_map[318].push_back(838140);
nums_map[341].push_back(473526);
nums_map[352].push_back(495094);
/* Initialize nums array*/
for(auto i = nums_map.begin(); i != nums_map.end(); ++i) {
nums[i->first] = i->second[0];
}
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.
