Данная задача была на отборе в ШкИБ в 2023 году. Время шло, однако никто не опубликовал ни одного райтапа, поэтому публикую решение сохранившейся задачи с того отбора.

В данной задаче нам дан файл flag_checker.py, который проверяет введенный флаг на корректность. Эта простая задача: нужно просто вытащить сам флаг.

Начинаем анализ последовательно с функции "main":

if __name__ == "__main__":
    main(sys.argv)

Рассмотрим её. Прежде всего в ней проверяется, что пользователь передал собственный флаг для сравнения:

    print("Hello there! Welcome to flag checker v1.0!")
    if len(argv) < 2:
        print("Usage: <flag>")
        return

Если флаг передан, он преобразуется в список байт:

user_flag = [ord(x) for x in argv[1]]

После этого проверяется, что его длина совпадает с длиной флага. Из этого можно сделать предварительный вывод, что все дальнейшие действия с флагом не меняют его длину:

if len(user_flag) != len(FLAG):
        print("Wrong flag length!")
        return

Далее происходит шифрование введённого пользователем флага:

    a = []
        for i in range(0, 5):
            for _ in range(0, i):
                a.append(user_flag)
            user_flag = encrypt(user_flag)

И затем результат просто сравнивается с эталоном. В зависимости от этого выводится результат:

    if user_flag == FLAG:
        print("Correct :)")
    else:
        print("Wrong :(")
    return

Итак, пока мы узнали следующее:

1. при запуске программы пользователь предлагает свой вариант флага;
2. он как-то преобразуется, причём, скорее всего, без изменения длины;
3. после этого он сравнивается с «зашифрованным заранее» эталоном, и если они совпадают, значит, пользователь угадал правильный флаг.

Теперь рассмотрим подробнее, как происходит процесс шифрования флага. Прежде всего обратим внимание на главные строки:

    for i in range(0, 5):
        user_flag = encrypt(user_flag)

То есть флаг шифруется пятикратным последовательным применением функции "encrypt". Однако зачем же нужны остальные строки? Они создают пустой список "a", а затем добавляют в него результаты шифрования - сначала ноль, потом одну, потом две, три и, наконец, четыре копии. Этот список и всё, что в него добавляется, кажется нигде не используемым. Однако вряд ли эти строки добавлены в программу по ошибке. Скорее всего, они оказывают какое-то «неявное» действие на шифрование, которое нам предстоит определить позднее.

Итак, что мы знаем:

• выбранный флаг шифруется пять раз одной и той же функцией "encrypt", которой передаётся текущий флаг;
• кроме этого, существует вроде бы не используемый список, куда после каждого раунда шифрования добавляется его результат, причём разное количество раз (0, 1, 2, 3, 4).

После этого очевидно, что нам необходимо рассмотреть функцию "encrypt", и если мы сможем обратить её, то есть сделать её работу в обратном порядке, мы получим исходный флаг.

Однако прежде чем смотреть, что именно делает эта функция, мы видим, что над ней стоит декоратор:

@with_magic
def encrypt(user_flag):

Он говорит о том, что прежде, чем что-то шифровать, вызывается функция "with_magic", которая дополнительно меняет данные ключа. То есть всё происходит так:

• выбранный флаг шифруется пять раз одной и той же функцией "encrypt";
• однако прежде, чем функция "encrypt" шифрует каким-то способом наш флаг, вызывается функция "with_magic", которая, видимо, шифрует его дополнительно;
• таким образом, можно сказать, что наш флаг шифруется десять раз - попеременно функциями "with_magic", "encrypt", "with_magic", "encrypt" и так далее;
• расшифровывать будем в обратном порядке - сначала вызывать функцию "encrypt" (её придётся изменить, чтобы она работала в обратном порядке), а затем "with_magic". Однако так как декораторы всегда вызываются до функции, придётся убрать декоратор и просто вызвать её в конце функции расшифровки.

Так как декоратор "with_magic" вызывается первым, разберём, что делает он. Ему передаётся параметром функция (в нашем случае - "encrypt", к которой декоратор применён), и он вызывает внутри себя функцию "wrapper":

def with_magic(func):
...
    return wrapper

Сама функция вначале проверяет, сколько аргументов ей передали. Если ни одного, то просто ничего не делает и вызывает саму функцию. Однако функция "encrypt" всегда передает флаг.

    def wrapper(*args, **kwargs):
        if len(args) == 0:
            return func(*args, **kwargs)

