Вступление

С 27 по 29 августа 2021 года в онлайн-формате проходило соревнование YauzaCTF. Соревнование проводилось в формате Task-Based, принять участие могла любая команда, желающая попробовать свои силы. Участникам предстояло в течение 48 часов решить задания следующих категорий: web, reverse, PWN, forensics, crypto, OSINT, joy, hardware, pentest и emulation.

Команде Raccoon Security было предложено разработать собственное задание для соревнований. В результате мозгового штурма и нескольких дней кропотливой работы была придумана задача, условие и решение которой мы приведем в данной статье.

Предупреждение! Далее следует лонгрид про нули и единицы (в прямом смысле).

Текст задания

Ривенделл. Третья эпоха Арды

Очередным солнечным утром в Ривенделле Бильбо проснулся с ощущением спокойного дня, в который он сможет продолжить писать свои мемуары. Однако, снова приступив к работе, он был ошеломлен, увидев перед собой страницы, испещренные непонятными символами вместо своего красивого хоббитского почерка. Сломя голову Бильбо побежал к Элронду.

Элронд понял, что данный инцидент является темными делишками орочьих диверсантов. Для осуществления своего плана они использовали древнее устройство кодирования MEL-KOR. Храбрость эльфийской разведки помогла заполучить один образец устройства, благодаря чему был проведен ряд исследований. Выяснилось, что используется архитектура фон Эльфмана, очень похожая на разработанную морийскими гномами «Кхазад86», но длина инструкций одинакова и не кратна восьми битам. Также вечным эльфийским умам без труда удалось понять, что в бездарном орочьем поделии всего две функции, первая из которых находится в самом начале прошивки.

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

Бильбо разбит и опечален, и только мы с вами сможем помочь ему восстановить потерянную часть работы. Для этого он поделился с нами оставшимися от его мемуаров орочьими каракулями, а владыка Элронд предоставил прошивку MEL-KOR. Вперед!

Предполагаемый ход решения

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

Красным цветом на рисунке 1 обведена область, содержащая исполняемый код, синим – область, содержащая таблицу данных. Таблица с данными немного упростила задачу: поняли, что в исполняемом коде используется таблица Base-64. Мы предположили, что, скорее всего, в орочьем устройстве используется модификация алгоритма кодирования Base-64.

Отобразили фон Эльфмана в фон Неймана и поняли, какая используется архитектура, однако разрядность архитектуры неизвестна. Поэтому при анализе бинарного вида файла мы решили определить разрядность одной инструкции. Для анализа файла использовали утилиту SublimeText, в которой при помощи сдвига границ окна можно проверить выравнивание по последней строке.

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

В ходе проверки различных вариаций выравнивания пришли к выводу, что разрядность инструкции равна 20 бит. В данном случае нулевой бит всех команд, кроме одной, равен 0, поэтому нулевой бит каждой инструкции был отделен. Мы предположили, что данный бит с большой вероятностью имеет какое-то специальное назначение.

Далее мы перешли к определению длины опкода команд. По условию задачи предположительно используется 32 команды, однако длина опкода команд может быть как больше 5 бит, необходимых для использования 32 команд, так и меньше 5 бит (в данном случае будет использоваться менее 32 команд). Мы предположили, что опкод находится в левой части инструкции и начинается непосредственно после нулевого бита «специального назначения». Также визуально была определена граница справа для опкода, в результате чего предполагаемая длина опкода – 7 бит.

После чего, написав программу на Python 3.9, мы проверили, насколько часто встречается каждый предполагаемый опкод. Результат приведен на рисунке 4.

Самыми популярными предполагаемыми опкодами являются 0000010 и 0000110. Мы решили проверить, как меняется статистика при сдвиге правой границы опкода вправо и влево. По полученным результатам стало понятно, что частота инструкций, которые являлись самыми популярными при предполагаемой длине опкода 7 бит, не изменяется при предполагаемой длине опкода 5–8 бит. Однако при 4 и 9 битах длины количество повторений начинает изменяться, можно предположить, что граница опкода находится в пределах 8 бит, а далее уже (вероятно) идут аргументы.

Если рассматривать опкоды длиной 5 бит, на первое место по количеству повторений выходит строка 00010 с заметным отрывом: количество повторений данной строки – 116, в то время как следующая за ней по популярности строка встречается 81 раз. Исходя из предполагаемого общего количества разнообразных инструкций и заметного выделения строки 00010, мы предположили:

1. длина опкода инструкции – 5 бит;

2. 00010 является опкодом команды MOV, т.к. в архитектуре x86 данная команда является наиболее популярной.

Следовательно, две оставшиеся популярные строки 00000 и 00001 – это команды PUSH и POP. Строка 00000, которая появляется в самом начале кода (вторая инструкция), в тексте всего кода встречается чаще всех остальных, поэтому мы пришли к выводу, что именно этот опкод относится к команде PUSH. С учетом того, как менялась статистика повторений различных строк (предполагаемых опкодов), возникла мысль, что следующие 3 бита за опкодом представляют собой что-то, связанное с аргументом, но при этом не являются самим аргументом.

Предположение о том, что данные биты не являются аргументом инструкции, возникло из-за идентичной статистики команд 00000 (PUSH) и 00001 (POP) на различных длинах проверки опкода в диапазоне от 5 до 8 бит. Данные команды могут принимать различные аргументы, а тип аргументов, скорее всего, будет идентичным.

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

Рассмотрев различные варианты, решили, что данные структуры отвечают за формирование DWORD (00111) и WORD (10110), т.к., скорее всего, в данном коде должны использоваться константы размером 4 байта. Поскольку из 20 бит инструкции 9 бит уже были определены (0 бит – специальное значение, 1–5 бит – опкод команды, 6–8 бит – тип аргументов), то для аргументов оставалось 11 бит, что, вероятно, недостаточно для формирования DWORD или WORD у, кхм, Кхазад86.

Идея следующая: четыре подряд идущие идентичные команды – это запись 4 байт, составляющих вместе полноценный DWORD, аналогично с WORD. Ну а следующая за ними команда 01000, назовем ее MAKEDWORD, как раз собирает четыре части пазла в единую картину, в нашем случае – необходимую константу. Аналогично команду 10111 назовем MAKEWORD.

Единственное, что оставалось загадкой, – тип данных, используемый в данных инструкциях. Одним из аргументов, вероятно, является 8-битная константа, но неизвестно, присутствует ли второй аргумент. Вопрос в том, сохраняют ли команды 00111 и 10110 константы в регистры или нет. Сомнения быстро развеялись при анализе первого же гаджета формирования DWORD-константы.

В случае если константа при записи занимает 8 бит из 11, отведенных под аргументы, то остаются еще 3 бита, которые могут использоваться для второго аргумента. Предположим, что команда DWORD записывает константы в регистры, тогда либо первые 3 бита, либо последние 3 бита должны отвечать за регистр, в который выполняется запись. Но если посмотреть на вторую и третью команды DWORD-структуры, представленной на рисунке 5, можно заметить, что и первые 3 бита и последние 3 бита (из 11 бит, отведенных под аргументы) совпадают. Тогда получается, что одно значение просто перезаписывается другим, это выглядит бесполезно с точки зрения формирования константы типа DWORD. В итоге получается, что предположение не подтвердилось и команда DWORD принимает один аргумент, являющийся константой. При этом опять возвращаясь к структуре, приведенной на рисунке 5, становится понятно, что в случае использования менее 11 бит, предположительно выделенных под аргументы, идет дополнение нулями с левой стороны.

Итак, подведем промежуточные итоги.  В таблице ниже привели, какие команды уже предположительно известны.

Также мы определили предположительную структуру построения инструкции. Так как архитектура должна каким-то образом кодировать тип аргументов инструкции, то возникает еще одно предположение. У всего блока инструкций DWORD, работающего с константами, одинаковый тип аргумента, а именно константа длиной 8 бит, поэтому предположим, что тип аргументов 110 – один аргумент – константа.

Нам известно, что команда MAKEDWORD записывает константу в регистр (выяснили, что для команды DWORD это было бы нелогично). В итоге мы пришли к тому, что тип аргументов 101, используемый в инструкциях с командой записи, – это один аргумент, являющийся регистром (reg32).

