Break a homemade cryptosystem.

## Information

• category : crypto
• points : 210

## Description

A simple and homemade cryptosystem, you may need to review your high school skills!

2 file: gantun.py, flag.enc

## Writeup

I solved this challenge together with e_ciavatta.

Let’s see the source code of the cryptosystem:

#!/usr/bin/python

from Crypto.Util.number import *
from flag import flag
from random import randint

def gantunex(x):
if len(x) == 1:
return x
elif len(x) == 2:
x, y = x[0], x[1]
if x != max(x, y):
return y ** 2 + x
else:
return x ** 2 + x + y
else:
l = randint(0, len(x) - 2)
r = randint(l + 1, len(x) - 1)
return gantunex([gantunex([x[l], x[r]])] + x[:l] + x[l + 1:r] + x[r + 1:])

def encryptex(m, l):
if len(m) % l != 0:
m += (l - len(m) % l) * b'='
M = [bytes_to_long(m[l * i:l * i + l]) for i in range(len(m)// l)]
return gantunex(M)

f = open('flag.enc', 'w')
f.write(long_to_bytes(encryptex(flag, 6)))
f.close()


We can resume the step of the system:

1. Divide the flag in blocks, the number of blocks is len(flag) // 6.
2. For each block, convert the block value to int (bytes -> int).
3. Call gantunex passing as value the list of blocks derived from step 2.

gantunex(x) is a recursive function, to understand it better we have rewritten the function in an iterative way:

def gantunex(x):
res = 0
for i in range(len(x) - 2):
l = randint(0, len(x) - 2)
r = randint(l + 1, len(x) - 1) # include both ends
g = case_2([x[l], x[r]])
x = [g] + x[:l] + x[l + 1:r] + x[r + 1:]
return case_2(x[0], x[1])

def case_2(a, b):
x, y = a, b
if x < y:
return y ** 2 + x
else:
return x ** 2 + x + y


The step are the following:

1. Iterate from $$i = 0$$ to $$len(x) - 2$$.
2. At each iteration choose two random integer $$l, r$$, with $$l \neq r$$, $$l \geq 0 \land l \leq len(x) - 2$$ and $$r \geq l+1 \land r \leq len(x) - 1$$.
3. Generate $$g$$ = case_2(x[l], x[r]).
4. Reconstruct $$x$$ such that x = g + x[:l] + x[l + 1:r] + x[r + 1:].
5. Increment $$i$$ and continue.
6. When the for loop is over, return case_2(x[0], x[1]).

As we can see, we start with a list of blocks, and we end with a number.

### 1st Problem

To create a decryption function we need to reverse case_2(a, b), to generate two values $$a, b$$ from one $$z$$. This is our solution using z3.

def reverse_2(z):
s_1 = Solver()
x = Int('x')
y = Int('y')
s_1.add(z == x ** 2 + x + y, x > y, x > 0, y > 0)
if s_1.check() == sat:
return (s_1.model()[x].as_long(), s_1.model()[y].as_long())
s_2 = Solver()
s_2.add(z == y ** 2 + x, x < y, x > 0, y > 0)
if s_2.check() == sat:
return (s_2.model()[x].as_long(), s_2.model()[y].as_long())
raise ValueError


### 2nd Problem

What about the values generated randomly?

We don’t know the values generated randomly $$(l, r)$$, so we need to bruteforce every possible solution. To do that we need to create a list (of list), which contains all possible combination of the pair $$(l, r)$$ used during the encryption.

def generate_column(len_block):
for x in range(0, len_block - 1):
for y in range(x + 1, len_block):
yield (x, y)

def generate_indexes(len_block):
x = [generate_column(i) for i in range(2, len_block + 1)]
y = itertools.product(*x)
return y


### 3rd Problem

How many blocks there were at the start?

We don’t know, but we can presume that the flag was composed by a number of blocks between $$3$$ and $$10$$. So we start supposing that there were $$3$$ blocks and we reverse the function with all possible combination of $$(l, r)$$ of length $$3$$. If we don’t find the flag we try to increment the number to $$4$$ and so on.

for i in range(3, 9):
indexes = generate_indexes(i)
print("trying: " + str(i), end="\r")
for x in indexes:
try:
g = gantunex_solver(enc, x)
for h in g:
try:
print(long_to_bytes(h).decode(), end='')
except UnicodeDecodeError:
continue
print("")
except ValueError:
continue


### 4th Problem

How can we know that the decrypted content is the flag?

We can’t be sure, but we know that the flag starts with SUSEC{, so we try to print all the decrypted values that start with SUSEC{.

## Exploit

#!/usr/bin/python

from Crypto.Util.number import *
import itertools
from z3 import *

def gantunex_solver(a, indexes):
g = [a]
for i in range(len(indexes)):
l = indexes[i][0]
r = indexes[i][1]
x, y = reverse_2(g.pop(0))
g.insert(l, x)
g.insert(r, y)
if b'SUSEC{' != long_to_bytes(g[0]):
raise ValueError
return g

def case_2(a, b):
x, y = a, b
if x < y:
return y ** 2 + x
else:
return x ** 2 + x + y

def reverse_2(z):
s_1 = Solver()
x = Int('x')
y = Int('y')
s_1.add(z == x ** 2 + x + y, x > y, x > 0, y > 0)
if s_1.check() == sat:
return (s_1.model()[x].as_long(), s_1.model()[y].as_long())
s_2 = Solver()
s_2.add(z == y ** 2 + x, x < y, x > 0, y > 0)
if s_2.check() == sat:
return (s_2.model()[x].as_long(), s_2.model()[y].as_long())
raise ValueError

def generate_column(len_block):
for x in range(0, len_block - 1):
for y in range(x + 1, len_block):
yield (x, y)

def generate_indexes(len_block):
# a = generate_column(2)
x = [generate_column(i) for i in range(2, len_block + 1)]
y = itertools.product(*x)
return y

def main():
enc = bytes_to_long(open('./flag.enc', 'rb').read())
for i in range(3, 9):
indexes = generate_indexes(i)
print("trying: " + str(i), end="\r")
for x in indexes:
try:
g = gantunex_solver(enc, x)
for h in g:
try:
print(long_to_bytes(h).decode(), end='')
except UnicodeDecodeError:
continue
print("")
except ValueError:
continue

if __name__ == '__main__':
main()


After a while we got the flag:

## Flag

SUSEC{m0rE_eL39An7_P41RING_fUnct1ON}