Далее происходит получение магического значения n = get_magic_value(id(args[0])).
И это магическое значение зависит от первого аргумента, то есть флага. К нему применяется функция id, которая позволяет получить уникальный идентификатор (представляющий собой большое число). Позже мы рассмотрим, как именно получается это магическое значение, а пока посмотрим, что с ним происходит далее:

new_args = (transform(args[0], n), *args[1:])
return func(*new_args, **kwargs)

Аргументы функции изменяются через "transform", а уже далее этот измененный флаг передается самой функции "encrypt".

Итак, шифрование выглядит следующим образом:

• выбранный флаг шифруется пять раз одним и тем же образом;
• на каждом раунде шифрования происходит получение «магического числа», которое каким-то образом зависит от нашего флага (точнее, от его уникального идентификатора);
• далее флаг меняется через "transform", которая от этого магического числа и зависит;
• в конце флаг шифруется функцией encrypt.

Рассмотрим функцию "transform":

def transform(seq, n):
    return seq[n:] + seq[:n]

где:
seq - наш текущий флаг,
n - определённое «магическое число».
Можно увидеть, что наш флаг просто перестраивается. Если пронумеровать символы нашего флага от 0 до i, то после данной функции в изменённом флаге вначале будут идти символы от n до i, а потом от 0 до n-1. То есть можно сказать, что наш флаг как бы разрезается на две части между символами n-1 и n, затем эти части меняются местами, и строка склеивается заново.


Например, при i = 8, n = 5 строка 012345678 поменяется на 567801234.

Пишем обратную функцию

def inverse_transform(seq, n):
    return seq[-n:] + seq[:len(seq)-n]

Ее мы будем использовать в программе для дешифровки. Она делает все ровно наоборот – вначале берет последних n символов (в примере ваше – 01234), а затем берет первые len(seq)-n символов, то есть, в случае нашего примера, первые 9-5=4 символа, то есть, 5678. В итоге получается изначальная строка – 012345678.
Однако нам предстоит разобраться, откуда же берется это магическое число n. А его получает функция get_magic_value, которой передается уникальный идентификатор нашего флага

def get_magic_value(object_id):
    return struct.unpack(ULONG_CHAR, ctypes.string_at(object_id, LONG_LEN))[0]

Что делает данная функция? Она вызывает функцию ctypes.string_at, а ctypes.string_at читает сырые байты по заданному адресу памяти, и если указан size, возвращает ровно столько байт. В CPython id(x) - это адрес объекта в памяти, а любой объект начинается со служебного заголовка, первое поле которого - счётчик ссылок ob_refcnt. Счётчик увеличивается, когда на объект сохраняется новая ссылка, и уменьшается, когда ссылка удаляется; при нуле объект освобождается.
Поэтому get_magic_value(id(user_flag)) фактически читает ob_refcnt строки как число. А строки

for _ in range(0, i):
    a.append(user_flag)

добавляют в список a от 0 до 4 дополнительных ссылок на тот же объект-строку. Каждое добавление увеличивает ob_refcnt на единицу, поэтому на каждом i магическое число равно base + i. Значит, последовательность магических чисел имеет вид base, base+1, …, base+4, а при дешифровке идёт в обратном порядке: base+4, base+3, …, base. Если в цикле дешифровки i = 0..4, то можно перебирать n = C - i, где C - небольшое число (5, 6, 7, 8, …), либо просто перебрать весь небольшой диапазон кандидатов. Для C = 7 это и даёт 7 - i: 7, 6, 5, 4, 3.
Итак, перед каждым вызовом encrypt флаг разрезается в позиции n и две части меняются местами; при дешифровке применяется обратная перестановка seq[-n:] + seq[:len(seq)-n], а n подбирается перебором небольшого начального значения счётчика ссылок.


Осталось разобраться с функцией encrypt. Она начинается с какой-то строки под названием code, состоящей из 16-ричных символов:

def encrypt(user_flag):
    code = b"\x89\xc8\xb3\x04\xf6\xf3\x31\xc9\x88\xc1\x89\xf7\xad\xc1\xc0\x03\x35\x84\xce\x5b\x3f\xab\xe2\xf4"

Далее в функции происходит работа с библиотекой Unicorn:

    try:
        mu = Uc(UC_ARCH_X86, UC_MODE_32)

Если посмотреть описание данной библиотеки, то можно узнать, что она предоставляет возможность эмулировать выполнение команд на процессоре. Поэтому:

• UC_ARCH_X86 – тип эмулированного процессора – X86
• UC_MODE_32 – 32-битный режим
• code – сам код, который выполняется (в 16-ричном виде)

