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)

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

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)