Предположим, что начало кода стандартное, т.е. первые две команды должны создавать кадр стека x86. Данными командами являются PUSH ebp и MOV ebp, esp. Сопоставив входной бинарный файл с уже известными нам командами, мы получили не совсем ожидаемый результат. Команда первой инструкции не является командой PUSH, однако команда второй инструкции – это PUSH, а третьей – MOV. Первая инструкция содержит опкод 11111. Из-за особенности ее расположения мы предположили, что 11111 является опкодом команды, которая просто выравнивает битность блоков кода (для возможности побайтовой, а не побитовой адресации). Примем ее за условный NOP.

Также благодаря стандартному «началу» кода, была получена новая информация:

• тип аргументов 000 ничего не принимает (noarg);

• тип аргументов 001 принимает на вход два 32-битных регистра (reg32 + reg32), при этом заняты последние(!) 6 бит аргумента;

• cудя по строкам 2 и 3, один регистр кодируется ровно тремя битами, при этом:

  • аргумент 110 – регистр ebp;

  • аргумент 111 – регистр esp.

После этого сразу стала понятна полная структура инструкции – sp_bit (1 бит) + cmd_op (5 бит) + argtype (3 бит) + dst + src (11 бит).

Также мы обратили внимание на инструкцию в строке 6 – операция с esp: раз угадали шапку х86, значит и место на стеке должно выделиться. Бывают разные операции для выделения места на стеке, но обычно это происходит с помощью команды sub. Но там точно нет разыменования, и если посмотреть на аргументы, то станет понятно, что тип аргумента 010 – это два аргумента, один из которых регистр без разыменования, а второй – 8-битная константа (reg32+imm8).

Значение константы в инструкции в строке 6 равно 0хA0. На битовую маску это не похоже, поэтому предположение о том, что 00011 – это опкод команды SUB становилось еще логичнее. Далее мы проверили все участки кода, в которых могла бы находиться команда SUB. По итогу везде, где предположительно используется SUB, в качестве аргументов используются либо два регистра (reg32+reg32), либо регистр и константа (reg32+imm8). Это не противоречит предположению, что 00011 – это опкод команды SUB.

Далее рассмотрели инструкцию в строке 9.

Обратили внимание на MOV с неизвестным типом аргументов 100. Видим, что первые биты аргумента точно значащие, т.к. это единицы. А такое может быть только при использовании регистра и 8-битной константы (imm8). Но такой тип аргумента уже есть. Стало понятно, либо это [reg32]+imm8, либо или reg32+[imm8]. Тип аргументов 100 также встречается в инструкции в строке 37. На основе значений констант в инструкции в строке 9 (0x0) и инструкции в строке 37 (0x41) было сделано предположение, что разыменование нулевого адреса в данной архитектуре возможно (т.к. началом кода является адрес 0x0).

Но зачем разыменовывать 0x41, ведь очевидно, что по данному адресу располагается исполняемый код? Если мы исполняемся с нулевого адреса, может ли адрес 0x41 быть началом какой-либо 20-битной инструкции? 65*8/20 – целое число, значит может. Решили посмотреть, где еще в коде встречается MOV с таким типом аргумента. Пришли к выводу, что варианта imm8 таких MOV всего два – 0х0 и 0х41. Других команд, использующих данный тип аргумента, найдено не было. Но отдельное внимание было уделено инструкциям в строках 7 и 10. В них мы видим PUSH ebp и POP ebp, т.е. сохранение регистра в стек и его восстановление. Вариант reg32+[imm8] становится совсем бессмысленным, поэтому предположили, что тип аргументов 100 – это разыменование регистра и 8-битная константа ([reg32]+imm8).

Далее решили рассмотреть инструкцию в строке 12.

Данная инструкция содержит пока что неизвестную операцию, принимающую регистр и константу как аргументы. Зато известен регистр, с которым выполняется операция. Также заметим, что инструкции на строках 11–17 снова сохраняют/восстанавливают ebp, значит над ним происходит spoil-операция. Вероятно, эти строки ограничивают гаджет, в котором активно используется ebp. Значит можно предположить, что инструкция в строке 13 в этом гаджете также использует ebp, а не просто константу. Старшие биты – три нуля, следовательно, они не обязательно значащие. Более того, видим картинку, похожую на reg32+reg32: все биты, за исключением последних шести, не обязательно значащие... А еще, если предположить, что это два регистра, то получается – это ebp и еще раз ebp, что неплохо ложится на логику гаджета.