Далее выделяется необходимое количество места под выполнение программы:

MEMSIZE = 0x2000
mu.mem_map(0, MEMSIZE)

С нулевого адреса записывается наша программа mu.mem_write(0, code)

В область данных записывается флаг:

FLAG_ADDR = MEMSIZE - len(FLAG)
mu.mem_write(FLAG_ADDR, bytes(user_flag))

Далее настраиваются регистры – указатель стека (на случай вызова подпрограмм), регистр ESI, указывающий на наш флаг, и регистр ECX, содержащий длину флага:

mu.reg_write(UC_X86_REG_ESP, STACK_ADDR)
mu.reg_write(UC_X86_REG_ESI, FLAG_ADDR)
mu.reg_write(UC_X86_REG_ECX, len(FLAG))

Далее наша программа выполняется, и измененный результат берется обратно в переменную user_flag, после чего возвращается:

        mu.emu_start(0, len(code))
        user_flag = mu.mem_read(FLAG_ADDR, len(FLAG))

    except UcError as e:
        print("ERROR: %s" % e)

    return user_flag

Итак, мы выяснили, что:

• Функция encrypt использует библиотеку unicorn, чтобы эмулировать процессор X86 в 32-битном режиме
• Он выполняет программу из переменной code, которая изменяет переданный ей флаг
• В регистре ESI содержится адрес флага, а в регистре ECX – его длина

Попробуем расшифровать программу, записанную в переменной code. Для этого перейдем на сайт Online x86 and x64 Intel Instruction Assembler, введем содержимое переменной code, и получим:

Итак, перед нами – листинг на языке ассемблера X86. Первые три команды делят содержимое регистра ECX (то есть, длины флага) на 4 (очевидно, мы будем работать сразу с группами по 4 байта, и их количество будет в 4 раза меньше исходной длины).
Результат данной операции помещается в AL, а нам нужно разместить его обратно в ECX.
В регистре ESI у нас адрес нашего флага - оттуда мы будем брать данные для шифрования, но нужно еще адрес, куда эти зашифрованные данные мы будем помещать. Сделаем EDI = ESI.

Теперь происходит собственно шифрование. Мы берём 4 байта ключа командой LODS, меняем их командами ROL/XOR, а затем сохраняем обратно с помощью команды STOS. Это продолжается столько раз, какое число записано в ECX (а именно длина нашего флага, делённая на 4).

Итак, мы выяснили, что всё шифрование заключается в следующем:

• берутся каждые 4 байта флага (в регистр EAX);
• выполняется команда ROL EAX, 0x03 (Команда ROL EAX, 03 сдвигает регистр EAX на 3 бита влево (ROtate Left));
• выполняется команда XOR EAX, 0x3f5bce84 (Команда XOR EAX, 0x3f5bce84 выполняет XOR-операцию с регистром EAX и данной константой);
• получившиеся 4 байта сохраняются обратно на то же место.

Предположим, что можно перевернуть данную операцию, вообще не меняя функции encrypt. Достаточно поменять лишь две команды, выполняющие шифрование, чтобы они работали наоборот + сдвиг влево (ROL) нужно заменить на сдвиг вправо (ROR)

Мы получаем следующий результат:

В итоге напишем программу для расшифровки сообщения. Прежде всего, нам нужно узнать константу, от которой будет зависеть магическое число. Просто переберем ее в цикле for. В цикле будем пять раз (как и в оригинале) расшифровывать наш флаг и выводить на экран:

При шифровании вначале выполнялась функция with_magic, а затем encrypt, но при расшифровке наоборот - сначала encrypt, поэтому мы уберем с нее декоратор, а также добавим ей еще один параметр - магическое число, чтобы не нужно было самостоятельно его рассчитывать:

Сама функция практически такая же, как и раньше, кроме двух изменений. Во-первых, изменена переменная code на то значение, что мы получили выше:

Во-вторых, в конце нужно расшифровать то, что ранее зашифровывал декоратор with_magic.
Саму функцию расшифровки мы уже наметили при описании процесса шифрования - она выглядит следующим образом:

То есть, можно сказать, что мы просто «развернули» процесс шифрования в обратную сторону, и теперь мы расшифровываем итоговый результат. Запускаем нашу программу:

Проверим флаг, запустив чекер:

Флаг найден верно.

 

Отличная работа. Есть ссылка на задание, чтобы посмотреть?

 

Ссылки на задание нет, но сохранился исходный код file_checker.py. Я его докинул в формате .txt