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:
- Divide the flag in blocks, the number of blocks is
len(flag) // 6. - For each block, convert the block value to int (
bytes->int). - 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:
- Iterate from \(i = 0\) to \(len(x) - 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\).
- Generate \(g\) = case_2(x[l], x[r]).
- Reconstruct \(x\) such that x = g + x[:l] + x[l + 1:r] + x[r + 1:].
- Increment \(i\) and continue.
- 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}