Работа над задачей позволила познакомиться с архитектурой m68k и попробовать сделать простые инструменты для работы с трассировкой инструкций.
Райтап описывает успешную часть решения, опуская тупиковые и не использованные ветки развития решения.
TL;DR, очень коротко:
- трассировка инструкций была добавлена в эмулятор,
- были найдены две независимые проверки по два байта,
- проверки были пройдены перебором.
С веб-страницы конкурса:
Конкурс для реверс-инженеров, в котором любой может продемонстрировать навыки анализа исполняемых файлов. Проводится с 1 по 14 мая.
К конкурсу допускается любой интернет-пользователь.
Участникам для анализа представляется ROM игры для Sega Mega Drive (best_reverser_phd9_rom_v4.bin).
Задача: подобрать такой ключ, который в паре с email-адресом участника будет признан валидным.
Для проверки правильности решения можно использовать эмуляторы Sega Mega Drive, доступные по следующим ссылкам:
https://www.carpeludum.com/download/Fusion364.zip (Windows)
https://www.carpeludum.com/download/Fusion363x.tar.gz (Linux)
https://www.carpeludum.com/download/Fusion363i.zip (macOS)
Ответы и комментарии к решению необходимо присылать на адрес
[email protected].
Инвайты на PHDays и памятные призы от организаторов.
| Место | Время отправки решения | Имя/никнейм |
|---|---|---|
| 1 | 02.05.2019 14:55 | sysenter |
| 2 | 02.05.2019 19:49 | Vesemir |
| 3 | 02.05.2019 20:55 | a1exdandy |
| 4 | 03.05.2019 16:47 | Aleksey Cherepanov |
| 5 | 05.05.2019 21:33 | Marat Gayanov |
| 6 | 06.05.2019 21:26 | AV1ct0r |
| 7 | 08.05.2019 19:21 | mostobriv |
| 8 | 10.05.2019 01:34 | Danila Parnishchev |
| 9 | 10.05.2019 02:15 | Ivan Uschapovskiy |
| 10 | 10.05.2019 14:44 | Dmitriy Sklyar |
| 11 | 10.05.2019 19:13 | vient |
| 12 | 13.05.2019 03:08 | Sergey Karbovsky |
-
Запуск ROM'а в эмуляторе дал представление о приложении: это классическое crackme, только вводить текст неудобно из-за наэкранной клавиатуры (всё-таки для ввода используется gamepad).
-
Сообщения из интерфейса были сопоставлены с результатами
strings. Для сообщений о результате проверки были найдены адреса - простое смещение от начала файла. -
Для дизассемблирования использовался radare2 последней версии. (Хотя можно использовать
objdumpиз пакетаbinutils-multiarch.) -
По адресам строк сообщений о результатах проверки были найдены концы проверки в коде.
-
Поиск инструментов в интернете привёл к эмулятору Gens KMod, который предоставляет gdb server.
-
Получилось выяснить адреса буферов с почтой и ключом:
0xff01aaи0xff01c7. -
Однако подход оказался слишком медленным для трассировки через gdb. Так что было решено добавить трассировку в эмулятор.
-
-
Для модификаций был выбран эмулятор Mednafen. Он есть в основном репозитории Debian и, соответственно, его можно легко собрать из исходников при помощи команды
apt-get -b source. -
В Mednafen было создано сохранённое состояние с введённой почтой и ключом-пустышкой
A01BC23DE45FG67H, который легко ввести, но который при этом не имеет повторов в памяти, что позволяет его легко заменить на другой ключ в файле состояния. -
Эмулятор был настроен так, чтобы стартовать сразу с заданного состояния.
-
Для трассировки был исправлен исходный код Mednafen:
- был добавлен выход по достижению одной из концовок проверки ключа,
- было добавлено зажатие кнопки
Enter, чтобы при старте эмулятора сразу вызывалась проверка ключа, - был добавлен вывод адреса текущей инструкции, её опкода и всех регистров в файл.
-
По полученным записям выполнения проверки получилось найти первую проверку по адресу
0x1f12со сравнением, которое забраковывало ключ, если младшие два байта регистраd2не равны значению0xcb4c(лежащему в памяти). При этом значение регистра зависело от ключа. -
Чтобы пройти первую проверку, использовался перебор: эмулятор запускался со случайными ключами, результаты записывались.
-
Через несколько часов был найден подходящий ключ:
D2S5YSX951P0OAD3. Тут не обошлось без везения: за 117 тысяч запусков получилось найти только 54 тысячи из 65 тысяч возможных значений в регистре в момент проверки. -
Найденный ключ проходил проверку со значением
0xcb4c, но оказалось, что этого недостаточно для решения задачи. И дальше всё становилось только интереснее, потому что трассировка показывала, что часть код находится в изменяемой памяти. -
Вторая проверка была устроена несколько иначе и была расположена как раз в изменяемой памяти по адресу
0xff0daa. Она сравнивала двухбайтовое значение, нетривиально зависящее от ключа, со значением, зависящим от почты. При этом изменение почты не могло создать подходящее значение. -
Было замечено, что код в изменяемой памяти вызывает функцию по адресу
0x1526. Ей через стек передаётся указатель, который в одном вызове совпадает с адресом ключа. А в 3 других вызовах этот аргумент является отступами от начала буфера ключа, идущими по 4 байта. При этом два вызова происходят до первой проверки, а ещё два - после. -
Это привело к предположению, что ключ не используется целиком для первой проверки и его части можно менять независимо. Были попробованы ключи с другими последними 4 байтами.
-
Изменения последних 4 байт ключа не повлияли на первую проверку.
-
Оказалось, что последние 2 байта ключа - hex младшего байта значения, участвующего во второй проверке.
-
Старший байт значения в регистре зависит от предпоследней пары байт в ключе, но эта зависимость немного сложнее. Небольшими изменениями эти байты были подобраны вручную за несколько попыток.
-
-
Новый ключ прошёл обе проверки и оказался решением задачи.
$ file best_reverser_phd9_rom_v4.bin
best_reverser_phd9_rom_v4.bin: Sega MegaDrive/Genesis raw ROM dump Name: "BEST REVERSER PH" (C)PT RE 2019
$ sha256sum best_reverser_phd9_rom_v4.bin
381efbbe1a1be2c683858dbf0c541c414565bab6ff17438e0dd19c46cadacae2 best_reverser_phd9_rom_v4.bin
При запуске в эмуляторе появляется следующий текст:
Sega MD [KEYGEN ME]
A=INPUT B=ERASE C=CLEAR S=CHECK
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z @ _ . -
Email:
Key:
При нажатии кнопки Start ввод переходит во второе поле, потом
вызывает проверку и переходит обратно в первое поле. В результате
проверки показывается одно из трёх сообщений:
Wrong length! Try again...(смещение0xfdfa), если в поле ключа меньше 16 символов,Wrong key! Try again...(смещение0xfe30), если ключ не подошёл,YOU ARE THE BEST REVERSER!(смещение0xfe15), если ключ подошёл.
Но третье сообщение не получается легко. Его можно найти в самом файле между двумя другими сообщениями.
Смещения сообщений относительно начала файла находились по-простому:
$ python -c 'import sys; print hex(sys.stdin.read().index("Wrong length! Try again..."))' < best_reverser_phd9_rom_v4.bin
0xfdfa
Для дизассемблирования использовался radare2. При этом был дизассемблирован весь файл, включая служебный заголовок:
$ r2 -AA best_reverser_phd9_rom_v4.bin
WARNING: Plugin smd should implement load_buffer method instead of load_bytes.
Copyright: SEGA MEGA DRIVE (C)PT RE 2019
DomesticName: BEST REVERSER PHD 9 (2019)
OverseasName: BEST REVERSER PHD 9 (2019)
ProductCode: GM 12345678-90
Checksum: 0x0000
Peripherials: JD
SramCode:
ModemCode:
CountryCode: JUE
[...]
[0x00000200]> 0
[0x00000000]> pD $s >bdis
Результат дизассемблирования был записан в файл bdis. Этот файл
использовался, как импровизированная база данных для добавления
ассемблера в результаты трассировки.
- Для использования файла
bdisвместе с результатом трассировки оказалось недостаточно простого дизассемблирования, потому что при работе происходит прыжок на адрес0x23e8, который не был дизассеблирован, как отдельная инструкция.
Это несложно исправить, добавив ещё раз правильный кусок кода в файл bdis.
$ r2 -AA best_reverser_phd9_rom_v4.bin
[...]
[0x00000200]> 0x23e8
[0x000023e8]> pD 100
0x000023e8 4feffff4 lea.l -0xc(a7), a7
0x000023ec 48e73c3c movem.l d2-d5/a2-a5, -(a7)
0x000023f0 303900ff0d1a move.w 0xff0d1a.l, d0
0x000023f6 00400001 ori.w 0x1, d0
0x000023fa 33c000ff0d1a move.w d0, 0xff0d1a.l
0x00002400 203900ff0c78 move.l 0xff0c78.l, d0
0x00002406 5280 addq.l 0x1, d0
0x00002408 23c000ff0c78 move.l d0, 0xff0c78.l
0x0000240e 207900ff0c94 movea.l 0xff0c94.l, a0
0x00002414 b0fc0000 cmpa.w 0x0, a0
,=< 0x00002418 6702 beq.b 0x241c
| 0x0000241a 4e90 jsr (a0)
| ; CODE XREF from fcn.00001608 (+0xe10)
`-> 0x0000241c 263900ff0cf0 move.l 0xff0cf0.l, d3
[...]
-
В
bdisбыло вырезана левая часть строк, где проходят визуальные линии. Только<и>были оставлены. -
Позже пришлось добавить ещё инструкции, которые не были дизассеблированы сразу:
0x0000151e 203900ff017e move.l 0xff017e.l, d0
0x00001524 4e75 rts
- Предполагалось вставлять ассемблер в результат трассировки по адресам, благо в ходе программы код не изменялся. Но после первой проверки код был в изменяемой части памяти, так что пришлось добавить соединение ассемблера и истории по опкодам.
Отдельно были дизассеблированы некоторые инструкции вот такой командой (неправильной для некоторых инструкций, типа условных переходов):
$ rasm2 -a m68k -d 12300800
move.b (a0, d0.l), d1
Тут надо обратить внимание на 2 особенности: во-первых, если дать слишком мало данных, то ошибки не будет, просто инструкция будет дизассемблирована неправильно, во-вторых, условные переходы обычно кодируются, используя относительное смещение, а в ассемблере показываются с абсолютным адресом. Так что условные переходы не получится корректно показывать, связывая статичную строку ассемблера с опкодом.
Для задания адреса инструкции для дизассемблера есть опция -o:
$ rasm2 -a m68k -d 66ea -o 0xff0d96
bne.b 0xff0d82
Так что в файл были добавлены ещё такие строки:
0x12345678 1002 move.b d2, d0
0x12345678 12300800 move.b (a0, d0.l), d1
0x12345678 0c010020 cmpi.b 0x20, d1
0x12345678 4e560000 link.w a6, 0x0
0x12345678 48e73838 movem.l d2-d4/a2-a4, -(a7)
0x12345678 206f0032 movea.l 0x32(a7), a0
0x12345678 22680006 movea.l 0x6(a0), a1
0x12345678 2668000e movea.l 0xe(a0), a3
0x12345678 d1fc00000012 adda.l 0x12, a0
0x12345678 280c move.l a4, d4
0x12345678 5084 addq.l 0x8, d4
0x12345678 49ec000c lea.l 0xc(a4), a4
0x12345678 b143 eor.w d0, d3
0x12345678 2480 move.l d0, (a2)
0x12345678 4cee1c1cffe8 movem.l -0x18(a6), d2-d4/a2-a4
0x12345678 2468000a movea.l 0xa(a0), a2
0x00ff0d96 66ea bne.b 0xff0d82
Инструкция по адресу 0xff0d96 - не единственный прыжок в коде в
изменяемой области памяти, но именно этот прыжок сильно мешал
пониманию кода.
- Можно воспользоваться
objdumpдля дизассемблерования. Он есть в основном репозитории операционной системы Debian. Однако для поддержки архитектурыm68kнадо использовать пакетbinutils-multiarch. Плюс формат файла не опознаётся, так что надо будет дизассемблировать файл целиком:
$ objdump -m m68k -b binary -D best_reverser_phd9_rom_v4.bin
Пример использования objdump для одной инструкции с указанием адреса
инструкции:
$ python -c 'import sys; sys.stdout.write("66ea".decode("hex"))' > t.bin
$ objdump -m m68k -b binary -D t.bin --adjust-vma=0xff0d96
[...]
ff0d96: 66ea bnes 0xff0d82
Вначале были найдены смещения строк с сообщениями о результате проверки ключ. По смещениям можно найти код вывода результатов, потому что они используются напрямую.
> 0x000019aa 4878000e pea.l 0xe.w
0x000019ae 48780008 pea.l 0x8.w
0x000019b2 48790000fe30 pea.l 0xfe30.l ; "Wrong key..."
0x000019b8 4eb900006fc0 jsr fcn.00006fc0
> 0x00001d1c 4878000e pea.l 0xe.w
0x00001d20 48780008 pea.l 0x8.w
0x00001d24 48790000fdfa pea.l 0xfdfa.l ; "Wrong length..."
0x00001d2a 4eb900006fc0 jsr fcn.00006fc0
> 0x00001a6c 4878000e pea.l 0xe.w
0x00001a70 48780008 pea.l 0x8.w
0x00001a74 48790000fe15 pea.l 0xfe15.l ; "YOU ARE THE..."
0x00001a7a 4eb900006fc0 jsr fcn.00006fc0
0x00001a80 4fef000c lea.l 0xc(a7), a7
< 0x00001a84 6000ff3c bra.w 0x19c2
-
bra- безусловный переход, отBRanch Always(что написано тут). -
peaкладёт константу в стек, отPush Effective Address(что написано тут).
По адресам кода с выводом можно найти некоторые проверки.
Вот проверка длины ключа:
> 0x000017de 41f900ff01c7 lea.l 0xff01c7.l, a0
0x000017e4 7000 moveq 0x0, d0
0x000017e6 303900ff01e4 move.w 0xff01e4.l, d0
0x000017ec 0c3000200800 cmpi.b 0x20, (a0, d0.l)
< 0x000017f2 67000528 beq.w 0x1d1c ; go to "Wrong length..."
Отсюда можно предположить, что буфер с введённым ключом располагается
по адресу 0xff01c7. Туда точно стоит заглянуть.
Видно ещё две проверки, которые могут забраковать ключ.
0x00001998 4a81 tst.l d1
< 0x0000199a 660e bne.b 0x19aa ; go to "Wrong key..."
0x0000199c 2f0b move.l a3, -(a7)
0x0000199e 4ebafb64 jsr fcn.00001504(pc)
0x000019a2 588f addq.l 0x4, a7
0x000019a4 4a80 tst.l d0
< 0x000019a6 660000c4 bne.w 0x1a6c ; go to "YOU ARE ..."
Если условный прыжок по адресу 0x19a6 не переходит на победную
концовку, то получается Wrong key..., потому что этот код идёт сразу
за этим блоком.
Поверхностное изучение доступных инструментов для разработки и отладки
ROM'ов привело на страницу с разными инструментами и в
частности к эмулятору
Gens KMod, в котором
есть встроенный gdb server. Этот эмулятор поддерживает только ОС
Windows, но он без проблем работает под Wine.
(Если говорить об инструментах и материалах, надо заметить, что в
ROM'е есть строка DR. MEFISTO (03/26/2019), а 20 марта 2019 была
опубликована
статья о добавлении загрузки ROM'ов в GHIDRA
за авторством DrMefistO, у которого есть и
другие статьи по теме Sega Mega Drive.)
gdb server надо включить в настройках Gens KMod. После этого можно
использовать gdb-multiarch, чтобы отлаживать программу со всеми
удобствами. При этом gdb-multiarch может работать прямо на Debian,
пока Gens KMod работает в Wine.
Для корректной работы gdb надо указать архитектуру и порядок байтов в машинных словах (endianness).
$ gdb-multiarch
[...]
(gdb) set architecture m68k
The target architecture is assumed to be m68k
(gdb) show endian
The target endianness is set automatically (currently little endian)
(gdb) set endian big
The target is assumed to be big endian
(gdb) target remote localhost:6868
Remote debugging using localhost:6868
- Изучение памяти позволило найти буферы для почты и ключа.
После введения 1111BBBBBBBBB в качестве почты:
(gdb) x/4096b 0xff0000
[...]
0xff01a8: 0x26 0x10 0x31 0x31 0x31 0x31 0x42 0x42
0xff01b0: 0x42 0x42 0x42 0x42 0x42 0x42 0x42 0x20
0xff01b8: 0x20 0x20 0x20 0x20 0x20 0x20 0x20 0x20
0xff01c0: 0x20 0x20 0x20 0x20 0x20 0x20 0x00 0x20
0xff01c8: 0x20 0x20 0x20 0x20 0x20 0x20 0x20 0x20
0xff01d0: 0x20 0x20 0x20 0x20 0x20 0x20 0x00 0x00
[...]
Для почты 1111BBBBBBBBBBDDDDDDDDDDDDDD и ключа DEEEEEEEEEEEEEEE:
(gdb) x/4096b 0xff01a8
0xff01a8: 0x26 0x10 0x31 0x31 0x31 0x31 0x42 0x42
0xff01b0: 0x42 0x42 0x42 0x42 0x42 0x42 0x42 0x42
0xff01b8: 0x44 0x44 0x44 0x44 0x44 0x44 0x44 0x44
0xff01c0: 0x44 0x44 0x44 0x44 0x44 0x44 0x00 0x44
0xff01c8: 0x45 0x45 0x45 0x45 0x45 0x45 0x45 0x45
0xff01d0: 0x45 0x45 0x45 0x45 0x45 0x45 0x45 0x00
0xff01d8: 0x00 0xff 0x25 0x3e 0x00 0x0e 0x00 0x00
[...]
Так что адреса почты и ключа - 0xff01aa и 0xff01c7. При этом
изначально буферы заполнены пробелами, но для ключа там только 15
пробелов, хотя ввести можно 16 символов.
- С
gdbможно попробовать трассировать по инструкциям при помощи простого цикла сx/1i $pcиsi.
Однако при этом трассировка работала медленно и застревала в цикле, который, вероятно, ждёт ввод:
(gdb) while 1
x/1i $pc
si
end
[...]
0x00000c92 in ?? ()
=> 0xc92: movew 0xc00004,%d0
0x00000c98 in ?? ()
=> 0xc98: btst #3,%d0
0x00000c9c in ?? ()
=> 0xc9c: bnes 0xc92
Вместе с такой трассировкой не получалось нажать "Start" и запустить
проверку. Выбраться из цикла точкой останова сразу за 0xc9c тоже не
получилось.
Хотя, вероятно, можно было бы поставить точку останова на коде для проверки длины. Но это было упущено.
Желание получить быструю трассировку инструкций привело к идее поправить эмулятор для записи хода выполнения в файл.
Выбор пал на Mednafen, который есть в основном репозитории операционной системы Debian и является свободным программным обеспечением.
Чтобы собрать Mednafen из исходников, можно использовать команду
apt-get -b source mednafen. Все зависимости нужные для сборки можно
поставить командой apt-get build-dep mednafen. Если её не
использовать и не будет нужных пакетов, будет выдана ошибка с
перечислением отсутствующих пакетов.
После сборки пакета mednafen остаётся каталог с исходниками. Внутри
есть папка src/, в которой есть объектные файлы и готовый
Makefile, так что после правок можно использовать make в каталоге
src/. Там же находится исполняемый файл mednafen.
Код эмулятора процессора m68k находится в файле
hw_cpu/c68k/c68kexec.c. Функция C68k_Exec вызывается на каждом
шаге. В неё-то и был добавлен код для трассировки.
Вначале нужно включить заголовочные файлы для работы с файлами и для функции выхода:
#include <stdio.h>
#include <stdlib.h>
В функции C68k_Exec сразу после строки Opcode = FETCH_WORD; был
добавлен код, приведённый ниже.
Код для открытия файла для результатов трассировки (trace.txt):
static FILE *trace = 0;
if (!trace) {
trace = fopen("trace.txt", "wb");
if (!trace) {
puts("fopen trace.txt failed");
exit(1);
}
}Код для выхода по достижению одной из веток с показом результата проверки ключа:
if (PC == 0x000019b8) {
puts("wrong_key branch");
exit(2);
}
if (PC == 0x00001a7a) {
puts("you_are branch");
exit(3);
}
if (PC == 0x00001d2a) {
puts("wrong_length branch");
exit(4);
}Надо заметить, что exit() - "грязный" выход для многопоточного
положения, использующего SDL/OpenGL. Иногда Mednafen падает на этом и
получает сигнал, так что полагаться на код возврата не стоит.
Код для сохранения большего количества данных из памяти, чтобы дизассемблировать длинные опкоды из изменяемое области памяти:
u32 mypc = PC;
PC += 2; /* <-- original line */
u32 op2 = FETCH_WORD;
PC += 2;
u32 op3 = FETCH_WORD;
PC -= 2;Собственно, код, выводящий данные в файл, пропуская некоторые адреса:
if (0x00000c92 <= PC && PC <= 0x00000cb6) {
/* skipped */
} else if (0x0000702a <= PC && PC <= 0x00007034) {
/* skipped */
} else {
fprintf(trace,
"%04x %04x%04x%04x"
" [A %x %x %x %x %x %x %x %x"
" D %x %x %x %x %x %x %x %x]\n",
mypc, Opcode, op2, op3,
CPU->A[0], CPU->A[1], CPU->A[2], CPU->A[3],
CPU->A[4], CPU->A[5], CPU->A[6], CPU->A[7],
CPU->D[0], CPU->D[1], CPU->D[2], CPU->D[3],
CPU->D[4], CPU->D[5], CPU->D[6], CPU->D[7]
);
}Флаги при этом не выводятся. Также не выводится память, используемая инструкцией. А состояние регистров выводится на момент до выполнения инструкции.
Изначально выводились только PC и Opcode и для всех инструкций.
При этом в процессе трассировки записывалось около 2.5 миллионов
инструкций, из которых ~4/5 были в цикла 0x0c92-0x0cb6 и
0x702a-0x7034.
> 0x00000c92 303900c00004 move.w 0xc00004, d0
0x00000c98 08000003 btst.b 0x3, d0
< 0x00000c9c 66f4 bne.b 0xc92
; CODE XREFS from fcn.0000067c (0xcb6, 0xce0)
> 0x00000c9e 303900c00004 move.w 0xc00004, d0
0x00000ca4 08000003 btst.b 0x3, d0
< 0x00000ca8 6600ff4a bne.w 0xbf4
> 0x0000702a 1018 move.b (a0)+, d0
0x0000702c 4880 ext.w d0
0x0000702e d041 add.w d1, d0
0x00007030 32c0 move.w d0, (a1)+
0x00007032 b5c8 cmpa.l a0, a2
< 0x00007034 66f4 bne.b 0x702a
Исключив эти циклы, получилось сократить трассировку до сотен тысяч
инструкций. Тогда появилась идея, что нужно сразу нажимать Start.
Чтобы нажимать сразу Start, была добавлена строка
keys[SDLK_RETURN] = 1; в функции UpdatePhysicalDeviceState в файле
drivers/input.cpp.
memcpy(keys, SDL_GetKeyState(0), MKK_COUNT); /* <-- original line */
keys[SDLK_RETURN] = 1;
Старт с заданного состояния не потребовал модификаций исходников.
Загрузка сохранённого состояния - стандартная возможность эмуляторов.
Некоторые эмуляторы позволяют указывать файл с сохранением через
командную строку. Mednafen использует autosave: есть особый файл с
состоянием, с которым стартует эмулятор и в который автоматически
сохраняется состояние при закрытии эмулятора. Для использования этой
возможности надо указать autosave 1 в файле конфигурации Mednafen
(~/.mednafen/mednafen-09x.cfg).
При этом состояние будет сохраняться в файл с расширением .mca:
~/.mednafen/mcs/best_reverser_phd9_rom_v4.99e440e408b93591d6fbedfb548d8334.mca
Файл с состоянием - бинарный файл, сжатый gzip'ом. Если его распаковать, можно увидеть строки из памяти, в частности введённые почту и ключ. Оказалось, что можно не вводить ключ вручную, заменяя его в файле состояния.
С заготовленным состоянием и автоматической проверкой при старте, количество строк в результате трассировки упало до 28900.
Формат результатов:
pc opcode [A a0 a1 a2 a3 a4 a5 a6 a7 D d0 d1 d2 d3 d4 d5 d6 d7]
где [A, D, ] и пробелы вставлены, как есть; на месте остальных
подстрок находятся следующие значения:
pc- адрес инструкции в формате%04x(хотя может быть 5 цифр),opcode- 6 байт в hex из памяти по адресу инструкции (скрипт для добавления ассемблера ниже обрезает до 2 байт),a0-a7,d0-d7- значения регистров на момент до выполнения инструкции, записанные в шестнадцатеричной системе счисления.
В примерах вывода ниже часть значений регистров убрана: несколько
значений заменены на ..., отдельные значения заменены на ..
Результаты трассировки записывались в текстовый файл в простом формате, так что использовались соответствующие инструменты для работы с этим файлом.
- Подсчёт статистики по файлу трассировки:
$ cut -d ' ' -f 1 trace.txt | sort | uniq -c
(Тут можно было бы добавить | less, но использовался shell-mode в
emacs, так что свободная работа с историей вывода команд была без
дополнительных усилий.)
- Поиск инструкции по адресу:
$ grep '^1f12 ' trace.txt
1f12 b46e00226700 [A ff1fd4 ff0de4 9d ff0d46 56bc 11d0 ff1d48 ffffff4e D ffffff 9fd4 cb4c ff0d46 1c 9 fffedc e3e]
Подобным образом можно выбирать строки по содержимому регистра. И команды можно сочетать.
- Взятие части, начиная с какого адреса:
$ sed -ne '/^1f12 /,$ p' trace.txt
Или вариант, требующий знания общего количества (зато легко получаемый из поиска):
$ grep -A 100000 '^1f12 ' trace.txt
Подобным образом можно брать и небольшое количество соседних строк.
- Добавление ассемблера (это должен был быть маленький one-liner, но что-то пошло не так...):
grep -B 100000 '^1f12 ' trace.txt | python -c '
import sys;
h = {};
h2 = {};
[ (h.__setitem__(int(l[2 : 12], 16), l[33 : ]),
h2.__setitem__(l[18 : 32].strip(), l[33 : ]))
for l in open("bdis")
if l[2 : 4] == "0x" ];
print "-*- truncate-lines: t -*-";
[ sys.stdout.write(
l
if l == "\n"
else l.strip() + " " + h.get(
int(l.split(" ", 1)[0], 16),
h2.get(l.split(" ", 2)[1],
h2.get(l.split(" ", 2)[1][ : 4],
h2.get(l.split(" ", 2)[1][ : 8],
"???\n")))))
for l in sys.stdin ]
' \
| perl -pe 's/(\[.*\])(.*)/$2 $1/' \
| perl -pe 's/^([a-f0-9]+ [a-f0-9]{4})[a-f0-9]{8}/$1/' \
| python -c '
import sys;
[ sys.stdout.write(
l
if "[" not in l
else l.split(" [")[0].ljust(38) + "[" + l.split("[")[1])
for l in sys.stdin ]
' > ttb2.txt
На выходе получается история выполнения с отформатированным ассемблером и значениями регистров:
1f0c 508f addq.l 0x8, a7 [A ff1fd4 ff0de4 9d ff0d46 56bc 11d0 ff1d48 ffffff46 D ffffff 9fd4 9e ff0d46 1c 9 fffedc e3e]
1f0e 342e move.w 0x24(a6), d2 [A ff1fd4 ff0de4 9d ff0d46 56bc 11d0 ff1d48 ffffff4e D ffffff 9fd4 9e ff0d46 1c 9 fffedc e3e]
1f12 b46e cmp.w 0x22(a6), d2 [A ff1fd4 ff0de4 9d ff0d46 56bc 11d0 ff1d48 ffffff4e D ffffff 9fd4 cb4c ff0d46 1c 9 fffedc e3e]
Похоже, это немного не логично, что регистры справа, но при этом состояние в них приводится на момент до выполнения этой инструкции.
Связь по опкодам длиннее 6 байт не реализована. В выводе все опкоды обрезаны до 2 байт.
При этом комментарии из файла bdis, записанные на строках вместе с
инструкциями, попадают в вывод.
- Изучение результата трассировки подряд происходило в текстовом редакторе.
Для ключа A01BC23DE45FG67H можно получить следующий результат.
Самый конец трассировки:
1998 4a81 tst.l d1 [A ... D 0 5 ...]
199a 660e bne.b 0x19aa ; go to "Wrong key..."[A ... D ...]
19aa 4878 pea.l 0xe.w [A ... ffffff4e D ...]
19ae 4878 pea.l 0x8.w [A ... ffffff4a D ...]
19b2 4879 pea.l 0xfe30.l ; "Wrong key..."[A ... ffffff46 D ...]
Регистр a7 является указателем на стек, так что инструкции pea
меняют его.
Для перехода в ветку "Wrong key" проверяется регистр d1. Его
значение - 5, а должно быть 0. Следя за изменением значения
регистра, за 112 инструкций до этого можно найти такую проверку:
1f12 b46e cmp.w 0x22(a6), d2 [A ... ff1d48 . D . 9fd4 7d24 ...]
1f16 6700 beq.w 0x20ea [A ... ff1d48 . D . 9fd4 7d24 ...]
1f1a 7205 moveq 0x5, d1 [A ... ff1d48 . D . 9fd4 7d24 ...]
1f1c 6000 bra.w 0x190c [A ... ff1d48 . D . 5 7d24 ...]
В ветке 0x20ea находится присваивание 0 в d1:
> 0x000020ea 7200 moveq 0x0, d1
< 0x000020ec 6000f81e bra.w 0x190c
Так что можно было надеяться, что нужно свернуть именно туда.
Поиск 0x22(a6) приводит к следующей инструкции:
1de0 3d41 move.w d1, 0x22(a6) [A . ff1d48 . D . cb4c ...]
Это запись значения в память. Но между этой записью и той проверкой случается ещё 25254 инструкций, так что нет гарантий, что память не была перезаписана другими инструкциями.
С другой стороны, проверка сравнивает только 2 байта, так что её должно быть легко преодолеть перебором.
Цикл для пробы случайных ключей:
$ while true; do
perl -C0 -e 'print +(A..Z,0..9)[rand 36] for 0..15' > key \
&& perl -C0 -pe "s/A01BC23DE45FG67H/`cat key`/" < state0 > state1 \
&& gzip < state1 > ~/.mednafen/mcs/best_reverser_phd9_rom_v4.99e440e408b93591d6fbedfb548d8334.mca \
&& DISPLAY=:0 ./src/mednafen best_reverser_phd9_rom_v4.bin 2>/dev/null \
| tail -n 1;
target="`grep ^1f12 trace.txt | cut -d ' ' -f 15`";
echo "`cat key` $target";
mv key outkeys/"$target";
done
Тут есть некоторая избыточность, чтобы не потерять прогресс. Плюс потребовалось небольшое везение, потому что такой перебор идёт не подряд и не гарантирует нахождение всех значений за разумное время. Хотя один запуск Mednafen занимал ~0.26 секунды, что давало примерно 3 итерации цикла в секунду.
В итоге, был найден ключ D2S5YSX951P0OAD3. Он даёт значение 0xcb4c
в момент проверки по адресу 0x1f12 и проверка проходит успешно, так
что значение в памяти не было перезаписано (или было восстановлено
после перезаписи).
С новым ключом код проходит проверку, попадает в другую ветку,
сталкивается с неправильной инструкцией и попадает в обработчик
исключения по адресу 0x0408.
(Тут упоминается,
что такое исключение позволяет старым моделям процессора эмулировать
инструкции новых моделей.)
1998 4a81 tst.l d1 [A ... D 0 0 ...]
199a 660e bne.b 0x19aa ; go to "Wrong key..."[A ... D ...]
199c 2f0b move.l a3, -(a7) [A ... D ...]
199e 4eba jsr fcn.00001504(pc) [A ... D ...]
1504 23ef move.l 0x4(a7), 0xff0d12.l [A ... D ...]
150c f000 invalid [A ... D ...]
0408 4eba jsr fcn.00000344(pc) [A ... D ...]
Из дизассемблера:
;-- Reserv0:
;-- Reserv1:
0x00000408 4ebaff3a jsr fcn.00000344(pc)
0x0000040c 48e7c0c0 movem.l d0-d1/a0-a1, -(a7)
0x00000410 207900ff0d12 movea.l 0xff0d12.l, a0
0x00000416 4e90 jsr (a0)
0x00000418 4cdf0303 movem.l (a7)+, d0-d1/a0-a1
0x0000041c 4e73 rte
Однако на общий подход это не влияет. В этой задаче надо смотреть на конец трассировки:
19a4 4a80 tst.l d0 [A ... D 0 ...]
19a6 6600 bne.w 0x1a6c ; go to "YOU ARE ..."[A ... D ...]
19aa 4878 pea.l 0xe.w [A ... D ...]
19ae 4878 pea.l 0x8.w [A ... D ...]
19b2 4879 pea.l 0xfe30.l ; "Wrong key..."[A ... D ...]
В этой проверке регистр должен быть не нулевым, чтобы ход выполнения оказался в победной ветке.
Пропустив 9 инструкций до проверки:
ff0daa b642 cmp.w d2, d3 [A ... D . . 671090d3 5617 ...]
ff0dac 57c0 seq.b d0 [A ... D f8ad3 ...]
ff0dae 4880 ext.w d0 [A ... D f8a00 ...]
ff0db0 48c0 ext.l d0 [A ... D f0000 ...]
ff0db2 4480 neg.l d0 [A ... D 0 ...]
По адресу 0xff0daa сравниваются значения по 2 байта из регистров
d2 и d3. Старшие байты в регистрах игнорируются. Результат
проверки сохраняется в регистр d0 следующими инструкциями. При этом
значение в регистре d2 зависит от ключа (а в d3 от почты).
Изучая историю выполнения дальше, были замечены повторы кода,
начинающегося с адреса 0x1526. По адресу 0x152e в регистре видно
аргумент функции:
$ grep -e '^152e ' -e '^199a ' trace.txt | ...оформление...
152e 1210 move.b (a0), d1 [A ff01c7 ... D ...]
152e 1210 move.b (a0), d1 [A ff01cb ... D ...]
199a 660e bne.b 0x19aa ; go to "Wrong key..."[...]
152e 1210 move.b (a0), d1 [A ff01cf ... D ...]
152e 1210 move.b (a0), d1 [A ff01d3 ... D ...]
Тут видно, что в регистре a0 оказываются указатели в буфере ключа с
шагом по 4 байта. Смещения +0 и +4 оказываются до первой проверки,
а смещения +8 и +12 - после первой проверки.
Это дало надежду, что изменение конца ключа влияет на вторую проверку и не влияет на первую проверку. Это было легко попробовать и предположение подтвердилось. Можно было бы снова делать ключи со случайным концом и ждать совпадения, но в процессе проб было замечено, что значение в регистре не очень сложно зависит от ключа.
Можно заметить, что d3 в значении ...90d3 совпадает с D3 на
конце использованного ключа. Оказалось, что это не просто совпадение.
Второй байт зависит от предпоследней пары символов в ключе немного
сложнее, но получилось подобрать эти символы вручную.
Новый ключ с исправленным концом прошёл вторую проверку и программа
вывела долгожданное сообщение: YOU ARE THE BEST REVERSER!
Пример успешной пары: почта 000 и ключ D2S5YSX951P05300.
ff0daa b642 cmp.w d2, d3 [A ... D . . 67105100 5100 ...]
Задача позволяет познакомиться с ассемблером архитектуры m68k и с
некоторыми особенностями Sega Mega Drive. При этом задачу можно
решить, избегая глубокого вникания в код.
Уровень удовольствия от задачи: 10 непонятных функций из 10! Рекомендую!