21 July 2013

Ищем коды уровней в Prehistorik-2

AssemblerGame development

В игре Prehistorik 2 не предусмотрены сейвы, но на каждом уровне есть (болтается в воздухе в некотором месте уровня) код уровня. Есть два режима прохождения, Beginner и Expert, код также определяет режим. При старте игры можно начать с первого уровня, а можно ввести код и попасть сразу на соответствующий уровень. На одном и том же компьютере с неизменным окружением коды не меняются, но на разных компьютерах коды, вообще говоря, разные, так что коды, найденные при прохождении и тщательно выписанные на бумажку, станут совершенно бесполезны в другом окружении. Поэтому вместо бумажки лучше иметь программу, которая пишет коды для конкретного окружения. Готовый результат: genpass.com, представляет из себя DOS-программу, которая должна запускаться в том же окружении, что и игра. Альтернативный вариант попасть на нужный уровень из экрана ввода кода: ввести три кода ADDE C0DE F00D либо DEAD C0DE F00D, каждый из трёх кодов сам по себе неверен, но при вводе их в таком порядке четвёртый код — номер уровня от 1 до 10, плюс 10 для режима Expert, приводит сразу на запрошенный уровень.

Под катом — процесс исследования. Требуется знание ассемблера x86 хотя бы на уровне «читаю со словарём».

Инструменты


Главный инструмент — дизассемблер IDA Pro. Для исследования DOS-программ вполне хватит бесплатной версии 5.0.

Много разных DOS-утилит есть здесь: http://www.exetools.com/, некоторые из них будут упомянуты далее в тексте.

Необязательный инструмент — отладчик. Можно использовать какой-нибудь из DOSовских отладчиков (выбор есть по ссылке выше), их общий недостаток — разделение ресурсов (как минимум, экрана) с отлаживаемой программой. Отдать все ресурсы программе, но при этом отлаживать её позволяет эмулятор Bochs со встроенным отладчиком. Кроме того, можно обойтись и без отладчика.

Также не помешает hex-редактор. Из открытых, видимо, лучший — beye (бывший biew). Но можно обойтись и hexdump для просмотра и
echo -ne '\x..\x..' | dd of= seek= bs=1 conv=notrunc для изменения (без conv=notrunc для уменьшения размера).

Распаковка


Будем анализировать версию, которую можно скачать с old-games.ru: pre2orig.exe размером 52190 байт. Над ней потрудилась (сняв защиту от копирования оригинальной версии) группа Hybrid, о чём игра настойчиво сообщает при старте.

В exe'шнике не обнаруживается связных текстовых строк, что наводит на мысли об упакованности файла: exe'шник на диске сжат с добавлением кода распаковщика, при загрузке сначала выполняется распаковщик, который распаковывает данные в памяти и передаёт управление на распакованный код. Естественно, перед исследованием кода придётся снять этот слой. File Scanner отсюда успешно идентифицирует упаковщик как LZEXE, для которого есть автоматический распаковщик unlzexe. Запустив unlzexe, получаем pre2_1.exe размером 63728 байт.

В pre2_1.exe осмысленные текстовые строки есть, первая из них "INTRO CODED BY CYBER". Смотрим внутрь:

seg002:5E48 start proc near seg002:5E48 mov cs:pspSeg, ds seg002:5E4D mov ax, cs seg002:5E4F mov es, ax seg002:5E51 assume es:seg002 seg002:5E51 mov cx, 20h seg002:5E54 mov si, 80h seg002:5E57 mov di, si seg002:5E59 rep movsb seg002:5E5B mov ds, ax seg002:5E5D assume ds:seg002 seg002:5E5D call loc_19960 seg002:5E60 mov ax, pspSeg seg002:5E63 add ax, 10h seg002:5E66 add nextCS, ax seg002:5E6A add nextSS, ax seg002:5E6E sub ax, 10h seg002:5E71 mov ds, ax seg002:5E73 assume ds:nothing seg002:5E73 mov es, ax seg002:5E75 assume es:nothing seg002:5E75 mov ax, cs:nextSS seg002:5E79 mov ss, ax seg002:5E7B assume ss:nothing seg002:5E7B mov sp, cs:nextSP seg002:5E80 mov bx, offset nextIP seg002:5E83 jmp dword ptr cs:[bx] seg002:5E83 start endp seg002:5E83 seg002:5E83 ; --------------------------------------------------------------------------- seg002:5E86 nextIP dw 3 ; DATA XREF: start+38o seg002:5E88 nextCS dw 0 ; DATA XREF: start+1Ew seg002:5E8A pspSeg dw 0 ; DATA XREF: startw seg002:5E8A ; start+18r seg002:5E8C nextSS dw 1681h ; DATA XREF: start+22w seg002:5E8C ; start+2Dr seg002:5E8E nextSP dw 80h ; DATA XREF: start+33r