Проверим себя, удастся ли нам найти инструкции, работающие с типом аргументов 011, где присутствует единица в первых 5 бит, отведенных под данные? Нет! Более того, команд MOV, использующих такой аргумент, насчиталось аж 40, и ни в одной из них наша теория о двух регистрах пока что не провалилась. А есть ли еще инструкции, использующие 011? Ни одной, зато 40 команд MOV. Все ведет к тому, что наиболее вероятный вариант – reg32+[reg32]. Такой вывод можно сделать исходя из инструкции в строке 14, т.к. при варианте [reg32]+reg32 сохранение ebp в регистр, кодирующийся нулем, имеет меньше смысла. Такое предположение сделали, т.к. выше нет ни формирования адреса в регистре 000, ни операций с ним. Примем наше предположение и вернемся к его исправлению, если встретим нелогичность или противоречие. Предположим, что тип аргументов 011 – это регистр и разыменование регистра (reg32+[reg32]).

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

При этом видно, что в данную инструкцию не передаются аргументы noarg. Таким образом, опкод команды RETURN – 11000. Если на самом деле представленный фрагмент орочьего машинного кода – это две функции, то логично было предположить, что где-то есть инструкция с командой CALL. Однако определить опкод команды CALL на данном этапе было невозможно.

Смотрим дальше: инструкции в строках 16–19 (рисунок 8) – снова гаджет с сохранением/восстановлением регистра через стек, только это регистр с кодом 000. С текущим прогрессом видим следующее: регистр сохраняется, далее следует инструкция, принимающая только константу (imm8), вслед за ней – перекладывание значения регистра 000 в регистр 010 и восстановление 000. Получается, что регистр 000 spoil-ился. Но инструкция 00101 не принимает регистр 000 в качестве аргумента, единственным ее аргументом является константа. Смотрим, что там за константа – 0x4. Можно предположить, что, скорее всего, 00101 является опкодом команды MUL, а регистр 000 – это eax. Смотрим, где еще используется опкод 00101 и нет ли тому противоречий – всего два раза в коде и всегда с константой в качестве аргумента.

Далее необходимо было проверить достоверность предположения, что регистр 000 – это eax. Если уж мы нашли x86-шапку, может eax используется в качестве регистра-хранителя возвращаемого значения? В конце каждой из двух функций присутствует spoil предполагаемого регистра eax. Предположение о том, что 000 – это eax, подтвердилось.

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

Что ж, полезной информации для раскручивания с каждой итерацией все меньше и меньше… Тогда на помощь пришла подсказка, размещенная в тексте задания. В самом начале нам была предоставлена информация о некоторых командах, используемых в коде. И когда был получен порядковый номер команды RETURN в тексте условия и сопоставлен с опкодом, то стало понятно, что это одно и то же значение. Решили сопоставить и остальные предоставленные команды с опкодами по их порядковому номеру. В таблице ниже представлен полученный результат.

Наступило отличное время для того, чтобы вернуться к предыдущим предположениям и выяснить, остались ли противоречия, нужно ли нам вернуться на несколько шагов назад?

С помощью полученных новых данных мы провели ряд подстановок:

• MUL был определен верно! Наши шансы все выше и выше.

• SAR имеет номер 9 или 01001, если начинать отсчет с нуля. Команда выполняет арифметический сдвиг вправо. Посмотрим, сохраняется ли логика для наших догадок. Везде reg32+imm8. Подходит, была произведена замена.

• Опкод команды TEST по орочьей документации равен 01011. Везде в качестве аргументов данной команды используется reg32+reg32 в связке с регистром eax. Ну очень похоже на то, что любят устраивать компиляторы x86. Поверили и заменили.

• CMOVS? Экзотично. Опкод у орков – 01100. Снова обратившись к нашим каракулям, нашли единственное совпадение (что грустно, это не дает новой информации). Используется тип аргументов tworegs в связке с регистрами eax и 011. Не противоречит conditional move, более того идет сразу же после TEST.

• DEC = 10011. Хорошая проверка, здесь должен быть только тип аргументов onereg. Так и есть! Пока все один к одному.

• CDQ = 10100. Аргумент должен быть noarg, и где-то рядом должен быть задействован регистр eax. Инструкция, использующая опкод 10100, и инструкция, находящаяся на две строки выше предыдущей, подтверждают догадки.

