На выходных я имел удовольствие принять участие в ежегодном Google CTF, или, точнее, в части квеста для начинающих CTF. По большей части мне удавалось решать проблемы самостоятельно, но я должен сказать, что некоторые из них были сложными. Жители сервера Discord Джона Хаммонда (https://discord.gg/Gw9gSMV) оказали большую помощь в решении некоторых наиболее загадочных задач.

Говоря о головоломках, сегодня я хочу погрузиться в одно из испытаний, которое я считаю одним из самых сложных и самых интересных испытаний в квесте для начинающих. Эта задача называлась FriendSpaceBookPlusAllAccessRedPremium.com и была классифицирована как реверсивная. Честно говоря, большинство людей просто назвали его Emoji Reverser по причинам, которые вы увидите через минуту. Я сделал почти все следующие шаги в VSCode, используя его отладчик на виртуальной машине Kali Linux.

Общие сведения о программе

Задача состояла из zip с двумя файлами, vm.py и программой. Vm.py была простой программой на основе стека, которая принимала программный файл в качестве аргумента. Прежде чем я углублюсь в это, я хочу немного объяснить о программах на основе стека, так как я не совсем понял, как они решают эту задачу.

Основное объяснение (скопировано с https://www.pythoncentral.io/stack-tutorial-python-implementation/) заключается в том, что программа Python на основе стека состоит из класса Stack (в данном случае VM) и различных методы, используемые стеком для выполнения операций над данными внутри стека. Данные могут быть добавлены (протолкнуты) или удалены (извлечены) из стека, но только последняя часть стека и только одна часть за раз. Хотя я не уверен на 100%, из того, что я прочитал, основная причина использования стека, а не чего-то вроде списка, заключается в том, что правильные стеки могут работать намного быстрее, если нет необходимости в произвольном доступе к элементам.

У Vm.py было множество второстепенных методов, основные из которых показаны на следующем рисунке:

Конечно, вы можете заметить, что вместо имен функций или переменных используются эмодзи. Как и следовало ожидать, последующий программный файл полностью написан смайликами.

Это, конечно, нестандартный подход, но на самом деле он ничем не отличается от простого кодирования файла программы во что-то, кроме UTF-8.

Первым шагом, который я предпринял, было просто запустить программу как есть. Я использовал Kali Linux для этой задачи, поскольку Windows выдает ошибку charmap.

Программа распечатала URL-адрес, рассчитанный на основе ранее помещенных в стек значений. Это объясняло подход на основе стека, поскольку данные, которые необходимо было совместно использовать, были известным и постоянным фактором.

Программа вытащила первые значения очень быстро, но замедлилась после n, которую вы видите. Если вы были достаточно терпеливы (или просто пошли пообедать), вы могли подождать, пока будет показана большая часть URL-адреса, и угадать это значение: http://emoji-t0anaxnr3nacpt4na.web.ctfcompetition.com/, которое в классическом стиле было гигантская кроличья нора, заполненная ссылками на изображения кошек. Реальный ответ заключался в понимании программы и поиске способа ускорить вычисление значений, чтобы получить полный URL-адрес.

Разбивка кода

Первым шагом, который я предпринял, было декодирование файла программы с помощью ключа, предоставленного в vm.py. Для большинства изображений, показанных в этой статье, они будут отображать только часть программы, так как она состоит из более чем 100 строк.

Здесь вы можете получить пример стека, о котором я упоминал ранее. Числа в первых строках загружаются в стек для дальнейшего использования. Строки ниже казались почти простой сборкой, где выполняется последовательность шагов. Я потратил некоторое время на прослеживание шагов, но по большей части это просто набор математических процедур, и непривычность подхода на основе стека быстро ошеломила меня.

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

Для начала мне нужно было выяснить, как программа печатала, что было прямолинейно: она просто вызывала chr() для последнего значения в стеке. Описание Chr выглядит следующим образом: Метод chr() возвращает символ (строку) из целого числа (представляет собой кодовую точку Unicode символа).

В заключение в стек загружается ряд целых чисел, и по мере продвижения vm.py над ними выполняется ряд математических процедур, чтобы в конечном итоге получить правильное значение для вызова chr().

Хорошо, давайте работать в обратном порядке. В строке 47 программы есть вызов print_top. Однако прямо перед этим есть вызов XOR, который делает именно то, на что он похож, берет последние 2 значения стека, XOR их и помещает возвращенное значение в стек. Таким образом, значение, переданное в chr() и, следовательно, записанное, будет результатом этого XOR. Я не собираюсь вдаваться в подробности XOR, но ключевая идея, которую нужно знать об этом, заключается в том, что если вы знаете любые два значения a ^ b = c, то вы можете найти недостающее, независимо от того, какие 2 у вас есть .

Это означает, что нам просто нужно выяснить, какие два значения передаются в стеке во время записи, что означает время отладчика. Как я уже говорил в начале статьи, я использовал отладчик VSCode, так как в нем есть плагин для работы со скриптами Python. Я никогда не использовал VSCode, но обнаружил, что его легко настроить и использовать, и я обязательно буду использовать его в будущем. Поскольку ключевым моментом времени, который меня волновал, была операция XOR, я установил там точку останова и наблюдал за переменной стека:

В итоге я выполнил первые 5 шагов программы, скопировав стек и записав его в файл Excel, чтобы его было легко просмотреть. В этот момент программа написала «http:»

Вот расшифровка первых 5 букв.

Итак, на этом этапе немного сложно увидеть закономерность. Очевидно, что номера стеков каждый раз подвергаются операции XOR с разными значениями, и похоже, что это простое число. Может быть, это просто XOR путем увеличения простых чисел?

Давайте сделаем следующие 5 значений и посмотрим.

Какого черта? Мы прошли весь путь от XOR с 11 до 101? И почему кажется, что числа увеличиваются на произвольные величины?

Итак, это тот момент, когда после еще нескольких попыток и короткой прогулки я заметил закономерность. Увеличение зеркально отраженных простых чисел, чтобы числа, которые при переворачивании оставались теми же, поэтому существует большой перейти с 11 на 101. Стек был загружен значениями, и ключ должен был увеличить число простых чисел и использовать следующее зеркальное для XOR правильного значения.

Я не знаю, кто руководил созданием этого со стороны Google, но я был впечатлен мыслью, которая вошла в это. Почитав программу еще немного, стало ясно, что программа вычисляет простые числа для каждой буквы. Хорошо, когда вы просто делаете 11, не так хорошо, когда вы добираетесь до 100 000, что и вызвало замедление работы программы.

В качестве резервной копии программный файл был разделен на 3 отдельных части стека или секции, первая из которых имела номера от 106 до 17 488, вторая — от 93 766 до 98 426, а последняя — от 9 916 239 до 100 030 045. . Как работает XOR, чтобы преобразовать младшие числа, такие как 47, в chr() в читаемые значения, «ключ» XOR должен быть примерно того же размера, что и значение стека.

Некоторое время я не замечал, что существует переменная с именем accumulator2, в которую загружается число, соответствующее начальному количеству зеркальных простых чисел для каждой секции. Покажу на примере второго «раздела» стека:

Как вы можете видеть, значения стека находятся в диапазоне от 93 766 до 98 426, а аккумулятор2 загружен 99. Это означает, что для декодирования этого раздела нам нужно начать с 99-го найденного основного зеркала.

Что ж, к сожалению для нас с вами, нет готовых списков зеркальных простых чисел, поэтому пришло время вырваться из верного Python и написать реальное решение.

Решение

Мое решение началось с создания функции для проверки того, является ли число простым. В Интернете есть много примеров, поэтому я просто взял тот, в котором говорилось, что это быстро. После этого я создал еще одну функцию, чтобы проверить, является ли число зеркальным.

Первоначально я пробовал упорядочивать числа в диапазоне, проверяя, являются ли они простыми, а затем проверяя, являются ли они зеркальными. Я быстро понял, что вычисления для проверки того, является ли число простым, очень длинны для чисел в 100 000 000, которые нам пришлось проверять для третьего раздела стека. Итак, я пошел другим путем, проверяя, зеркально ли это число, а затем проверяя, является ли это число простым, что в итоге оказалось значительно быстрее. Я написал отдельную программу от моей основной, чтобы найти необходимые простые числа, затем сохранил значения и жестко закодировал их в основном решении, так как я не хотел вычислять простые числа несколько раз.

Вот полный скрипт для вычисления простых чисел, необходимых для декодирования (он закодирован с учетом особенностей второго «раздела» стека, начиная с 99):

Вывод:

Как только я сгенерировал простые числа для каждого раздела, пришло время декодировать стек и распечатать URL-адрес!

Я покажу здесь полный код, но он просто пробежался по каждому разделу, выполнил операцию XOR над правильными значениями и распечатал результаты, а также сохранил их в массив.

Его, конечно, можно было почистить, поместив штрих и буквы в один список, но для меня это сработало достаточно хорошо. Конечный результат выглядел примерно так (значения XOR я поставил туда для отладки, плюс мне понравилось, как это выглядит)

Полный URL-адрес ведет на другую веб-страницу с несколькими изображениями, одно из которых содержит флаг!

Вывод

Эта задача была определением того, что на первый взгляд кажется невероятно сложным и сложным, но если вы не торопитесь и действительно пытаетесь понять, что происходит за кулисами, у нее есть четкий путь к ее решению. Реверсирование в целом — это то, над улучшением которого я недавно работал, и в сочетании со стековым методом лично для меня эта задача усложнилась, хотя я уверен, что для многих более опытных хакеров используемый метод будет довольно похож на другие программы, которые пытаются скрыть вредоносное ПО, и поэтому его будет легко распознать.