DOS создаёт в памяти перед программой область PSP размером 100h байт, самая интересная часть которой - командная строка по смещению 80h (в Pascal-стиле: первый байт - длина). Регистры ds и es при запуске программы указывают на сегмент PSP, приложение начинается с адреса ds:0+100h = (ds+10h):0. Первая команда сохраняет ds, следующие 7 (не считая assume - это не команды, а директивы ассемблера) копируют командную строку и настраивают ds, es, затем следует вызов какой-то процедуры loc_19960. После завершения процедуры следует последовательность действий, типичная для последней части кода, "навешенного" поверх готового бинарника, эмулирующая последние действия DOS перед началом выполнения программы: ds и es устанавливаются в сегмент PSP, ss:sp устанавливаются в значение, находящееся по фиксированному смещению относительно начала программы (сегмент pspSeg+10h), происходит прыжок на адрес, находящийся по фиксированному смещению относительно начала программы. Процедура loc_19960 начинает с трёх проверок, при нарушении которых немедленно выходит; о смысле проверок лучше всего говорят текстовые сообщения "This program requires an 80286 or higher", "This program requires a VGA card", "Intro skipped". Фрагмент кода последней проверки:
seg002:082F                 cmp     al, '/'
seg002:0831                 jnz     short loc_1A08A
seg002:0833                 lodsb
seg002:0834                 and     al, not 20h
seg002:0836                 cmp     al, 'N'
seg002:0838                 jnz     short loc_1A08B
seg002:083A                 lodsb
seg002:083B                 and     al, not 20h
seg002:083D                 cmp     al, 'I'
seg002:083F                 jnz     short loc_1A08B

То есть, остаток процедуры loc_19960 не вызывается, если передать в командной строке параметр /ni. Пробуем, видим, что с этим параметром игра пропускает напоминание о доблестной команде Hybrid и сразу переходит к собственно игре. Делаем вывод, что весь seg002 - ненужная для игры заставка, навешенная на рабочий exe'шник. Переписываем в заголовке cs:ip на 0000:0003, ss:sp на 1681:0080, обрезаем последние 5E90h байт, соответственно скорректировав поля размера и дополнительной памяти в заголовке.

Получаем файл pre2_2.exe размером 39520 байт. В нём снова нет связных текстовых строк (все строки из pre2_1.exe оказались связаны с заставкой Hybrid), что снова наводит на мысли об упакованности. Тот же File Scanner показывает "Diet 1.00,1.20" в качестве упаковщика. Этот факт примечателен тем, что diet может работать в двух режимах: упаковка бинарников и упаковка данных. Попробовав распаковать файлы уровней (как самые интересные данные из всех) с помощью diet, убеждаемся, что, действительно, файлы уровней тоже упакованы diet, и, если нас заинтересует структура файлов уровней, один слой (упаковку) мы уже знаем.

Для снятия diet прибегнем к универсальному распаковщику cup386. diet не содержит антиотладочных приёмов, запуск cup386 pre2_2.exe pre2unp.exe /1 приводит к распакованному файлу pre2unp.exe размером 91344 байт. Поиск текстовых строк показывает, что pre2unp.exe - то, что нам нужно.

Поиск кодов



