Декодируем 90-ые: реверс-инжиниринг и криптография на заре разработки ПО

В августе 2020 года к нам обратился клиент с кэшем из заблокированных документов QText из середины 90-х, пароль для которых он утерял.

QText — это редактор из времён DOS, использовавшийся для обработки иврита и английского текста. Написан он на Pascal и был выпущен где-то за 15 лет до того, как мы с @Elisha занялись обратной разработкой.

В этой статье мы опишем весь процесс анализа тех зашифрованных документов и выполним реверс-инжиниринг программы DOS.

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

▍ Содержание

• Начинаем
• Реверс-инжиниринг бинарников MS-DOS
  
  • PKZip
  • int 3f — оверлеи MS-DOS
• Функция расширения ключа
  
  • Трассировка потока генерации пароля
  • Функция получения ключа
• Реверс-инжиниринг получения ключа
  
  • Реверс-инжиниринг первого этапа — получение из 4 байт 4 печатных символов
  • Реверс-инжиниринг второго этапа — получение из 16 байт строки 4х4 байта
• Обобщение

Начинаем

К счастью, у нас был доступ к рабочим двоичным файлам QText, которые нам предоставил клиент. Мы загрузили экземпляр эмулятора DOSBOX и немного поэкспериментировали с редактором, сосредоточившись на функции шифрования документов.

Что нам удалось выяснить изначально:

• Пароль короткий — 4 символа и включает только заглавные буквы и цифры. В итоге получается очень скромное пространство ключей в сравнении с современными вычислительными мощностями.
• Документы обычно представляют некую форму простого текста с форматированием — но заблокированные сопровождались заголовком 0𝑥1𝒟. Документы с одним паролем имеют один и тот же заголовок (без дополнения).
• Из 0𝑥1𝒟 байтов заголовка — 1616 фактически являются переменными и связаны напрямую с паролем — может ли быть, что ключ шифра включён в сам файл?
• Незнакомый вид шифрования — похоже, работает на основе строк и столбцов, то есть равные строки текста будут давать равные строки шифротекста. Пробелы при шифровании пропускаются, что говорит о построении шифра по столбцам.

Первая строка двух документов с разными паролями — ключ подчёркнут

Полезная нагрузка из двух документов с одинаковым паролем и текстом — одна перемежается пробелами

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

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

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

Тогда мы взялись за алгоритм получения ключа и начали разбирать исполняемый файл.

Реверс-инжиниринг бинарников MS-DOS

DOS работает в реальном режиме, то есть всё 16-битное пространство адресов разделяется между всеми процессами, и адресация происходит с использованием 16-битного селектора сегментов и дополнительного 16-битного адреса — который применяется для охвата доступного диапазона памяти в 640 КБ.

Исполняемые файлы в этом случае представлены не в формате PE, а в MZ. Файловая утилита распознала наш бинарник QText как SFX-архив PKZip.

▍ PKZip

Своей популярностью известный нам сегодня формат ZIP обязан компании PKWare, которая также разработала широко известный упаковщик исполняемых файлов эпохи MS-DOS.

Про упаковщик PKZip сложно найти какую-то подробную информацию — предполагается, что в нём используется тот же алгоритм сжатия, что и в не-SFX zip-архиваторе, но мы не можем найти инструмент, который бы должным образом распаковал SFX в рабочий файл.

Не найдя никакой дополнительной информации об этом архиваторе и не желая прибегать здесь к реверс-инжинирингу — мы решили использовать функцию CPU LOG отладчика DOSBOX, чтобы шагнуть вглубь его кода куда-нибудь после точки входа и затем извлечь код из памяти.

Это сработало, но добыть удалось лишь небольшую часть кода — размер исполняемого файла был 24 КБ (в архиве).

Вспоминая времена реверс-инжиниринга crackme-программ (хоть и не таких старых, как эта), мы занялись поиском универсального инструмента распаковки исполняемых файлов, которых на сайтах взломщиков оказалось валом.

Опережая некоторые опенсорсные тренды лет так на десять, их внутреннее устройство зачастую оказывалось загадочным, но чаще всего они со своей задачей справлялись. В конечном итоге мы нашли статью в блоге ssokolow, через которую вышли на мифическую реликвию из истории реверс-инжиниринга — exetools.

На этой странице присутствовал огромный список распаковщиков. Думаю, что с задачей справились бы многие из них — всё же PKZip был довольно распространён. Сначала мы попробовали утилиту PKUNLITE, но она не сработала (хотя вселяла надежду). Успеха же удалось добиться с помощью DISLITE v1.15.

▍ int 3f — механизм оверлея в MS-DOS

