**Tags:** collatz-conjecture python misc

Rating: 5.0

# ICAN'TBELIEVEIT'SNOTCRYPTO

This is a pretty simple challenge, once you know what is going on.

So the question asks to give two lists `l1` and `l2`, where `l1` contains only 0 and 1, and `l2` only contains 0, 1, and 2. The lists go through the function `step()` each time, and `count()` counts how many steps it will take for `l1` and `l2` to reach the state where `l1 = [1]` and `l2 = [0]`. The flag will be printed if it needs more than 2000 steps.

There are two constraints, namely that `len(l1) == len(l2)` and `len(l1) < 24`. So you can't give a sufficiently large array to pass the test.

This is actually a well-known and studied problem in disguise. It is the process described in [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture). And `l1` and `l2` is just a simple conversion from a number to its base-6 form, and for each digit split across two lists. A simple conversion script looks like this:

```python

def to_lists(num):

l1 = []

l2 = []

while num:

digit = num % 6

l1.append(digit & 1)

l2.append(digit >> 1)

num //= 6

return l1, l2

def from_lists(l1, l2):

num, mul = 0, 1

for i in range(len(l1)):

digit = l1[i] | (l2[i] << 1)

num += digit * mul

mul *= 6

return num

```

The starting value that has the largest total stopping time within the range of $$6^{24} \approx 10^{18}$$ is written on the Wikipedia page:

> less than 10^17 is 93571393692802302, which has 2091 steps [...]

which is enough for the required 2000 steps. Therefore the exploit is simply something like this:

```python

char = ord('f')

assert(char % 6 == 0)

l1, l2 = to_lists(93571393692802302)

str1, str2 = "", ""

for i in l1:

str1 += chr(char + i)

for i in l2:

str2 += chr(char + i)

print(str1)

print(str2)

```

Which gives us output string `fggffgfgfggffffgffgggf` and `fgghfgghhhhhhghffgggfh`. Input it and we get the flag.

Original writeup (https://www.cis.upenn.edu/~hanbangw/blog/google-ctf-2021/#icantbelieveitsnotcrypto).