• JL, JZ, JNZ? Слава эльфийским разведчикам! С помощью такого даже начала просвечивать логика кода. Уже заранее доверяя (но проверяя), было решено подставить команды вместо опкодов 11010, 11100 и 11101 соответственно.

В итоге к данному моменту оставалось 12 неясных команд. Ниже в таблице представлена частота встреч данных опкодов в исходном коде.

Что с другими неясностями? Все еще неясен специальный бит в начале инструкций, а также неизвестен тип аргументов 111. Через тип аргументов «открывается» куда больше информации, поэтому в первую очередь мы решили попытаться определить его.

Просмотрев все инструкции с данным типом аргументов, заметили, что в большинстве случаев специальный бит используется командой MOV. При просмотре 11 бит аргументов нигде не нашли единиц в начале этих 11 бит. Значит, вероятнее всего, в качестве аргументов используется либо один, либо два регистра. Тип аргументов 101, предположительно (пока что это только подтверждалось), означает один регистр, т.е., скорее всего, используются два регистра. Это было подтверждено с помощью аргументов типа 00000110011: 5 незначащих бит и дважды по 3 значащих бита – регистры. Варианты reg32+reg32 и reg32+[reg32] уже определены, не хватало только одного варианта – [reg32]+reg32. Решили заменить значение типа аргументов 101 на [reg32]+reg32 и проанализировать полученный код. Во многих местах по итогу было видно инструкцию mov [reg32]+reg32 ebp, ebp, что являлось единственным логичным оставшимся вариантом с точки зрения команды MOV и двух одинаковых регистров.

Дальше делать было нечего, кроме как вернуться к неизвестным командам. Ситуация оказалась довольно запутанной и нетривиальной, единственным оставшимся вариантом был анализ статистики и контекста. К этому моменту стало понятно, что архитектура практически полностью идентична х86, только с добавлением команд DWORD, WORD, MAKEDWORD и MAKEWORD, т.е. добавлено несколько спецкоманд.

Обратимся к рисунку 10. Десятка лидеров среди команд, используемых в x86, согласно сайту strchr.com: mov, push, call, cmp, add, pop, lea, test, je, xor. Многовато не найдено из основных…

Мы решили начать с поиска наиболее простой, на наш взгляд, команды CALL. Нам известно, что в орочьем изделии всего две функции, поэтому одна из функций хотя бы раз вызывает другую. При этом возможны две вариации инструкции с командой CALL – это либо CALL imm8, либо CALL onereg. Но в Hex-редакторе было замечено, что размер кода равен 0x528 и для вызова по абсолютному адресу не хватит imm8, нужен imm16. Такого типа аргументов не имелось в принципе, в результате адрес должен получаться либо сложением (которое тоже, вероятно, не было найдено), либо MAKEWORD. Было принято решение искать команду CALL по данным признакам.

В результате недолгого поиска удалось подтвердить предположение:

В данном примере используется команда JL, а не CALL, однако смысл остается тем же. Стало понятно, что переходы в данной архитектуре осуществляются по абсолютным адресам и, более того, MAKEWORD зануляет остальные 16 бит регистра, чтобы ничего не сломалось при переходе. Было решено искать MAKEWORD и операцию с типом аргументов onereg после него. Нашлись опкоды 11001, 11011 и 11110. Анализировать начали  с опкода 11001.

Видим, что после команды 11001 следует команда NOP, мы пришли к выводу, что перед нами конец базового блока и начало нового, т.к. NOP, предположительно, служит для выравнивания базовых блоков в данном коде. Под команду CALL не подошло, но было выдвинуто предположение, что опкод 11001, скорее всего, обозначает условный или безусловный переход. Запомним данную информацию и перейдем к анализу опкода 11011.

Была найдена лишь одна инструкция с опкодом 11011. Аналогичному анализу подвергся опкод 11110.

Таковой оказался так же единственным в коде. Однако рядом с данной инструкцией нет выравнивания, и, скорее всего, это не конец базового блока. Помимо этого, на рисунке 15 видно, как выполняется работа со стеком (esp) до и после инструкции, а еще и работа с eax. Видим подготовку стека, а именно – sub esp, 8, затем PUSH двух 4-байтовых значений. После 11110 мы заметили инструкцию с опкодом команды 00100 с аргументами esp и 0x10. Скорее всего, 00100 является опкодом команды ADD. В итоге при поиске команды CALL (11110) была также обнаружена команда ADD (00100).

