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}