sugar free candies

#

Подготовлено: rasti

Автор задания: 0x50r4

Уровень сложности: Очень легко

Описание

#

• Годами в воздухе накануне 31 октября раздавались странные сигналы. Кто‑то говорил, что это голос древней ведьмы, другие верили, что это послание от чего‑то куда более тёмного. Криптическое сообщение, разбитое на три части, перехватила отважная группа сельчан. Легенда говорила о сделке между ведьмой и теневым созданием, но истинный замысел их тайны могли раскрыть лишь те, кто хватится её расшифровать до полуночи, когда занавесь между мирами истончится.

В таске дано два файла:

• source.py : шифрует секретное сообщение в шифротекст
• output.txt : сам по себе файл с защифрованным сообщением

Анализ исходного кода

#

from Crypto.Util.number import bytes_to_long

FLAG = open("flag.txt", "rb").read()

step = len(FLAG) // 3
candies = [bytes_to_long(FLAG[i:i+step]) for i in range(0, len(FLAG), step)]

cnd1, cnd2, cnd3 = candies

with open('output.tcnd1t', 'w') as f:
    f.write(f'v1 = {cnd1**3 + cnd3**2 + cnd2}\n')
    f.write(f'v2 = {cnd2**3 + cnd1**2 + cnd3}\n')
    f.write(f'v3 = {cnd3**3 + cnd2**2 + cnd1}\n')
    f.write(f'v4 = {cnd1 + cnd2 + cnd3}\n')

Кратко, что здесь происходит:

• читает флаг из flag.txt, который является секретным и не предоставлен нам
• разделяет его на 3 части, которые записаны в виде cnd1, cnd2, и cnd3 соответственно. Каждая часть переводится в числовое представление
• между частями вычисляются четыре отношения и результат записывается в файл output.txt.

Решение

#

Нужно решить систему из трёх неизвестных, заданную четырьмя уравнениями. Поскольку количество неизвестных меньше количества уравнений, гарантировано, что существует решение (x, y, z) = (x0, y0, z0). Хотя три уравнения также обеспечили бы единственное решение.

Проблема в том, что числа велики, а уравнения нелинейны, поэтому решить это вручную очень сложно. Поискав по запросу python solve equations вы натолкнётесь на библиотеку SymPy. В CTF чаще используется библиотека SageMath, поэтому мы отдадим ей предпочтение. Также существуют онлайн‑решатели уравнений, которые тоже подойдут.

Сначала напишем функцию, которая создаёт и возвращает три переменные, по одной для каждой части флага. Из-за использования bytes_to_long мы знаем, что они должны быть целыми числами, поэтому нас интересуют только решения в множестве целых чисел $\mathbb{Z}$. В SageMath такие переменные можно определить с помощью функции var().

from sage.all import *

def create_variables():
	x,y,z = var('x,y,z', domain=ZZ)
    return x,y,z

Для решения системы будем использовать SageMath функцию solve() . Эта функция получает список уравнений и переменные, для которых нужно найти решение. Давайте напишем функцию, которая удобно возвращает решения этих уравнений.

def solve_system(x, y, z, v1, v2, v3, v4):
    return solve([
            x**3 + z**2 + y == v1,
            y**3 + x**2 + z == v2,
            z**3 + y**2 + x == v3,
            x + y + z == v4
        ], x, y, z, solution_dict=True)[0]

Это работает потому что выражения вида x3 + z2 + y == v1 и x y z представляют собой символьные объекты sage.symbolic.expression.Expression с перегруженными операторами благодаря созданию через var().

Мы также выбираем формат словаря для возвращаемых решений, чтобы упростить их разбор.

Имея решения, мы можем восстановить флаг так:

from Crypto.Util.number import long_to_bytes

def get_flag(sols):
    return b''.join([
        long_to_bytes(int(n))
        for n in [sols[x], sols[y], sols[z]]
    ])

Получение флага

exec(open('output.txt').read())

def pwn():
    x, y, z = create_variables()
    sols = solve_system(x, y, z)
    flag = get_flag(sols)
    print(flag)

if __name__ == '__main__':
	pwn()