После этой маленькой победы необходимо было вернуться к опкодам 11001 и 11011, чтобы определить их возможное назначение. Опкод 11001 (рисунок 13), скорее всего, является опкодом команды JMP, т.к. собирается 16-битовый адрес и нет ни одной проверки условий. Мы, предположительно, нашли JMP.

Наконец обратили внимание на опкод 11011. Взяли адрес, разыменовали, положили в eax, сформировали константу, сделали неизвестную операцию. После всего этого стоит NOP, значит присутствует выравнивание блоков кода. Опкод 11011 больше всего похож на команды J(cond.) и CMP. CMP использует два аргумента, а вот J(cond.) – как раз один, что сразу отсеивает предположение о CMP.

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

В общем и целом, в данном коде нет особой разницы между ebx и edx, поэтому их коды можно перемешивать, как душе угодно. Но вот esi, edi и ecx могут служить первым аргументом, вторым аргументом и счетчиком для некоторых операций, как и eax+edi. Предположим, что порядок соответствует приведенному в таблице и что eax имеет код 000, а ebp и esp «тащатся в хвосте», то, если и есть необнаруженная до этого момента операция копирования, она будет рядом с использованием предполагаемых esi и edi. Поискав в наших нераскодированных инструкциях данный кусок кода, обнаружили следующее:

Наткнулись на ту самую инструкцию с уникальной единицей в начале. Увидели, что иcпользуются eax, предполагаемые ecx и edi, ориентируясь на х86, предположили, что команда 01010 – это подобие stos(w/d) со счетчиком в ecx, нулем в eax и неким адресом сначала в ebp, а потом в edi. После чего сразу раскрылась суть использования первого бита, который в данной команде принимает значение 1 единственный раз во всем коде – это, скорее всего, rep, заимствованный из x86.

После подстановки новых значений таблица с кодировкой регистров приобрела новый вид.

По итогу осталось семь неизвестных команд.

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

С самой первой строчки мы начали восстанавливать исходный код, используя уже подтвержденные нами предположения. И практически в самом начале кода наткнулись на интересный момент: сначала выполняется копирование данных из ecx в eax, затем неизвестная инструкция с опкодом команды 00110, не использующая в качестве аргумента регистр eax, а после – снова копирование данных из ecx в eax.

Получается, что неизвестная команда неявно использует регистр eax, иначе данная конструкция бессмысленна. После анализа статистики использования различных команд с неявным использованием регистра eax было сделано предположение, что 00110 является опкодом команды IMUL, т.к. команда MUL уже присутствовала и также подходила по своей логике. Следовательно, опкод IMUL отличается от опкода MUL всего на одну позицию. Данное утверждение нельзя назвать уверенным, однако все же лучше, чем ничего.

Также был найден гаджет с опкодами 01110 и 01101.

Инструкции с данными опкодами используют идентичный тип аргументов и сами аргументы. После анализа всего кода было определено, что данные команды чаще встречаются в паре, чем по отдельности. Определив все известные команды, выдвинули предположение, что где-то в данном коде скрываются такие команды, как AND, OR, NOT, а также, возможно, SHL или SHR. На основе этого предположения мы попробовали подставить все возможные комбинации и проследить, во что будет собираться гаджет.

Но по итогам проведенного анализа, мы поняли, что ошиблись. Проверив все наиболее вероятные команды (AND, OR, NOT), решили попробовать подставить SHL и SHR, и о чудо! Мы предполагали, что будет использоваться либо SHL, либо SHR, однако в данном коде используются оба. Гаджет собрался в полноценную команду MOVZX, что отлично вписалось в логику исходного кода. Получили, что 01110 – это опкод команды SHL, а 01101 – SHR. И опять же, подтверждение немного подкрепляется тем, что опкоды данных команд идут друг за другом. Оставалось еще четыре неизвестных опкода.

Из всех оставшихся ненайденных команд наиболее очевидно было присутствие команды AND. Возможно, архитектура не предусматривает использование данной команды, однако вероятность этого крайне мала ввиду схожести «Кхазад86» с архитектурой x86. В процессе анализа кода (в поисках команды AND) был найден интересный гаджет.