Прежде всего нужно найти место проверки и генерации кодов. Вариантов несколько. Можно прийти дизассемблером в точку входа программы и начать изучать всё подряд (если вы никуда не торопитесь; самый медленный способ, зато по дороге можно узнать много интересного). Можно зайти отладчиком, пройтись по коду без захода внутрь вызываемых процедур, отмечая, какие визуальные эффекты происходят во время выполнения процедур. Можно запустить под отладчиком, дойти до экрана выбора кода и прервать выполнение, посмотрев, где мы находимся (и заглянув в стек, чтобы выяснить, кто вызвал процедуру, где мы находимся). В данном случае самый простой способ - привязаться к текстовой строке "ENTER CODE", наличествующей на экране ввода кода. Поиск находит такую строку по адресу seg002:B171 (IDA любезно определила сегменты ещё при загрузке exe'шника), поиск значения 0B171h выводит на такую процедуру:
seg001:99C3 sub_19BC3       proc near               ; DATA XREF: sub_1906F+A1o
seg001:99C3                 call    sub_19D1E
seg001:99C6                 mov     byte_251D7, 3
seg001:99CB                 mov     bx, offset aEnterCode ; "ENTER CODE"
seg001:99CE                 mov     word_251D2, 0AF2h
seg001:99D4                 call    sub_19AC4
seg001:99D7                 mov     byte_251D7, 4
seg001:99DC                 mov     bx, offset levelCode ; "[[[["
seg001:99DF                 mov     word_251D2, 12C9h
seg001:99E5                 call    sub_19AC4
Первую команду вызова sub_19D1E проигнорируем. Дальше следует два вызова одной и той же процедуры sub_19AC4, первый раз для строки "ENTER CODE", второй раз для строки из 4 символов, изменяемой далее в ходе процедуры; логично считать, что это вывод строки на экран, а вторая строка - вводимый код.
seg001:99E8                 cmp     byte_251D6, 1
seg001:99ED                 jnz     short loc_19BF2
seg001:99EF                 jmp     loc_19CF2
seg001:99F2 ; ---------------------------------------------------------------------------
seg001:99F2
seg001:99F2 loc_19BF2:                              ; CODE XREF: sub_19BC3+2Aj
seg001:99F2                 cmp     byte_251D6, 2
seg001:99F7                 jnz     short loc_19BFC
seg001:99F9                 jmp     loc_19D02
seg001:99FC ; ---------------------------------------------------------------------------
...
seg001:9AF2 ; ---------------------------------------------------------------------------
seg001:9AF2
seg001:9AF2 loc_19CF2:                              ; CODE XREF: sub_19BC3+2Cj
seg001:9AF2                 inc     word_251DC
seg001:9AF6                 mov     bx, word_251DC
seg001:9AFA                 sub     bx, 8Ch
seg001:9AFE                 jb      short locret_19D1D
seg001:9B00                 jmp     short loc_19D06
seg001:9B02 ; ---------------------------------------------------------------------------
seg001:9B02
seg001:9B02 loc_19D02:                              ; CODE XREF: sub_19BC3+36j
seg001:9B02                                         ; sub_19BC3+4Ej
seg001:9B02                 inc     byte_251DE
seg001:9B06
seg001:9B06 loc_19D06:                              ; CODE XREF: sub_19BC3+13Dj
seg001:9B06                 mov     bx, offset levelCode ; "[[[["
seg001:9B09                 mov     word ptr [bx], '[['
seg001:9B0D                 mov     word ptr [bx+2], '[['
seg001:9B12                 mov     byte_251D6, 0
seg001:9B17                 mov     word_251D4, 0
seg001:9B1D
seg001:9B1D locret_19D1D:                           ; CODE XREF: sub_19BC3+42j
seg001:9B1D                                         ; sub_19BC3+60j ...
seg001:9B1D                 retn
seg001:9B1D sub_19BC3       endp
В режиме byte_251D6 == 1 увеличивается счётчик word_251DC, пока не достигнет значения 8Ch, после чего byte_251D6 сбрасывается в 0, а введённый код очищается. Это как раз подходит под то, что после введения неправильного кода в игре он некоторое время остаётся на экране, после чего сбрасывается сам собой. В режиме byte_251D6 == 2 происходит то же самое, но без паузы; это нам неинтересно.
seg001:99FC
seg001:99FC loc_19BFC:                              ; CODE XREF: sub_19BC3+34j
seg001:99FC                 mov     bl, ScanCode
seg001:9A00                 test    bl, 80h
seg001:9A03                 jz      short loc_19C08
seg001:9A05                 jmp     locret_19D1D
seg001:9A08 ; ---------------------------------------------------------------------------
seg001:9A08
seg001:9A08 loc_19C08:                              ; CODE XREF: sub_19BC3+40j
seg001:9A08                 mov     al, KeysPressed+39h
seg001:9A0B                 or      al, KeysPressed+1Ch
seg001:9A0F                 jz      short loc_19C14
seg001:9A11                 jmp     loc_19D02
seg001:9A14 ; ---------------------------------------------------------------------------
seg001:9A14
Дальше читается переменная по адресу seg002:2870. Изучение ссылок на неё (найденных IDA) показывает, что ненулевое значение записывается только в одном месте, где оно берётся чтением из порта клавиатуры 60h. Делаем вывод, что эта переменная - последний обработанный сканкод клавиатуры, а записывающая процедура - обработчик прерывания клавиатуры; переименовываем переменную в ScanCode. Прокрутив обработчик прерывания до конца, понимаем значение ещё двух используемых переменных: массив KeyPressed (обновляемый в обработчике клавиатуры) содержит статусы кнопок (0 = кнопка не нажата, 0FFh = кнопка нажата). Возвращаемся в исследуемую процедуру: KeyPressed[39h] и KeyPressed[1Ch] - статусы пробела и Enter соответственно. При нажатии пробела или Enter (как показывает тест) игра возвращается из экрана ввода кода в экран с меню, это не то, что нам надо.
seg001:9A14 loc_19C14:                              ; CODE XREF: sub_19BC3+4Cj
seg001:9A14                 mov     ScanCode, 0
seg001:9A19                 xor     bh, bh
seg001:9A1B                 mov     al, byte ptr a1234567890AEADfCB[bx] ; "--1234567890----A-E-----------A-DF-----"...
seg001:9A1F                 cmp     al, '-'
seg001:9A21                 jnz     short loc_19C26
seg001:9A23                 jmp     locret_19D1D
seg001:9A26 ; ---------------------------------------------------------------------------
seg001:9A26
seg001:9A26 loc_19C26:                              ; CODE XREF: sub_19BC3+5Ej
seg001:9A26                 mov     ah, al
seg001:9A28                 sub     ah, '0'
seg001:9A2B                 cmp     ah, 9
seg001:9A2E                 jbe     short loc_19C33
seg001:9A30                 sub     ah, 7
seg001:9A33
seg001:9A33 loc_19C33:                              ; CODE XREF: sub_19BC3+6Bj
Здесь начинаются интересные действия. Сканкод подставляется как индекс в строку "--1234567890----A-E-----------A-DF------------C-B-...-", это преобразование в ASCII-код (заглянув в список сканкодов, обнаруживаем, что ASCII-код 'A' получается не только от клавиши A, но и от клавиши Q - надо полагать, чтобы игра работала также с раскладкой AZERTY). Если ASCII-код не является hex-цифрой, процедура игнорирует клавишу и выходит. Если является, то происходит преобразование в число от 0 до 0Fh.
seg001:9A33                 mov     dx, word_251E5
seg001:9A37                 mov     cl, 4
seg001:9A39                 shl     ah, cl
seg001:9A3B                 shl     ah, 1
seg001:9A3D                 rcl     dx, 1
seg001:9A3F                 shl     ah, 1
seg001:9A41                 rcl     dx, 1
seg001:9A43                 shl     ah, 1
seg001:9A45                 rcl     dx, 1
seg001:9A47                 shl     ah, 1
seg001:9A49                 rcl     dx, 1
seg001:9A4B                 mov     word_251E5, dx
seg001:9A4F                 mov     bx, word_251D4
seg001:9A53                 mov     byte ptr levelCode[bx], al ; "[[[["
seg001:9A57                 inc     word_251D4
seg001:9A5B                 inc     bl
seg001:9A5D                 cmp     bl, 4
seg001:9A60                 jnb     short loc_19C65
seg001:9A62                 jmp     locret_19D1D
seg001:9A65 ; ---------------------------------------------------------------------------
Переменная word_251E5 сдвигается на 4 бита влево, младшие биты заполняются числом, соответствующим введённому символу. Сам символ дописывается в строку со введённым кодом, число введённых символов word_251D4 увеличивается на единицу. Если ещё нет 4 символов, на этом обработка заканчивается. После 4 символов word_251E5 содержит 16-битное число, хранящее введённый код ("1234" -> 1234h), дальше следует ожидать проверок этого числа.
seg001:9A65
seg001:9A65 loc_19C65:                              ; CODE XREF: sub_19BC3+9Dj
seg001:9A65                 push    bp
seg001:9A66                 mov     word_251DC, 0
seg001:9A6C                 mov     di, word_251DF
seg001:9A70                 mov     si, word_251E1
seg001:9A74                 mov     bp, word_251E3
seg001:9A78                 mov     ax, di
seg001:9A7A                 rol     ax, 1
seg001:9A7C                 rol     ax, 1
seg001:9A7E                 mul     ah
seg001:9A80                 xor     ax, si
seg001:9A82                 mul     bp
seg001:9A84                 mov     bx, ax
seg001:9A86                 add     bx, si
seg001:9A88                 ror     bx, 1
seg001:9A8A                 rol     bl, 1
seg001:9A8C                 xor     bl, bh
seg001:9A8E                 xor     bx, bp
seg001:9A90                 pop     bp
seg001:9A91                 cmp     ax, 36C8h
seg001:9A94                 jnz     short loc_19CAC
seg001:9A96                 cmp     bx, 8BD1h
seg001:9A9A                 jnz     short loc_19CAC
seg001:9A9C                 cmp     dx, 8E71h
seg001:9AA0                 jnz     short loc_19CAC
seg001:9AA2                 mov     dx, word_251E5
seg001:9AA6                 dec     dx
seg001:9AA7                 cmp     dx, 14h
seg001:9AAA                 jbe     short loc_19CD9
seg001:9AAC
seg001:9AAC loc_19CAC:                              ; CODE XREF: sub_19BC3+D1j
seg001:9AAC                                         ; sub_19BC3+D7j ...
Обнуление счётчика word_251DC и первая проверка. Если некоторые преобразования над тремя переменными, лежащими в памяти непосредственно перед word_251E5, приводят к некоторым фиксированным значениям и введённый код находится в диапазоне от 1 до 15h включительно, происходит переход на метку loc_19CD9 с dx, равным введённому коду минус единица. Отложим пока выяснение, что же это за переменные.
seg001:9AAC                 xor     dx, dx
seg001:9AAE
seg001:9AAE loc_19CAE:                              ; CODE XREF: sub_19BC3+FAj
seg001:9AAE                 mov     ax, dx
seg001:9AB0                 call    sub_19559
seg001:9AB3                 cmp     word_251E5, ax
seg001:9AB7                 jz      short loc_19CD9
seg001:9AB9                 inc     dx
seg001:9ABA                 cmp     dx, 14h
seg001:9ABD                 jbe     short loc_19CAE
seg001:9ABF                 mov     si, offset word_251E1
seg001:9AC2                 mov     ax, [si]
seg001:9AC4                 mov     [si-2], ax
seg001:9AC7                 mov     ax, [si+2]
seg001:9ACA                 mov     [si], ax
seg001:9ACC                 mov     ax, [si+4]
seg001:9ACF                 mov     [si+2], ax
seg001:9AD2                 mov     byte_251D6, 1
seg001:9AD7                 jmp     short locret_19D1D
seg001:9AD9 ; ---------------------------------------------------------------------------
Основная проверка. word_251E5 последовательно сравнивается с результатом работы функции sub_19559, вызываемой последовательно с dx от 0 до 14h. При равенстве происходит переход на метку loc_19CD9 с dx, при котором sub_19559 возвращает введённый код. Ясно, что sub_19559 возвращает код заданного уровня.

Если совпадения нет, то byte_251D6 устанавливается в 1 (как мы уже видели, это соответствует неверному коду), введённый код и две предшествующих ему переменных перемещаются на одну переменную назад. После трёх неправильных попыток три переменные, предшествующие введённому коду, будут хранить предыдущие варианты; теперь понятно, откуда берутся исходные данные для первой проверки.
seg001:9AD9
seg001:9AD9 loc_19CD9:                              ; CODE XREF: sub_19BC3+E7j
seg001:9AD9                                         ; sub_19BC3+F4j
seg001:9AD9                 mov     al, 0
seg001:9ADB                 cmp     dl, 0Ah
seg001:9ADE                 jb      short loc_19CE4
seg001:9AE0                 sub     dl, 0Ah
seg001:9AE3                 inc     ax
seg001:9AE4
seg001:9AE4 loc_19CE4:                              ; CODE XREF: sub_19BC3+11Bj
seg001:9AE4                 mov     byte_1CDB6, dl
seg001:9AE8                 mov     byte_251C3, al
seg001:9AEB                 mov     byte_251D6, 2
seg001:9AF0                 jmp     short locret_19D1D

Завершение процедуры при правильном коде: если dx меньше 10, оно записывается как есть в byte_1CDB6, а byte_251C3 становится нулём; иначе в byte_1CDB6 записывается dx-10, а byte_251C3 становится единицей. В любом случае byte_251D6 становится равным 2, что означает конец процедуры.

Остаётся сделать генератор кодов, действующий так же, как sub_19599, и/или выяснить, как пройти первую проверку. Кратко о вычислении кодов: сначала вычисляется переменная word_2435F на основе последних 10h байт BIOS F000:FFF0 (включающих дату BIOS) и первых 80h байт всех расширений BIOS в интервале от C000:0000 до F000:0000. Собственно код уровня вычисляется следующим образом:
; ax = zero-based level
seg001:93C6                 xor     ax, 55A3h
seg001:93C9                 mul     word_2435F
seg001:93CD                 mov     cl, cs:ProcessorType ; always 3 for 386+
seg001:93D2                 rol     ax, cl
Процедура sub_19599 достаточно независима от окружения (ей требуется только тип процессора - для 386+ он всегда равен 3), её можно просто скопировать из дизассемблированного кода, получив примерно такой генератор кодов: genpass.asm, genpass.com.

Немного сложнее выяснить "магические" значения для первой проверки: три кода, после введения которых можно просто ввести номер уровня (в hex и 1-based). Проверяются три значения, вычисляемые по трём кодам: пара dx:ax должна быть равна 8E7136C8h, значение bx должно быть 8BD1h. Анализ кода, приведённого выше, показывает, что dx:ax получается на выходе команды mul bp и 8E7136C8h - произведение двух 16-битных чисел: третьего кода и некоторого выражения с первыми двумя кодами. bx - некоторое выражение со вторым и третьим кодом. Разлагая 8E7136C8h на множители, получаем 23*7*4861*8779; чтобы получить два 16-битных сомножителя, 4861 и 8779 должны входить в разные сомножители, а оставшиеся множители 23*7 должны быть как-то разбиты на две части. Получается довольно мало вариантов (16 до отсеивания из-за 16-битности). Переберём каждый из вариантов; второй сомножитель - третий код, зная его, находим второй код из bx, после чего первый сомножитель даёт произведение двух 8-битных множителей. Не всякое 16-битное число можно представить в виде произведения двух 8-битных, здесь отсеиваются все варианты для третьего кода, кроме одного, который зато даёт два варианта для первого кода (отличающихся порядком 8-битных множителей). Код перебора: getmagic.c, результаты: ADDE C0DE F00D и DEAD C0DE F00D.
Tags:reverse engineeringобратный инжинирингстарые игрыold school
Hubs: Assembler Game development
+82
34.5k 98
Comments 22
Top of the last 24 hours