Загрузка двоичного файла в IDA Free 5.0 (который, к счастью, до сих пор доступен на сайте ScummVM) показала, что в исполняемом файле с помощью Turbo Pascal реализован механизм оверлея.

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

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

Основной код (из файла .exe) всегда отображается в память, а фрагменты оверлея отображаются выборочно и подставляются по требованию.

Вызовы между оверлеями (и корневым сегментом) реализуются через таблицу переходов. Если оверлей уже отображён в память, стабы (или как лучше сказать?) в таблице «связываются» с его текущим местоположением в памяти.

В противном случае (собственно, в нашем) переход происходил на инструкцию int 3f и метаданные оверлея.

Метаданные, помимо прочего, содержали смещение файла соответствующего сегмента кода.

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

Пример непривязанного стаба. Обратите внимание на метаданные оверлея выше

Тот же стаб, но теперь уже связанный с загруженным в память оверлеем

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

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

Нарыть информацию о системе реализации оверлеев в Turbo Pascal было сложно, а отладчик DOSBOX не даёт удобной возможности выхода из функции прерываний.

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

Пример вызова корневого сегмента из оверлея

В примере выше pascal_strncpy расположен в корневом сегменте. Его адрес фиксирован и предсказуем. Чтобы проникнуть в вызывающую функцию в оверлее 73, мы поставим точку останова в pascal_strncpy и выйдем в вызывающей функции.

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

Функция расширения ключа

▍ Трассировка потока создания пароля

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

В итоге мы пошли более прямым путём, установив точку останова на обработчике прерываний int 21 для перехвата вызовов открытия файла и чтения.

Отладчик DOSBOX в момент вызова прерывания для открытия файла. Запрошенный путь указан в Data Overview

Мы прошли через функцию открытия документа и считали 0x1D байтов — то есть точный размер заголовка, который видели в заблокированных документах. Продолжив динамическую отладку, мы выявили функцию, которая в качестве параметров получает введённую строку пароля и заголовок 0x1D.

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

Часть потока проверки пароля — в случае успеха эта функция возвращает 1

Предполагается, что вызов функции до memcmp выполняет расширение ключа, после чего результат сравнивается с заголовком файла.

▍ Функция получения ключа

Пароль сначала передаётся пермутирующей функции, которая поочерёдно инкрементирует каждый байт на сумму всех байтов его строки. Прежде чем переходить к следующему байту, определённый предикат тестируется с использованием значения итогового байта в качестве индекса в статической битовой карте, где каждый бит показывает, является (1) или нет (0) значение байта валидным. Более современный пример использования такой битовой карты можно найти на CFG (Control-Flow Integrity).

Эта функция используется в нескольких местах для проверки значения байта по битовой карте

После пермутации значение каждого байта тестируется. Если это значение оказывается недействительным — оно увеличивается на 0x22. В случае нашей иммутабельной битовой карты такой «коррекции» всегда оказывается достаточно для попадания в валидный диапазон, то есть для каждого байта она может быть выполнена всего раз.

Битовая карта, используемая в функции пермутации

Предикат из qtext_cracker.py:

24 # Взят из двоичного файла
 25 BITMAP =  b"\xff\xff\xff\xff\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80"
 ... 
 28 def is_valid_char(c):
 29     # Можно упростить до 0x20 < c < 0x100
 30     assert type(c) is int
 31     assert c <= 0xFF
 32     upper_idx = c >> 3  # Старшие 5 бит
 33     lower_idx = c & 0b111  # Нижние 3 бита
 34     return not bool((BITMAP[upper_idx] >> lower_idx) & 1)

Более точно это можно выразить в виде проверки 0𝑥22 < значение < 0𝑥100 🤷

Функция пермутации 𝑃(𝑥) из того же файла довольно проста — она поочерёдно инкрементирует каждый байт на сумму всех предыдущих байтов этой строки:

37 def key_transform(input_key, modifier=0x22):
 38     assert type(input_key) is bytearray
 39     key = bytearray(input_key)  # Копирование
 40     for i in range(len(key)):
 41         for j in range(len(key)):
 42             key[i] = (key[i] + key[j]) & 0xFF
 43         while not is_valid_char(key[i]):
 44             key[i] = (key[i] + modifier) & 0xFF
 45     return key

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

Таким образом, функция получения ключа 𝐾(пароль) получается следующая:

𝐾(пароль) = 𝑃(𝑃(пароль)|𝑃(пароль)|𝑃(пароль)|𝑃(пароль))

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

Реверс-инжиниринг функции получения ключа

Сначала рассмотрим простой случай — результат пермутации элементарной двухсимвольной строки — ‘00’:

Этот процесс пермутации строки с длиной 2 иначе можно описать так:

Здесь задействуются только комбинации входных значений — поэтому она линейная, но не строго — мы теряем бит переноса в любой операции, ведущей к переполнению 0𝑥𝐹𝐹.

Предположим, нам нужно разобрать процесс пермутации, начиная с последнего байта. Мы знаем, что 𝟸𝑎₁＋𝑎₂ даёт 0x90, значит, можем использовать подстановку:

Но теперь, поскольку нам нужно делить на 2 (что в этом поле необратимо), есть два возможных решения:

Нам известно, что корректное значение здесь 0𝑥30, но если говорить в общем, то при попытке инвертировать функцию пермутации нам нужно накладывать один результат на другой. Проще говоря — на каждом шаге декомпозиции мы производим «разделение» на две ветки — по одной для каждого результата.

Кроме того, для определённого диапазона значений выполняется ещё одно разделение — если в результате пермутации байт попадает в определённый набор значений (0𝑥20 < 𝑏 < 0𝑥100), он инкрементируется на 0𝑥22.

То есть, если текущий байт находится между 0𝑥20 ＋ 0𝑥22 ≡ 0𝑥24 и 0𝑥100 ＋ 0𝑥22 ≡ 0𝑥22, нужно рассматривать случай, когда он может быть инкрементирован до этого значения, а не получен естественным путём.

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

Если в общем, то на каждом этапе декомпозиции ключа мы производим разделение на один или два пути. Ниже приведена реализация этого алгоритма декомпозиции на базе рекурсии в qtext_cracker.py:

48 def recursive_decomposition(input_key, decomposed_part=None, stop_at=4):
 49     assert type(input_key) is bytearray
 50     key = bytearray(input_key)  # Копирование
 51     if decomposed_part is None:
 52         decomposed_part = bytearray()
 53
 54     if len(key) == 0:
 55         # Условие остановки
 56         return [
 57             decomposed_part,
 58         ]
 59
 60     if stop_at is not None:
 61         if len(decomposed_part) >= stop_at:
 62             return [
 63                 decomposed_part,
 64             ]
 65
 66     results = []
 67     value = key.pop()
 68     if not is_valid_char((value - 0x22) % 0x100):
 69         # Есть дополнительный кейс для обработки
 70         new_key = bytearray(key)  # Копирование
 71         new_key.append((value - 0x22) % 0x100)
 72         # Куда это сохранить?
 73         results.extend(recursive_decomposition(new_key, decomposed_part, stop_at))
 74
 75     value = (value - sum(decomposed_part)) % 0x100
 76     # Вычитаем хвостовые (декомпозированные) символы
 77     # Вычисляем двух кандидатов
 78     candidate_1 = ((value // 2) - sum(key)) % 0x100
 79     candidate_2 = (((0x100 + value) // 2) - sum(key)) % 0x100
 80     new_decomposed_left = bytearray([candidate_1,]) + decomposed_part
 81     new_decomposed_right = bytearray([candidate_2,]) + decomposed_part
 82
 83     results.extend(recursive_decomposition(key, new_decomposed_left, stop_at))
 84     results.extend(recursive_decomposition(key, new_decomposed_right, stop_at))
 85
 86     return results

В случае 16-байтового ключа это означает от 2¹⁶ до 2¹⁷ ветвей, что в общем-то не сильно пугает, но, к счастью, есть два фактора, которые помогут существенно сократить пространство поиска.

▍ Реверс-инжиниринг первого этапа — получение из 4 байтов 4 печатных символов

Первый фактор довольно просто — любой декомпозированный байт изначально был байтом пароля — то есть заглавной буквой или цифрой.

Если рассматривать наш пример выше, то ясно, что мы могли выбрать только печатное значение — 0𝑥30.

▍ Реверс-инжиниринг второго этапа — получение из 16 байтов строки 4х4 байта

Второе ограничение уже не столь тривиально, но и не особо сложное — форма 16-байтового ключа непосредственно перед второй пермутацией представляет последовательность из 4 байт, повторяющихся 4 раза. Это означает, что нам нужно декомпозировать только 4-байтовый суффикс, после чего протестировать его, пропустив через функцию пермутации и проверив, получится ли на выходе исходный ключ.

Всё это сужает пространство поиска до 2⁵ для каждого этапа, или до 2⁶ в общем. При достаточном терпении вы можете взломать это шифрование на бумаге.

Обобщим

Итак, начиная с 16-байтового ключа (k), извлечённого из документа:

1. Прогнать k через функцию декомпозиции, собрав все возможные 4-байтовые суффиксы.
2. Передать суффиксы обратно через функцию пермутации для нахождения корректной.
3. Сузить спектр результатов до попадающих в пространство ввода пароля, чтобы вычислить его.

Весь скрипт взлома qtext лежит здесь.

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