Изначально собирается константа, при этом она больше похожа на битовую маску, нежели на значение, использующееся как-либо по-другому. А если это маска, то логично предположить, что вслед за ее «сборкой» расположена команда XOR, AND или OR, при этом команды AND и XOR имели статистический приоритет. Тогда появились две ветки предположения:

1. 01111 – это AND;

2. 01111 – это XOR.

После них идет неизвестная команда, при этом принимающая один аргумент-регистр. Из ненайденных популярных команд с одним регистром остались команды NOT и INC. Однако сразу после них используется команда DEC, и тогда использование INC на строчку выше становится нелогичным. Из других неизвестных команд с одним аргументом-регистром были найдены инструкции с опкодом 10010, других найдено не было. Допустим, что INC в данном коде не применяется, и пока неизвестно, какая еще команда используется с одним аргументом-регистром. Но NOT с большой вероятностью используется, поэтому мы выделили два варианта, предполагаемого опкода данной команды – 10010 и 10001.

Из дальнейших вариантов анализа оставался только перебор. На входе четыре неизвестных опкода, три предположения про AND, XOR и NOT, а также предположение, что возможно используется команда OR. Мы запаслись терпением и проверили различные вариации команд и опкодов, при этом попутно проверяли логику получившихся блоков кода. Спустя полдня усердной работы мы установили, что код становится логичным, когда:

• 01111 – AND;

• 10001 – NOT;

• 10000 – OR.

Ура! Бильбо почти доволен. Однако нас сильно удивило отсутствие команды XOR. Что оставалось:

• одна неизвестная команда с опкодом 10010;

• определить stos(w/d) – три варианта;

• определить условие J(cond.) с опкодом 11011.

Самым сложным было определить команду с опкодом 10010, которая на вход принимает один регистр, что для команды XOR (наличие которой предполагалось в коде) не свойственно. Информации для новых предположений не оставалось, поэтому пришлось воспользоваться исключительно статистикой и надеяться, что она не подведет. Было решено, что 10010 – это все же опкод команды INC.

Далее посредством брутфорса установили, что 01010 – это опкод команды STOSD. Осталось определить условие для команды 11011. Времени оставалось мало, и мы начали все переписывать на С++. Решили, что условие даст о себе знать, как только мы до него дойдем. Так и получилось. После того как восстановили весь исходный код, несложно было догадаться, с каким условием необходимо осуществлять прыжок: 01010 – это опкод команды JLE. Еще и опкод данной инструкции располагается рядом с JL.

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

Восстановив предполагаемый исходный код, стали разбираться, как написать алгоритм декодирования. Восстановленный алгоритм имел значительные отличия от стандартного алгоритма кодирования Base64.

Стандартный алгоритм Base64 преобразует каждые 6 бит входной последовательности в 8 бит, соответствующие ASCII-символу из алфавита A-Za-z0-9+/. Таким образом из 3 исходных байт получается 4 ASCII-символа. Модифицированный алгоритм также разбивает 3 исходных байта на 4 части по 6 бит, но выбирает биты не подряд, а в соответствии с битовой маской.

Для написания алгоритма декодирования весь код ассемблера был переписан на C++.

Поняв суть алгоритма кодирования, легко построили алгоритм декодирования.

После чего подали на вход закодированный текст и получили открытый текст. Счастье, радость, завелось!

Открытым текстом оказался абзац про хоббитов (чего можно было ожидать, исходя из стиля написания исходного задания), а флагом оказалась фраза «ПИРОГЭТОЛОЖЬ», находящаяся в середине одного из предложений.

Заключение

Вот так, потратив двое суток, мы разобрались с такой необычной задачей. Стоит отметить, что мы не считаем данный тип задач хоть в каком-то смысле простыми. При встрече с похожим кейсом проприетарной архитектуры в реальном исследовании невозможно быть уверенным, что огромная проделанная работа действительно к чему-то приведет. Этим заданием мы хотели показать, что делать ошибки и неверные предположения в процессе решения – нормально, а терпение и труд все равно все перетрут.

Raccoon Security – специальная команда экспертов НТЦ «Вулкан» в области практической информационной безопасности, криптографии, схемотехники, обратной разработки и создания низкоуровневого программного обеспечения.