Tags: crypto 

Rating: 5.0

# CHALLENGE

A stream cipher in only 122 bytes!
Note: This has been tested on python versions 3.8 and 3.9

# WRITEUP

In this challenge we are given a python script `mingen.py` that produced an output `output.txt`
The script is written in only two lines, but takes a complex analysis. I will try to break it down in simple terms:

```Python
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(id(f));print(*map(lambda c:ord(c)^next(g),list(open('f').read())))
```
The first line of the code is declaring a function 'f' taking an argument 'x' `def f(x)` which does some crazy math with you input 100 times. Therefore, it generates a 100-byte long generator item. In simple terms, you can compare this to a list of 100 items.
Then, the function is called using `id(f)` as parameter and stored in the variable `g`.
In simple terms, the function `id()` function returns the identity of an object. You could say that this is "random", since everytime you execute this script it will generate a different number.

So now we know that we are inputing a "random" number as x to `f(x)`, some black magic happens 100 times, and this "list" (generator) is stored in the variable `g`.
However, when you try to `print(g)`, you get something like `<generator object f at 0x7f834f0d3660>`. In order see the actual numbeers, we need to run `print(*g)`, this is because the `*` collects all the positional arguments in a tuple, similar how `for item in items` would collect every item in a list.

Let's move on with the code analysis:
this big part: `print(*map(lambda c:ord(c)^next(g),list(open('f').read())))` is doing the following:
1. opens the file "f" (we assume it's the flag file), reads it, and returns it as a list, so that every character of the file is now a list item.
2. stores the flag in the `c` variable, which is done using `lambda c`.
3. xor each flag character with each number in the `g` variable.

I'll rewrite the whole code now in simple terms:
```Python
def f(x):
my_list = []
for i in range(100):
x = ((-~x)*x+-~-x)%727 #I didn't actually verify if this works, think of as pseudo-code just to give a basic idea of what's happening
my_list.append(x)
return my_list

flag = open('f').read()
output = []
random_number = id(f)
g = f(random_number)

for i in range(len(flag)):
output.append(ord(flag[i]) ^ g[i])

print(output)
```
Now, the thing about xor encryption is that it can be easily reversed. This is because of the following:
a ^ b = c
c ^ a = b
c ^ b = a

We already know our c, because that's what's in the `output.txt` file given.
We know that a is supposed to be the real flag. The real flag always starts with `rarctf{`
We know that b is the generator object stored in the `g` variable.

So we can take the first 7 elements of our `output.txt` and xor with `rarctf{`. Hence c ^ a = b.

```Python
output = [281, 547, 54, 380, 392, 98, 158, 440, 724, 218, 406, 672, 193, 457, 694, 208, 455, 745, 196, 450, 724]
flag = 'rarctf{'

print("xor result of flag and output:")
for i in range(len(flag)):
print(ord(flag[i]) ^ output[i], end = ' ')
```

result = 363 578 68 287 508 4 229

Now let's brute force the `f(x)` to see what input we need to return a sequence that starts in those numbers:

```Python
print("number for x that will have g start in 363")
for i in range(1000):
g = f(i)
if next(g) == 363:
print(i, end = ' ')
```
result = 256 470 983

So these numbers will generate a sequence that starts in 363, just like our "c ^ a" result above. One of these numbers might generate a sequence that's identical to what we're looking for. Let's test them:
```Python
x = 256
print(f"Next 6 digits in g for x starting in {x}")
g = f(x)
for i in range(7):
print(next(g), end = ' ')
```
result = 363 150 666 457 250 45 569
Not what we're looking for, let's move on:

```Python
x = 470
print(f"Next 6 digits in g for x starting in {x}")
g = f(x)
for i in range(7):
print(next(g), end = ' ')
```
result = 363 578 68 287 508 4 229
Bingo!
This matches the result of output ^ flag
Now that we know that `470` will generate the list we want, we only need to xor it with the output to get the flag:
```Python
g = f(x)
print("xor output with g to get the flag")
for n in output:
print(chr(n ^ next(g)), end = '')
```
result = **rarctf{pyg01f_1s_fun}**

Full code:
```Python
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)

print("number for x that will have g start in 363")
for i in range(1000):
g = f(i)
if next(g) == 363:
print(i, end = ' ')
print("\n")

x = 470
print(f"Next 6 digits in g for x starting in {x}")
g = f(x)
for i in range(7):
print(next(g), end = ' ')
print("\n")

output = [281, 547, 54, 380, 392, 98, 158, 440, 724, 218, 406, 672, 193, 457, 694, 208, 455, 745, 196, 450, 724]
flag = 'rarctf{'

print("xor result of flag and output:")
for i in range(len(flag)):
print(ord(flag[i]) ^ output[i], end = ' ')
print("\n")

g = f(x)
print("xor output with g")
for n in output:
print(chr(n ^ next(g)), end = '')
print("\n")

```

Alternative two-line solution:
```Python
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(470);print(*map(lambda c:chr(int(c)^next(g)),open('output.txt').read().split(' ')))
```